Fortunato-benchmark

Community detection algorithms: a comparative analysis1,2 1Andrea Lancichinetti and Santo Fortunato1Complex Networks and Systems, Institute for Scienti c Interchange (ISI), Viale S. Severo 65, 10133, Torino, Italy2Physics Department, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, ItalyUncovering the community structure exhibited by real networks is a crucial step towards anunderstanding of complex systems that goes beyond the local organization of their constituents.Many algorithms have been proposed so far, but none of them has been subjected to strict teststo evaluate their performance. Most of the sporadic tests performed so far involved small networkswith known community structure and/or arti cial graphs with a simpli ed structure, which is veryuncommon in real systems. Here we test several methods against a recently introduced class ofbenchmark graphs, with heterogeneous distributions of degree and community size. The methodsare also tested against the benchmark by Girvan and Newman and on random graphs. As a resultof our analysis, three recent algorithms introduced by Rosvall and Bergstrom, Blondel et al. andRonhovde and Nussinov, respectively, have an excellent performance, with the additional advantageof low computational complexity, which enables one to analyze large systems.PACS numbers: 89.75.-k, 89.75.HcKeywords: Networks, community structureI. INTRODUCTION without community structure. The most popular versionof the ...