# Modularity of ErdHos-R'enyi random graphs

arXiv: https://arxiv.org/abs/1808.02243 · HTML: https://mlsanity.com/paper/1808.02243/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2018.

## Built on by (most cited first, 2 of 2)

- [Modularity of the ABCD Random Graph Model with Community Structure](https://mlsanity.com/paper/2203.01480/) (2022)
- [Stochastic Sequential Decision Making over Expanding Networks with Graph Filtering](https://mlsanity.com/paper/2603.19501/) (2026)

## Abstract (arXiv)

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^*(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0≤ q^*(G) < 1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the ErdHos-R'enyi random graph Gn,p with n vertices and edge-probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)-1/2 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.