Community Detection in the Stochastic Block Model by Mixed Integer Programming
This work addresses the challenge of ensuring optimal community detection in network analysis, offering an exact solution method that is incremental over existing heuristics.
The authors tackled the problem of community detection in the Degree-Corrected Stochastic Block Model by developing exact mathematical programming methods to find maximum likelihood estimates, which provably converge to the optimum, unlike existing heuristic approaches. They compared these exact methods with classical expectation-maximization heuristics, providing a principled way to measure and compare heuristic performance.
The Degree-Corrected Stochastic Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. The standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE). Current techniques for the MLE problem are heuristics, and therefore do not guarantee convergence to the optimum. We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph. We compare these exact methods with classical heuristic algorithms based on expectation-maximization (EM). The solutions given by exact methods give us a principled way of measuring the experimental performance of classical heuristics and comparing different variations thereof.