Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method
This work addresses a computational bottleneck in network analysis by providing a faster algorithm for simultaneous community detection and group synchronization, with theoretical guarantees and improved parameter bounds.
The paper tackles the joint problem of community detection and group synchronization by proposing a Generalized Power Method (GPM) that achieves exact recovery in O(n log^2 n) time, significantly outperforming the benchmark semidefinite programming method with O(n^3.5) time.
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(n\log^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.