2022/03/29 by Julia Gaudio, Gaudio, Julia, Miklós Z. Rácz +3 · 2 citations
Computer Science · Physics and Astronomy · #Age of Information Optimization #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Opinion Dynamics and Social Influence #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2203.15736
openalex publication_date 2022/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.