Modularity and random graphs

Abstract

This work will appear as a chapter in a forthcoming volume titled `Topics in Probabilistic Graph Theory'. 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 $G$ is the maximum over all vertex-partitions of the modularity score, and satisfies $0\le q^{\ast }(G)<1$. Modularity lies at the heart of the most popular algorithms for community detection. In this chapter we discuss the behaviour of the modularity of various kinds of random graphs, starting with the binomial random graph $G_{n,p}$ with $n$ vertices and edge-probability $p$.

24 pages, 4 figures, 1 table