Linear Programming and Community Detection

Alberto Del Pia (), Aida Khajavirad () and Dmitriy Kunisky ()
Additional contact information
Alberto Del Pia: Department of Industrial and Systems Engineering & Wisconsin Institute for Discovery, University of Wisconsin–Madison, Madison, Wisconsin 53715
Aida Khajavirad: Department of Industrial & Systems Engineering, Lehigh University, Bethlehem, Pennsylvania 18015
Dmitriy Kunisky: Department of Computer Science, Yale University, New Haven, Connecticut 06520

Mathematics of Operations Research, 2023, vol. 48, issue 2, 885-913

Abstract: 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 nonrecovery in the linear average degree regime. Finally, we present nonrecovery conditions for graphs with average degree strictly between linear and logarithmic.

Keywords: Primary: 90C05; 90C57; 90C35; 68Q87; community detection; minimum bisection problem; linear programming; metric polytope (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1282 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:885-913

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().