论文标题
精确的社区恢复超过签名图
Exact Community Recovery over Signed Graphs
论文作者
论文摘要
签名图编码具有正边和负边缘的不同实体之间的相似性和差异关系。在本文中，我们研究了由签名的随机块模型（SSBM）与两个等级社区产生的签名图的社区恢复问题。我们的方法基于SSBM的最大似然估计（MLE）。与许多现有的方法不同，我们的表述表明，签名图的正和负边缘应不平等地对待。然后，我们提出了一种简单的两阶段迭代算法，用于求解正则化MLE。结果表明，在对数程度制度中，所提出的算法可以在几乎线上以信息理论限制在几乎线性的时间内恢复基础社区。据报道，综合数据和真实数据的数值结果均可验证和补充我们的理论发展，并证明了该方法的疗效。
Signed graphs encode similarity and dissimilarity relationships among different entities with positive and negative edges. In this paper, we study the problem of community recovery over signed graphs generated by the signed stochastic block model (SSBM) with two equal-sized communities. Our approach is based on the maximum likelihood estimation (MLE) of the SSBM. Unlike many existing approaches, our formulation reveals that the positive and negative edges of a signed graph should be treated unequally. We then propose a simple two-stage iterative algorithm for solving the regularized MLE. It is shown that in the logarithmic degree regime, the proposed algorithm can exactly recover the underlying communities in nearly-linear time at the information-theoretic limit. Numerical results on both synthetic and real data are reported to validate and complement our theoretical developments and demonstrate the efficacy of the proposed method.
