Community detection algorithms: A comparative analysis
Community detection algorithms: A comparative analysis
复制标题
DOI：
10.1103/physreve.80.056117
复制
发表时间：
2009-11-01
影响因子：
2.4
通讯作者：
Fortunato, Santo
中科院分区：
文献类型：
--
作者：
Lancichinetti, Andrea;Fortunato, Santo
探索真实网络所展示的社区结构是朝着对复杂系统的理解迈出的至关重要的一步。到目前为止，已经提出了许多算法，但是它们都没有经过严格的测试来评估其性能。到目前为止，大多数零星测试都涉及具有已知的社区结构和/或人工图的小型网络，这些网络具有简化的结构，在实际系统中，这并不常见。在这里，我们测试了几种方法，该方法针对最近引入的基准图，其学位和社区规模的分布分布。 Girvan和Newman [Proc。纳特。学院。科学。美国99，7821（2002）]和随机图。由于我们的分析，Rosvall和Bergstrom引入了最近的三种算法[Proc。纳特。学院。科学。美国104，7327（2007）; Proc。纳特。学院。科学。美国105，1118（2008）]，金发[J.统计Mech。：理论经验。 （2008年），P10008]以及Ronhovde和Nussinov [Phys。 Rev. E 80，016109（2009）]具有出色的性能，具有低计算复杂性的其他优势，这使一个人可以分析大型系统。
Uncovering the community structure exhibited by real networks is a crucial step toward an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman [Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)] and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom [Proc. Natl. Acad. Sci. U.S.A. 104, 7327 (2007); Proc. Natl. Acad. Sci. U.S.A. 105, 1118 (2008)], Blondel [J. Stat. Mech.: Theory Exp. (2008), P10008], and Ronhovde and Nussinov [Phys. Rev. E 80, 016109 (2009)] have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.