Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
复制标题
DOI：
10.1103/physreve.78.026112
复制
发表时间：
2008-08-01
影响因子：
2.4
通讯作者：
Caflisch, Amedeo
中科院分区：
文献类型：
--
作者：
Schuetz, Philipp;Caflisch, Amedeo
我们最近引入了用于模块化优化的贪婪算法的多步扩展。该扩展基于这样的想法：在每次迭代时合并 l 对社区 (l > 1) 可防止过早凝聚成少数大型社区。这里，提出了一个用于选择步长 l 的经验公式，该公式为 17 个现实世界和 1100 个计算机生成的网络生成具有（接近）最佳模块化的分区。此外，对两个现实世界网络（大肠杆菌的代谢网络和Martin Karplus合着的论文标题中共同出现的单词图）的社区的深入分析提供了证据，表明多步贪婪算法获得的分区不仅在模块性方面优于原始贪婪算法生成的分区，而且在目标方面也优于原始贪婪算法生成的分区。 标准。换句话说，贪心算法的多步扩展减少了陷入模块化局部最优的危险，并生成更合理的分区。
We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging l pairs of communities (l > 1) at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width l that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity, but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.