Active Community Detection with Maximal Expected Model Change
This work addresses the challenge of efficiently detecting communities in networks, particularly in sparse or below-threshold scenarios, which is incremental as it builds on existing active learning methods.
The paper tackles the problem of active learning for community detection in networks by proposing a Maximal Expected Model Change (MEMC) algorithm, which selects nodes to query based on their expected impact on the community assignment model, and demonstrates superior performance with super-linear error reduction in sparse and challenging cases compared to baselines.
We present a novel active learning algorithm for community detection on networks. Our proposed algorithm uses a Maximal Expected Model Change (MEMC) criterion for querying network nodes label assignments. MEMC detects nodes that maximally change the community assignment likelihood model following a query. Our method is inspired by detection in the benchmark Stochastic Block Model (SBM), where we provide sample complexity analysis and empirical study with SBM and real network data for binary as well as for the multi-class settings. The analysis also covers the most challenging case of sparse degree and below-detection-threshold SBMs, where we observe a super-linear error reduction. MEMC is shown to be superior to the random selection baseline and other state-of-the-art active learners.