Att upptäcka täta subgrafer och förstå relationerna mellan dem är ett grundläggande problem i grafbrytning. Vi vill inte bara identifiera täta subgrafer, utan också bygga en hierarki bland dem (t.ex. större men glesare subgrafer som bildas av två mindre täta subgrafer). Skalsalgoritmer (k-core, k-truss och kärndekomposition) har varit effektiva för att lokalisera många täta subgrafer. Man har dock för det mesta förbisett att konstruera en hierarkisk representation av densitetsstruktur, även korrekt beräkning av de anslutna k-kärnorna och k-trusserna. För att hålla koll på anslutna komponenter under peeling krävs ytterligare en traversal operation, som är lika dyr som peelingprocessen. I detta dokument börjar vi med en grundlig undersökning och pekar på nyanser i problemformuleringar som leder till betydande skillnader i körtider. Vi föreslår sedan effektiva och generiska algoritmer för att konstruera hierarkin av täta subgrafer för k-kärna, k-truss eller någon kärndekomposition. Våra algoritmer utnyttjar den osammanhängande skogsdatastrukturen för att effektivt bygga hierarkin under travertal. Dessutom introducerar vi en ny idé för att undvika traversal. Vi konstruerar subgraferna medan vi besöker stadsdelar i peelingprocessen, och bygger relationer till tidigare konstruerade subgrafer. Vi överväger också en befintlig idé för att hitta k-kärnhierarkin och anpassa oss till våra mål på ett effektivt sätt. Experiment på olika typer av storskaliga verkliga nätverk visar betydande hastigheter jämfört med naiva algoritmer och befintliga alternativ. Våra algoritmer överträffar också de hypotetiska gränserna för en möjlig traversal-baserad lösning.
Sariyuce och Pinar REF utvecklar generiska algoritmer för att konstruera hierarkin av täta subgrafer (för k-kärna, k-truss eller någon kärndekomposition) på ett sådant sätt att man håller reda på de olika anslutna komponenterna.
Fast Hierarchy Construction for Dense Subgraphs
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}