Statistical significance of communities in networks
arXiv:0907.3708 · doi:10.1103/PhysRevE.81.046110
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.
arXiv comment9 pages, 8 figures, 2 tables. The software to calculate the C-score can be found at http://filrad.homelinux.org/cscore
References in corpus (29)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- 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
- Defining and identifying communities in networks
- Community detection in complex networks using Extremal Optimization
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Synchronization reveals topological scales in complex networks
- Generation of uncorrelated random scale-free networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Mixture models and exploratory analysis in networks
- Extracting the hierarchical organization of complex systems
- Detecting Network Communities: a new systematic and efficient algorithm
- Robustness of community structure in networks
- Distance, dissimilarity index, and network community structure
- Assessing the relevance of node features for network structure
- Modularity and Extreme Edges of the Internet
- 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 (43)
- 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
- Tolerating the Community Detection Resolution Limit with Edge Weighting
- 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
- Core of communities in bipartite networks
- Gene communities in co-expression networks across different tissues
- 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
- Spectral coarse graining for random walk in bipartite networks
- Multiple phases in modularity-based community detection
- Resampling effects on significance analysis of network clustering and ranking
- 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
- Community Structure Characterization
- Detecting Statistically Significant Communities
- 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
- Reinventing the Triangles: Rule of Thumb for Assessing Detectability
- Hypothesis testing for community structure in temporal networks using e-values