Comparing community structure identification

By Leon Danon, Albert Díaz-Guilera, Jordi Duch, Alex Arenas. 2005

2,832 citations recorded by the source corpus.

We compare recent approaches to community structure identification in terms of sensitivity and computational cost. The recently proposed modularity measure is revisited and the performance of the methods as applied to ad hoc networks with known community structure, is compared. We find that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes. The work is intended as an introduction as well as a proposal for a standard benchmark test of community detection methods.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

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

How researchers see this paper

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

In Artificial Intelligence

1. Santo Fortunato
2. Jure Leskovec
3. Darko Hric
4. Olaf Sporns
5. Mark Newman
6. Boleslaw K. Szymanski
7. Jierui Xie
8. Jaewon Yang

In Statistical and Nonlinear Physics

1. Santo Fortunato
2. Jure Leskovec
3. Olaf Sporns
4. Darko Hric
5. M. A. Porter
6. Jaewon Yang
7. Richard F. Betzel
8. Mark Newman

Citations in the corpus

• A socio-aware overlay for publish/subscribe communication in delay tolerant networks (2007, neutral): “See the reviews by Newman [27] and Danon et al. [ 8 ] for methodological overviews and comparative study of different algorithms.”
• Community detection in social networks (2016, neutral): “in 2009, Danon et al.(12) in 2005, and Plantié and Crampes(13) in 2013.”
• 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).”
• Community detection in networks: A user guide (2016, methodology): “Since the first thorough comparative analysis of clustering algorithms [85], the NMI has been regularly used to compute the similarity of partitions in the literature.”
• Detecting highly overlapping community structure by greedy clique expansion (2010, methodology): “[25] first applied NMI to the problem of evaluating the similarity of two sets of communities, but defined the measure only for partitions.”
• Statistical properties of community structure in large social and information networks (2008, background): “For example, see the reviews on community identification [24, 9], graph and spectral clustering [13, 30], and the monographs on spectral graph theory and complex networks [6, 7].”
• Synchronization in complex networks (2008, background): “Finding the best partition of a network into communities is a very hard problem.”
• Defining and evaluating network communities based on ground-truth (2012, background): “…[9] has proven to be a challenging task [10], [18], [17] due to three reasons: There exist multiple structural definitions of network communities [5], [24]; Even if we would agree on a single common structural definition ( i.e. , a single scoring function), the formalizations of community…”
• Detect overlapping and hierarchical community structure in networks (2008, neutral): “One can refer to [13] for reviews.”
• Finding community structure in networks using the eigenvectors of matrices. (2006, background): “[6, 36].”
• Community detection in graphs (2009, methodology): “[238] and by Lancichinetti and Fortunato [424] (Section 15.”
• Focal Brain Lesions to Critical Locations Cause Widespread Disruption of the Modular Organization of the Brain (2012, neutral): “1276 Journal of Cognitive Neuroscience Volume 24, Number 6 D ow nloaded from http://direct.m it.edu/jocn/article-pdf/24/6/1275/1777991/jocn_a_00222.pdf by guest on 07 June 2021”
• Modularity and community structure in networks. (2006, neutral): “Modularity and community structure in networks”
• Link communities reveal multiscale complexity in networks (2009, methodology): “Modularity has been widely used for similar purposes in node-hierarchies, 18,41 but is not easily defined for overlapping communities.”
• The modular and integrative functional architecture of the human brain (2015, methodology): “In all networks, we found a high level of NMI between the modules and the cognitive components, suggesting that they share a similar spatial distribution (Shen network NMI = 0.523; Power network NMI = 0.603; Gordon network NMI = 0.542; Craddock network NMI = 0.410; Crossley network NMI = 0.410; P < ”