Recovering a Hidden Community Beyond the Spectral Limit in O(|E| ^*|V|) Time
share
Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n^1-o(1)≤ K ≤ o(n). It is shown that such recovery is attainable by a belief propagation algorithm running for ^∗ n+O(1) iterations, if λ =K^2(p-q)^2/((n-K)q), the signal-to-noise ratio, exceeds 1/e, with the total time complexity O(|E| ^*n). Conversely, if λ≤ 1/e, no local algorithm can asymptotically outperform trivial random guessing. By analyzing a linear message-passing algorithm that corresponds to applying power iteration to the non-backtracking matrix of the graph, we provide evidence to suggest that spectral methods fail to recovery the community if λ≤ 1. In addition, the belief propagation algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K >n/ n( ρ_ BP +o(1) ), where ρ_ BP is a function of p/q.
READ FULL TEXT