Statistical significance of communities in networks

Abstract

Nodes in real-world networks are usually organized in local modules. These groups, called communities, are intuitively defined as sub-graphs with a larger density of internal connections than of external links. In this work, we introduce a new measure aimed at quantifying the statistical significance of single communities. Extreme and Order Statistics are used to predict the statistics associated with individual clusters in random graphs. These distributions allows us to define one community significance as the probability that a generic clustering algorithm finds such a group in a random graph. The method is successfully applied in the case of real-world networks for the evaluation of the significance of their communities.

9 pages, 8 figures, 2 tables. The software to calculate the C-score can be found at http://filrad.homelinux.org/cscore

References in corpus (14)

• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• Robustness of community structure in networks
• Limited resolution in complex network community detection with Potts model approach
• When are networks truly modular?
• (Un)detectable cluster structure in sparse networks
• Inversion method for content-based networks

Cited by in corpus (42)

• Community detection in graphs
• Finding statistically significant communities in networks
• Limits of modularity maximization in community detection
• Robust Detection of Dynamic Community Structure in Networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Social features of online networks: the strength of intermediary ties in online social media
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Significant Scales in Community Structure
• Entropy of stochastic blockmodel ensembles
• Social significance of community structure: Statistical view
• Comparing and modeling land use organization in cities
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Core-periphery structure requires something else in the network
• Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
• Human diffusion and city influence
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Significant communities in large sparse networks
• A generalised significance test for individual communities in networks
• Combinatorial approach to Modularity
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• Biogeographical network analysis of plant species distribution in the Mediterranean region
• Gene communities in co-expression networks across different tissues
• Core of communities in bipartite networks
• Mapping flows on weighted and directed networks with incomplete observations
• Graph coarse-graining reveals differences in the module-level structure of functional brain networks
• The stability to instability transition in the structure of large scale networks
• Multiple phases in modularity-based community detection
• Resampling effects on significance analysis of network clustering and ranking
• Spectral coarse graining for random walk in bipartite networks
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• A generalized hypothesis test for community structure in networks
• Detecting the optimal number of communities in complex networks
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Criterions for locally dense subgraphs
• Detecting Statistically Significant Communities
• Community Structure Characterization
• EC-SBM Synthetic Network Generator
• Bootstrapping under constraint for the assessment of group behavior in human contact networks
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Hypothesis testing for community structure in temporal networks using e-values
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability