论文标题
线性编程和社区检测
Linear Programming and Community Detection
论文作者
论文摘要
两个等式社区的社区检测问题与某些随机图模型的最小图一分解问题密切相关。在具有社区结构的网络上的随机块模型分布中，众所周知的半决赛编程（SDP）放松最小分配问题会尽可能恢复基础社区。在其出色的可伸缩性的推动下，我们研究了相同随机模型的最小一分解问题线性编程（LP）放松的理论性能。我们表明，与对数平均度方案中经历相变的SDP松弛不同，LP弛豫表现出从线性平均度方案中从恢复到未恢复的过渡。我们表明，在对数平均度度方案中，LP弛豫未能以很高的概率恢复种植的一分化。
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.
