Effects of Null Model Choice on Modularity Maximization

Given a defined set of communities, modularity is computed by comparing each existing edge with its probability of occurrence in a random graph null model. The heuristic has historically garnered a wealth of attention, and many community detection algorithms have been designed around maximizing modularity. Despite this, there are potential issues with the Chung-Lu null graph model that underpins the heuristic. In this manuscript, we explore the output communities given by modularity maximization when this null model is subject to change. We construct two null models using iterated double edge swapping and maximum likelihood estimation, and we use these models as the basis for new modularity-like heuristics we call desmod, and mlemod. We compare the clusters output by standard modularity maximization with those output by our methods on a test suite of LFR benchmark graphs and find that changing the null model consistently increases the normalized mutual information scores when the mixing parameter is high.