Measuring Significance of Community Structure in Complex Networks
arXiv:0902.3331 · doi:10.1103/PhysRevE.82.066106
Abstract
Many complex systems can be represented as networks and separating a network into communities could simplify the functional analysis considerably. Recently, many approaches have been proposed for finding communities, but none of them can evaluate the communities found are significant or trivial definitely. In this paper, we propose an index to evaluate the significance of communities in networks. The index is based on comparing the similarity between the original community structure in network and the community structure of the network after perturbed, and is defined by integrating all the similarities. Many artificial networks and real-world networks are tested. The results show that the index is independent from the size of network and the number of communities. Moreover, we find the clear communities always exist in social networks, but don't find significative communities in proteins interaction networks and metabolic networks.
arXiv comment6 pages, 4 figures, 1 table
References in corpus (27)
- 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
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Specificity and stability in topology of protein networks
- Comparing community structure identification
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- Community Structure in Jazz
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Finding local community structure in networks
- Mixture models and exploratory analysis in networks
- Finding Communities in Linear Time: A Physics Approach
- Robustness of community structure in networks
- Local modularity measure for network clusterizations
- Identifying "communities" within energy landscapes
- Finding instabilities in the community structure of complex networks
- Community Detecting By Signaling on Complex Networks
- Deterministic Modularity Optimization
Cited by in corpus (12)
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Finding and testing network communities by lumped Markov chains
- Detecting Important Nodes to Community Structure Using the Spectrum of the Graph
- How to suppress undesired synchronization
- Link-Prediction Enhanced Consensus Clustering for Complex Networks
- Significant communities in large sparse networks
- Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
- Resampling effects on significance analysis of network clustering and ranking
- Spectral coarse graining for random walk in bipartite networks
- Detecting the optimal number of communities in complex networks
- Detecting Statistically Significant Communities
- How to Measure Significance of Community Structure in Complex Networks