Combinatorial approach to Modularity
arXiv:1004.5283 · doi:10.1103/PhysRevE.82.026102
Abstract
Communities are clusters of nodes with a higher than average density of internal connections. Their detection is of great relevance to better understand the structure and hierarchies present in a network. Modularity has become a standard tool in the area of community detection, providing at the same time a way to evaluate partitions and, by maximizing it, a method to find communities. In this work, we study the modularity from a combinatorial point of view. Our analysis (as the modularity definition) relies on the use of the configurational model, a technique that given a graph produces a series of randomized copies keeping the degree sequence invariant. We develop an approach that enumerates the null model partitions and can be used to calculate the probability distribution function of the modularity. Our theory allows for a deep inquiry of several interesting features characterizing modularity such as its resolution limit and the statistics of the partitions that maximize it. Additionally, the study of the probability of extremes of the modularity in the random graph partitions opens the way for a definition of the statistical significance of network partitions.
arXiv comment8 pages, 4 figures
References in corpus (37)
- Fast unfolding of communities in large networks
- 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 very large networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Assortative mixing in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Functional cartography of complex metabolic networks
- Resolution limit in community detection
- Defining and identifying communities in networks
- Community detection in complex networks using Extremal Optimization
- Community structure in directed networks
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Synchronization reveals topological scales in complex networks
- Modularity and community detection in bipartite networks
- Generation of uncorrelated random scale-free networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Random graphs with clustering
- Module identification in bipartite and directed networks
- Extending the definition of modularity to directed graphs with overlapping communities
- Size reduction of complex networks preserving modularity
- Cut-offs and finite size effects in scale-free networks
- Distance, dissimilarity index, and network community structure
- Limited resolution in complex network community detection with Potts model approach
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Identifying "communities" within energy landscapes
- Improved community structure detection using a modified fine tuning strategy
- Statistical significance of communities in networks
- Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
- Effect of size heterogeneity on community identification in complex networks
Cited by in corpus (9)
- Finding statistically significant communities in networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Entropy of stochastic blockmodel ensembles
- Generalised hypergeometric ensembles of random graphs: the configuration model as an urn problem
- The stability to instability transition in the structure of large scale networks
- Detecting the optimal number of communities in complex networks
- Detecting Statistically Significant Communities
- Intrinsically Dynamic Network Communities
- Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences