Robustness of community structure in networks

2007/09/13 by Brian Karrer, Elizaveta Levina, M. E. J. Newman · 3 citations
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #Peer-to-Peer Network Technologies #cond-mat.stat-mech #physics.data-an #physics.soc-ph

paper · pdf · doi:10.1103/physreve.77.046119

published as Phys. Rev. E 77, 046119 (2008) · 10 pages, 2 figures

arxiv created 2007/09/13 · openalex publication_date 2008/04/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.

Citations

• Thermodynamics of Community Structure
• Community structure in social and biological networks
• Directed network modules
• Evolution of sociology freshmen into a friendship network
• Finding communities in linear time: a physics approach
• Comparing community structure identification
• The large-scale organization of metabolic networks
• Comparing clusterings—an information based distance

Cited by

• Node-Context Network Clustering using PARAFAC Tensor Decomposition
• GA Based Q-Attack on Community Detection
• Detecting the optimal number of communities in complex networks