Modularity of Erdős-Rényi random graphs

Abstract

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^{\ast }(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0\le q^{\ast }(G)<1$. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd\H{o}s-R\'enyi random graph $G_{n,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\ge 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.