Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
复制标题
DOI：
10.1103/physreve.99.010301
复制
发表时间：
2019-01-17
影响因子：
2.4
通讯作者：
Kabashima, Yoshiyuki
中科院分区：
文献类型：
--
作者：
Kawamoto, Tatsuro;Kabashima, Yoshiyuki
即使在各种更好的形成算法被提出之后，使用贪婪算法的模块化最大化仍然是图中社区检测的流行方法。除了其清晰的机制和易于实现之外，这种方法一直很受欢迎，因为据推测，它的算法失败风险还没有得到很好的理解。这种快速通信提供了深入了解这个问题，估计使用模块化最大化的随机块模型推理的算法性能限制。这是通过在局部更新规则下计算亚稳态的数量来实现的。我们的研究结果提供了一个定量的洞察稀疏的水平，在贪婪算法通常失败。
Modularity maximization using greedy algorithms continues to be a popular approach toward community detection in graphs, even after various better forming algorithms have been proposed. Apart from its clear mechanism and ease of implementation, this approach is persistently popular because, presumably, its risk of algorithmic failure is not well understood. This Rapid Communication provides insight into this issue by estimating the algorithmic performance limit of the stochastic block model inference using modularity maximization. This is achieved by counting the number of metastable states under a local update rule. Our results offer a quantitative insight into the level of sparsity at which a greedy algorithm typically fails.