Att upptäcka kluster eller samhällen i stora verkliga grafer som stora sociala nätverk eller informationsnätverk är ett problem av stort intresse. I praktiken väljer man vanligtvis en objektiv funktion som fångar intuitionen hos ett nätverkskluster som uppsättning noder med bättre intern konnektivitet än extern konnektivitet, och sedan tillämpar man approximationsalgoritmer eller heuristik för att extrahera uppsättningar av noder som är relaterade till den objektiva funktionen och som "ser ut" bra samhällen för tillämpning av intresse. I detta dokument utforskar vi en rad metoder för att upptäcka nätverk för att jämföra dem och förstå deras relativa prestanda och systematiska fördomar i de kluster de identifierar. Vi utvärderar flera gemensamma objektiva funktioner som används för att formalisera begreppet nätverk gemenskap, och vi undersöker flera olika klasser av approximation algoritmer som syftar till att optimera sådana objektiva funktioner. Dessutom, snarare än att bara fastställa ett mål och be om en approximation till den bästa kluster av någon storlek, anser vi en storlekslös version av optimeringsproblem. Med tanke på samhällets kvalitet som en funktion av sin storlek ger en mycket finare lins med vilken man kan undersöka gemenskapens detektionsalgoritmer, eftersom objektiva funktioner och approximationsalgoritmer ofta har icke-uppenbara storleksberoende beteende.
En rad metoder för detektering av samhället har utvärderats empiriskt och jämförts i REF.
Empirical comparison of algorithms for network community detection
{'venue': "WWW '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}