Community detection algorithms: a comparative analysis: invited presentation, extended abstract

By Santo Fortunato, Andrea Lancichinetti. ValueTools, 2009

2,272 citations recorded by the source corpus.

Uncovering the community structure exhibited by real networks is a crucial step toward an understanding 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 tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman [Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)] and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom [Proc. Natl. Acad. Sci. U.S.A. 104, 7327 (2007); Proc. Natl. Acad. Sci. U.S.A. 105, 1118 (2008)], Blondel [J. Stat. Mech.: Theory Exp. (2008), P10008], and Ronhovde and Nussinov [Phys. Rev. E 80, 016109 (2009)] have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a641960669100a3de0b1dfc80b34dbdfc951d023

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Modular Brain Networks (2015, methodology): “Several recent studies have undertaken the task of benchmarking community detection methods, including many of those surveyed here (Danon et al. 2005, Lancichinetti et al. 2009).”
Memory in network flows and its effects on spreading dynamics and community detection (2013, methodology): “ent. The memory effects on community detection have important network-theoretical implications. Community-detection methods typically identify modules with stronger internal than external connections (26,27) or with relatively long ﬂow persistence times (23,25). A problem with these methods is that ”
Finding Statistically Significant Communities in Networks (2010, neutral): “As a term of comparison we used Infomap [49], which has proved to be very accurate on artificial benchmark graphs [50].”
An efficient and principled method for detecting communities in networks (2011, methodology): “4: Results of tests of the nonoverlapping community algorithm described in the text applied to synthetic networks generated using the LFR benckmark model of Lan-cichinetti et al. [31].”
Finding overlapping communities in networks by label propagation (2009, methodology): “[26] conta ins disjoint communities only.”
The modular and integrative functional architecture of the human brain (2015, methodology): “We chose to use the InfoMap algorithm, because, compared with other algorithms on networks for which the true division of nodes into modules is known, it achieves the most accurate division of nodes into modules (95, 96).”
Challenges in unsupervised clustering of single-cell RNA-seq data (2019, methodology): “Only the Louvain algorithm has been widely applied to scRNA seq data, despite many others being available 30 , some of which have demonstrated better per formance in benchmarking studies 31 .”
The Role of Gender in Scholarly Authorship (2012, background): “topology of scientific networks can be used to map the structure of science, and the map equation [13,14] has proven to be a particularly effective method [15].”
Detecting the dynamics of urban structure through spatial network analysis (2014, methodology): “According to the comparative analysis of different methods (Lancichinetti and Fortunato 2009), the map equation approach called Infomap developed by (Rosvall and Bergstrom 2008) is one of the recent algorithms that has shown excellent performance in generating such a two-level hierarchy of clusters…”
Stable Community Cores in Complex Networks (2012, background): “The automatic detection of such communities has attracted much attention in recent years and many community detection algorithms have been proposed, see [11] for a survey.”
Large-Scale Community Detection on YouTube for Topic Discovery and Exploration (2011, methodology): “A pre-processing step is employed to select seed videos from which the local cluster will be grown.”
Using Geodesic Space Density Gradients for Network Community Detection (2017, methodology): “For each setting, 100 networks are randomly generated by using the implementation of the original authors [28].”
Detecting highly overlapping community structure by greedy clique expansion (2010, methodology): “6 with the results of various disjoint CAAs in the recent comparative benchmarking of Lancichinetti and Fortunato [4].”
Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems (2010, methodology): “To test the performance of our algorithm, we used the benchmark paradigm developed by Lancichinetti and Fortunato (19).”