Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method
Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method
复制标题
基于广义幂法的非凸联合社区检测和组同步
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. M. So
中科院分区：
文献类型：
--
作者：
Sijin Chen;Xiwei Cheng;A. M. So
本文提出了一种广义功率方法（GPM），以直接的非凸方式同时解决社区检测和组同步问题。在随机群块模型（SGBM）下，理论分析表明，该算法能够在O（nlog^2n）$时间内精确地恢复地面真实值，大大优于半定规划（SDP）的基准方法，其时间复杂度为O（n^{3.5}）$.此外，参数的下限给出了精确恢复GPM的必要条件。新的界限突破了信息理论的纯社区检测随机块模型（SBM）下的阈值，从而证明了我们的同时优化算法的优越性，平凡的两阶段的方法，连续执行这两项任务。我们还对GPM和SDP进行了数值实验，以证明和补充我们的理论分析。
This paper proposes a Generalized Power Method (GPM) to tackle the problem of community detection and group synchronization simultaneously in a direct non-convex manner. Under the stochastic group block model (SGBM), theoretical analysis indicates that the algorithm is able to exactly recover the ground truth in $O(nlog^2n)$ time, sharply outperforming the benchmark method of semidefinite programming (SDP) in $O(n^{3.5})$ time. Moreover, a lower bound of parameters is given as a necessary condition for exact recovery of GPM. The new bound breaches the information-theoretic threshold for pure community detection under the stochastic block model (SBM), thus demonstrating the superiority of our simultaneous optimization algorithm over the trivial two-stage method which performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to evidence and complement our theoretical analysis.
影响因子：
2.5
作者：
Singer, A.
通讯作者：
Singer, A.