How robust are reconstruction thresholds for community detection?
How robust are reconstruction thresholds for community detection?
复制标题
社区检测的重建阈值有多稳健？
DOI：
10.1145/2897518.2897573
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Alexander S. Wein
中科院分区：
文献类型：
--
作者：
Ankur Moitra;William Perry;Alexander S. Wein
随机分块模型是研究聚类和社区发现的最古老、最普遍的模型之一。在一系列令人兴奋的发展中，在统计物理学深刻但不严格的想法的推动下，Decelle等人。推测了在稀疏制度下何时可能进行群落检测的尖锐阈值。Mossel，Neeman和Sly和Massoulie证明了这一猜想，并给出了匹配算法和下界。在这里，我们从半随机模型的角度重新审视随机区块模型，在该模型中，我们允许对手进行“有益的”改变，以加强每个社区内的联系，并打破它们之间的联系。我们展示了一个令人惊讶的结果，这些“有帮助的”变化可以改变信息论的门槛，使社区发现问题变得更加困难。我们通过展示基于半定规划(已知接近阈值)的算法继续在半随机模型中工作(即使对于部分恢复)来补充这一点。这表明，基于半定规划的算法是健壮的，任何满足信息论阈值的算法都不能做到这一点。这些结果指向了一个有趣的新方向：我们能否找到与统计学中一些经典的平均情况阈值类似的健壮、半随机的阈值？我们还在广播树模型中探讨了这个问题，并证明了半随机模型的观点可以帮助解释为什么一些算法在实践中比其他算法更受欢迎，尽管它们在随机模型上的统计性能存在差距。
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, Decelle et al. conjectured a sharp threshold for when community detection is possible in the sparse regime. Mossel, Neeman and Sly and Massoulie proved the conjecture and gave matching algorithms and lower bounds. Here we revisit the stochastic block model from the perspective of semirandom models where we allow an adversary to make `helpful' changes that strengthen ties within each community and break ties between them. We show a surprising result that these `helpful' changes can shift the information-theoretic threshold, making the community detection problem strictly harder. We complement this by showing that an algorithm based on semidefinite programming (which was known to get close to the threshold) continues to work in the semirandom model (even for partial recovery). This suggests that algorithms based on semidefinite programming are robust in ways that any algorithm meeting the information-theoretic threshold cannot be. These results point to an interesting new direction: Can we find robust, semirandom analogues to some of the classical, average-case thresholds in statistics? We also explore this question in the broadcast tree model, and we show that the viewpoint of semirandom models can help explain why some algorithms are preferred to others in practice, in spite of the gaps in their statistical performance on random models.
DOI：
10.1214/15-aap1145
发表时间：
2013-09
期刊：
--
影响因子：
--
作者：
Elchanan Mossel;Joe Neeman;A. Sly
通讯作者：
Elchanan Mossel;Joe Neeman;A. Sly