Semidefinite programming recovers many communities in large networks
Tightness and Error Exponents of SDP with Logarithmically Many Communities
Information Theory
Summary
This paper looks at a mathematical technique called semidefinite programming (SDP) used to find groups, or communities, in large networks where the number of groups grows slowly with the network size. The authors study the exact conditions when this technique can perfectly recover the communities and how the error behaves when it does not fully succeed. They also show that a simple procedure combining one SDP solve with additional steps can correctly find the communities even in challenging settings. This advances understanding of when and how SDP methods work for clustering many communities.
What this means in practice
- •For network analysts: Identify large numbers of groups in complex networks using a precise and efficient mathematical approach even as group counts grow logarithmically.
- •For data clustering engineers: Use a single semidefinite program solve plus explicit rounding to accurately cluster many communities when community counts grow slowly with data size.
A theory result. No direct application yet.
Authors
Shengtao Guo, Ethan X. Fang, Junwei Lu
Abstract
We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\toγ>0$, with edge probabilities $α\log m/m$ within communities and $β\log m/m$ across them, for fixed $α>β>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.