Modularity of Erdős-Rényi random graphs
arXiv:1808.02243 · doi:10.1002/rsa.20910
Abstract
For a given graph , each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in . The modularity of the graph is defined to be the maximum over all vertex partitions of the modularity score, and satisfies . Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erdős-Rényi random graph with vertices and edge-probability . Two key findings are that the modularity is with high probability (whp) for up to and no further; and when and is bounded below 1, it has order whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.
arXiv comment35 pages, to appear in Random Structures and Algorithms
References in corpus (15)
- Finding and evaluating community structure in networks
- Community detection in graphs
- Resolution limit in community detection
- Community structure in directed networks
- Hyperbolic Geometry of Complex Networks
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Limits of modularity maximization in community detection
- Module identification in bipartite and directed networks
- When are networks truly modular?
- Clustering via Hypergraph Modularity
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Information-theoretic thresholds for community detection in sparse networks
- Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
- Degree sequences of random digraphs and bipartite graphs
- The parameterised complexity of computing the maximum modularity of a graph