Strukturen av komplexa nätverk i verkligheten har länge varit ett intresseområde, och ett vanligt sätt att beskriva strukturen i ett nätverk har varit med den k-core nedbrytningen. Kärnantalet av en nod kan ses som ett mått på dess centralitet och betydelse, och används av tillämpningar såsom gemenskap upptäckt, förståelse virala spridningar, och upptäcka bedragare. Vi konstaterar dock att den k-kärniga nedbrytningen lider av en viktig brist: nämligen, den beräknas globalt, och så om nätverket innehåller olika regioner av olika densiteter, kan den glesare bland dessa regioner försummas. För att lösa detta problem, föreslår vi k-peak graf sönderdelningsmetoden, baserad på k-core algoritmen, som finner centra av olika regioner i grafen. Våra bidrag är följande: (1) Vi presenterar en ny graf nedbrytning-k-peak nedbrytning-och motsvarande algoritm, och utför en teoretisk analys av dess egenskaper. (2) Vi beskriver en ny visualiseringsmetod, "Mountain Plot", som kan användas för att bättre förstå en grafs globala struktur. (3) Vi utför en omfattande empirisk analys av verkliga grafer, inklusive tekniska, sociala, biologiska, och samarbete grafer, och visar hur k-peak nedbrytning ger insikt i strukturerna i dessa grafer. (4) Vi demonstrerar fördelen av att använda k-peak nedbrytningen i olika applikationer, inklusive gemenskap upptäckt, spridning och identifiera viktiga proteiner.
Govindan m.fl. REF föreslår k-peak nedbrytning som gör det möjligt att hitta lokala täta regioner i motsats till klassisk kärn nedbrytning.
The k-peak Decomposition: Mapping the Global Structure of Graphs
{'venue': 'WWW', 'journal': None, 'mag_field_of_study': ['Computer Science']}