Title: Active Community Detection: A Maximum Likelihood Approach,
Abstract: We propose novel semi-supervised and active learning algorithms for the
problem of community detection on networks. The algorithms are based on
optimizing the likelihood function of the community assignments given a graph
and an estimate of the statistical model that generated it. The optimization
framework is inspired by prior work on the unsupervised community detection
problem in Stochastic Block Models (SBM) using Semi-Definite Programming (SDP).
In this paper we provide the next steps in the evolution of learning
communities in this context which involves a constrained semi-definite
programming algorithm, and a newly presented active learning algorithm. The
active learner intelligently queries nodes that are expected to maximize the
change in the model likelihood. Experimental results show that this active
learning algorithm outperforms the random-selection semi-supervised version of
the same algorithm as well as other state-of-the-art active learning
algorithms. Our algorithms significantly improved performance is demonstrated
on both real-world and SBM-generated networks even when the SBM has a signal to
noise ratio (SNR) below the known unsupervised detectability threshold.