Equivalence between modularity optimization and maximum likelihood methods for community detection

We demonstrate an equivalence between two widely used methods of community detection in networks, the method of modularity maximization and the method of maximum likelihood applied to the degree-corrected stochastic block model. Specifically, we show an exact equivalence between maximization of the generalized modularity that includes a resolution parameter and the special case of the block model known as the planted partition model, in which all communities in a network are assumed to have statistically similar properties. Among other things, this equivalence provides a mathematically principled derivation of the modularity function, clarifies the conditions and assumptions of its use, and gives an explicit formula for the optimal value of the resolution parameter.

Figure 1

Resolution parameter $\gamma$, estimated using the method described here, for a set of synthetic networks with varying numbers of communities. The networks were generated using the standard (non-degree-corrected) planted partition model with $q$ equally sized groups of 250 nodes each and parameters ${\omega }_{\mathrm{in}}$ and ${\omega }_{\mathrm{out}}$ chosen so that each node has an average of 16 connections within its own group and 8 to every other group. Modularity was maximized using simulated annealing with an exponential cooling schedule. The circles represent the estimated values of $\gamma$ and the solid line represents the true values calculated from Eq. (15).