Vi använder en Potts modell community detektion algoritm för att exakt och kvantitativt utvärdera hierarkisk eller multiupplösning struktur av en graf. Vår multiupplösningsalgoritm beräknar korrelationer mellan flera kopior ("replicas") av samma graf över en rad upplösningar. Signifikanta multiupplösningsstrukturer identifieras av starkt korrelerade repliker. Den genomsnittliga normaliserade ömsesidiga informationen, informationsvariationen och andra åtgärder ger i princip en kvantitativ uppskattning av de "bästa" resolutionerna och anger den relativa styrkan hos strukturerna i grafen. Eftersom metoden är baserad på informationsjämförelser, kan den i princip användas med alla community detektion modell som kan undersöka flera resolutioner. Vårt tillvägagångssätt kan utvidgas till andra optimeringsproblem. Som en lokal åtgärd undviker vår Potts-modell den "upplösningsgräns" som påverkar andra populära modeller. Med denna modell, vår gemenskap detektionsalgoritm har en noggrannhet som rankas bland de bästa av för närvarande tillgängliga metoder. Med hjälp av den kan vi undersöka grafer över 40 miljoner noder och mer än en miljard kanter. Vi rapporterar vidare att multiupplösningsvarianten av vår algoritm kan lösa system på minst 200 000 noder och 10 miljoner kanter på en enda processor med exceptionellt hög noggrannhet. För typiska fall hittar vi en superlinjär skalning, O(L 1.3 ) för community detection och O(L 1.3 log N ) för multiupplösningsalgoritm där L är antalet kanter och N är antalet noder i systemet.
I sin sammanfattning rekommenderar författarna att använda olika algoritmer när man studerar en grafs samhällsstruktur för att erhålla algoritmoberoende information, och föreslår Infomap, Multilevel och Multiupplösningsalgoritm REF som de bästa kandidaterna.
Multiresolution community detection for megascale networks by information-based replica correlations
{'venue': 'Physical Review E 80, 016109 (2009)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Medicine']}