A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
Community detection and orthogonal group synchronization are both fundamental problems with a variety of important applications in science and engineering. In this work, we consider the joint problem of community detection and orthogonal group synchronization which aims to recover the communities and perform synchronization simultaneously. To this end, we propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR). The proposed algorithm is efficient and scales linearly with the number of edges in the graph. We also leverage the recently developed `leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships and stable recovery of the orthogonal transforms. Numerical experiments demonstrate the efficiency and efficacy of our algorithm and confirm our theoretical characterization of it.
Code (1)
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Multiple-View Spectral Clustering for Group-wise Functional Community Detection
Functional connectivity analysis yields powerful insights into our understanding of the human brain. Group-wise functional community detection aims to partition the brain into clusters, or communities, in which functiona…
ClusteringCommunity DetectionFunctional ConnectivityCommunity detection in censored hypergraph
Community detection refers to the problem of clustering the nodes of a network (either graph or hypergrah) into groups. Various algorithms are available for community detection and all these methods apply to uncensored n…
Community DetectionMissing ValuesNear-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods
Group synchronization asks to recover group elements from their pairwise measurements. It has found numerous applications across various scientific disciplines. In this work, we focus on orthogonal and permutation group …
Orthogonal symmetric non-negative matrix factorization under the stochastic block model
We present a method based on the orthogonal symmetric non-negative matrix tri-factorization of the normalized Laplacian matrix for community detection in complex networks. While the exact factorization of a given order m…
ClusteringCommunity DetectionStochastic Block ModelJoint Data and Active User Detection for Grant-free FTN-NOMA in Dynamic Networks
Both faster than Nyquist (FTN) signaling and non-orthogonal multiple access (NOMA) are promising next generation wireless communications techniques as a benefit of their capability of improving the system's spectral effi…