Asymptotic distribution of modularity in networks (Q2174525)

Consider a simple, undirected graph with \(n\) vertices, \(m\) edges and adjacency matrix \(\mathbf{A}=(A_{ij})_{n\times n}\). Let vertex \(i\) have degree \(k_i\). Suppose that the vertices of the graph are divided into \(K\) groups. The modularity of this partition is \[ \frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_ik_j}{2m}\right)\delta_{i,j}\,, \] where \(\delta_{i,j}\) is 1 if vertices \(i\) and \(j\) are in the same group, and 0 otherwise. The modularity is one measure of the extent to which vertices in the same group are connected to each other. Suppose that the proportion of vertices in each group is fixed. The authors establish the asymptotic (as \(n\rightarrow\infty\)) normal distribution of the modularity, with explicit mean and variance, under the free labeling, where vertices are assigned to groups via a multinomial distribution with parameters given by the proportion of vertices in each group. This asymptotic normality holds under relatively mild growth conditions on the vertex degrees, which ensure that the variance is not degenerate in the limit. Applications of this result to assessing statistical significance of network partitions are discussed, and numerical examples illustrate both the quality of the normal approximation and applications to real data.