Comparing community structure identification

2005/05/31 by León Danon, Leon Danon, Jordi Duch +4 · 15 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #cond-mat.dis-nn #physics.soc-ph

paper · pdf · doi:10.1088/1742-5468/2005/09/p09008

published as J. Stat. Mech. (2005) P09008 · 10 pages, 3 figures, 1 table. v2: condensed, updated version as appears in JSTAT

openalex publication_date 2005/09/01 · arxiv created 2005/10/18 · arxiv updated 2009/12/01 · openalex created_date 2020/11/23 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• Community structure in social and biological networks
• Modern Graph Theory
• Community Structure in Jazz
• Subnetwork hierarchies of biochemical pathways
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• A faster algorithm for betweenness centrality*
• The large-scale structure of semantic networks: statistical analyses and\n a model for semantic growth

Cited by

• Large-scale structure of time evolving citation networks
• Bayesian Approach to Network Modularity
• Optimal map of the modular structure of complex networks
• Comparative definition of community and corresponding identifying algorithm
• Revisiting Date and Party Hubs: Novel Approaches to Role Assignment in Protein Interaction Networks
• Identifying network communities with a high resolution
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Local resolution-limit-free Potts model for community detection
• Evaluating local community methods in networks
• A new method for quantifying network cyclic structure to improve\n community detection
• Robustness of community structure in networks
• Synchronizability determined by coupling strengths and topology on complex networks
• Covariance, correlation matrix, and the multiscale community structure of networks
• Broad lifetime distributions for ordering dynamics in complex networks
• Synchronization processes in complex networks