Modularity of Random Graphs

Abstract: 

An important problem in network analysis is to identify highly connected components or 'communities'. Most popular clustering algorithms work by approximately optimising modularity. Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the maximum modularity q*(G) of G is the maximum of the modularity over all partitions of V(G) and takes a value in the interval [0,1) where larger values indicates a more clustered graph.

Knowledge of the maximum modularity of random graphs helps determine the significance of a division into communities/vertex partition of a real network. We investigate the maximum modularity of Erdós-Rényi random graphs and find there are three different phases of the likely maximum modularity. Concentration of the maximum modularity about its expectation and structural properties of an optimal partition are also established. This is joint work with Prof. Colin McDiarmid.