Linear Programming and Community Detection

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Khajavirad, Aida; Kunisky, Dmitriy
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University; Yale University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1282
• 发表日期: 2023
• 页码: 885-913
• 关键词: Approximation; matrices; graphs

摘要

The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxations of the minimum bisection problem for the same random models. We show that, unlike the SDP relaxation that undergoes a phase transition in the logarithmic average degree regime, the LP relaxation fails in recovering the planted bisection with high probability in this regime. We show that the LP relaxation instead exhibits a transition from recovery to non-recovery in the linear average degree regime. Finally, we present non-recovery conditions for graphs with average degree strictly between linear and logarithmic.