Combinatorial approach to Modularity

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.

8 pages, 4 figures

References in corpus (19)

• Fast unfolding of communities in large networks
• 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
• Resolution limit in community detection
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Modularity and community detection in bipartite networks
• Random graphs with clustering
• Extending the definition of modularity to directed graphs with overlapping communities
• Size reduction of complex networks preserving modularity
• 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
• 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