Linear Programming and Community Detection

DOI10.1287/MOOR.2022.1282MaRDI QIDQ6199276zbMATH OpenOpenAlexWikidataFDO

Authors Alberto Del Pia, Aida Khajavirad, Dmitriy Kunisky

Publication date 23 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.03213

zbMATH Keywords

community detectionlinear programmingmetric polytopeminimum bisection problem

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Linear programming (90C05) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

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.

Recommendations

• Semidefinite programs on sparse random graphs and their application to community detection
• How well do local algorithms solve semidefinite programs?
• Community structures of networks

Cited in

(1)

• Efficient joint object matching via linear programming

This page was built for publication: Linear Programming and Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199276)