Exact Community Recovery in Correlated Stochastic Block Models
We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Harnessing Multiple Correlated Networks for Exact Community Recovery
We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, R\'acz, and Sridhar…
Graph MatchingCorrelated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models,…
Graph MatchingA Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
We propose and analyze a generic method for community recovery in stochastic block models and degree corrected block models. This approach can exactly recover the hidden communities with high probability when the expecte…
ClusteringExact Matching in Correlated Networks with Node Attributes for Improved Community Recovery
We study community detection in multiple networks whose nodes and edges are jointly correlated. This setting arises naturally in applications such as social platforms, where a shared set of users may exhibit both correla…
AttributeCommunity DetectionGraph MatchingStochastic Block ModelEfficient Graph Matching for Correlated Stochastic Block Models
We study learning problems on correlated stochastic block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. In the most interesting regime where…
Graph Matching