Linear Programming and Community Detection

作     者：Del Pia, Alberto Khajavirad, Aida Kunisky, Dmitriy 

作者机构：Univ Wisconsin Dept Ind & Syst Engn Madison WI 53715 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53715 USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA 

出 版 物：《MATHEMATICS OF OPERATIONS RESEARCH》 (运筹学数学)

年 卷 期：2023年第48卷第2期

页      面：885-913页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Office of Naval Research (ONR) [N00014-19-1-2322] ONR [N00014-20-1-2335] Simons Investigator Award National Science Foundation [DMS-1712730, DMS-1719545] 

主　　题：community detection minimum bisection problem linear programming metric polytope 

摘      要：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.