Linear Programming and Community Detection
Linear Programming and Community Detection
复制标题
线性规划和社区检测
DOI：
10.1287/moor.2022.1282
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Dmitriy Kunisky
中科院分区：
文献类型：
--
作者：
Alberto Del Pia;Aida Khajavirad;Dmitriy Kunisky
两个大小相等的社区的社区发现问题与某些随机图模型上的最小图二分问题密切相关。在具有社团结构的网络上的随机块模型分布中，一个著名的半定规划（SDP）松弛的最小二分法问题尽可能地恢复底层社团。出于他们的上级可扩展性，我们研究了相同的随机模型的最小二分法问题的线性规划（LP）松弛的理论性能。我们发现，与SDP松弛，经历了在对数平均度制度的相变，LP松弛未能恢复种植二分在这个政权的概率很高。我们表明，LP松弛，而不是表现出从恢复到nonrecovery的线性平均度制度的过渡。最后，我们给出了平均度严格介于线性和对数之间的图的不可恢复性条件。
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.
影响因子：
3.6
作者：
Boedihardjo, March;Deng, Shaofeng;Strohmer, Thomas
通讯作者：
Strohmer, Thomas
比率切割多面体和 K 均值聚类
影响因子：
3.1
作者：
De Rosa, Antonio;Khajavirad, Aida
通讯作者：
Khajavirad, Aida
通过线性规划进行高效的关节对象匹配
影响因子：
2.7
作者：
De Rosa, Antonio;Khajavirad, Aida
通讯作者：
Khajavirad, Aida