论文标题
相关随机块模型中的确切社区恢复
Exact Community Recovery in Correlated Stochastic Block Models
论文作者
论文摘要
我们考虑从多个相关网络学习潜在社区结构的问题。我们研究了具有两个平衡社区的边缘相关随机块模型，重点是平均程度在顶点数量的对数。我们的主要结果推导了使用多个相关图的精确信息理论阈值进行精确的社区恢复。该阈值捕获了社区恢复与图形匹配任务之间的相互作用。特别是，我们发现并表征了参数空间的一个区域，即使用多个相关图可以进行精确的社区恢复，尽管（1）使用单个图，从理论上讲这是不可能的信息，并且（2）精确的图形匹配在理论上也是不可能的。在这个制度中，我们开发了一种新颖的算法，该算法仔细综合了社区恢复和图形匹配文献中的算法。
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.
