Linear Programming and Community Detection
From MaRDI portal
Publication:6199276
DOI10.1287/MOOR.2022.1282arXiv2006.03213OpenAlexW4287764681WikidataQ114058147 ScholiaQ114058147MaRDI QIDQ6199276
Aida Khajavirad, Dmitriy Kunisky, Alberto Del Pia
Publication date: 23 February 2024
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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 exhibits a transition from recovery to non-recovery in the linear average-degree regime. We show that in the logarithmic average-degree regime, the LP relaxation fails in recovering the planted bisection with high probability.
Full work available at URL: https://arxiv.org/abs/2006.03213
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (1)
This page was built for publication: Linear Programming and Community Detection
