Query-Limited Community Recovery in Stochastic Block Models

Researchers have made advancements in community recovery in stochastic block models and community detection in sparse random hypergraphs, proposing new algorithms and strategies to improve exact recovery under limited and noisy access to network data.

A study on exact community recovery in the two-community stochastic block model on $n$ vertices has shown that adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery^[1]. The researchers considered a scenario where the learner may query a noisy neighborhood oracle with a finite query budget, and demonstrated that a two-stage adaptive strategy succeeds with $n+o(n)$ queries in a certain regime. This is an improvement over balanced uniform querying, which requires $m n$ queries for some $m>1$. In a related study, a spectral algorithm was proposed for community detection in sparse random hypergraphs under the non-uniform hypergraph stochastic block model^[2]. The algorithm achieves weak consistency when the signal-to-noise ratio grows slowly as the number of vertices goes to infinity. The algorithm consists of three major steps: hyperedge selection, spectral partition, and correction and merging. The theoretical analysis relies on the concentration and regularization of the adjacency matrix for sparse non-uniform random hypergraphs.