Upptäckten och analysen av samhällsstrukturen i nätverk är ett ämne av stort nytt intresse inom fysikvärlden, men de flesta metoder som hittills föreslagits är olämpliga för mycket stora nätverk på grund av deras beräkningskostnader. Här presenterar vi en hierarkisk tätbebyggelsealgoritm för att upptäcka samhällsstruktur som är snabbare än många konkurrerande algoritmer: dess körtid på ett nätverk med n hörn och m kanter är O(md log n) där d är djupet av dendrogram som beskriver samhällsstrukturen. Många verkliga nätverk är glesa och hierarkiska, med m  på n och d på log n, i vilket fall vår algoritm körs i huvudsak linjär tid, O(n log 2 n). Som ett exempel på tillämpningen av denna algoritm använder vi den för att analysera ett nätverk av objekt till salu på webbplatsen för en stor online återförsäljare, objekt i nätverket länkas om de ofta köps av samma köpare. Nätverket har över 400 000 hörn och 2 miljoner kanter. Vi visar att vår algoritm kan extrahera meningsfulla samhällen från detta nätverk, avslöjar storskaliga mönster som finns i kundernas köpvanor.
En snabb community upptäckt algoritm i mycket stort nätverk föreslogs med ungefärlig linjär tids komplexitet O(nlog 2 n), där n är antalet noder REF.
Finding community structure in very large networks
{'venue': 'Phys. Rev. E 70, 066111 (2004)', 'journal': None, 'mag_field_of_study': ['Physics', 'Medicine']}