Community detection algorithms: A comparative analysis

Community detection algorithms: A comparative analysis. Lancichinetti, A. & Fortunato, S. Physical Review E, 80(5):056117, 2009.

Paper doi abstract bibtex

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 et al. [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.

@article{lancichinetti_community_2009,
	title = {Community detection algorithms: {A} comparative analysis},
	volume = {80},
	shorttitle = {Community detection algorithms},
	url = {http://link.aps.org/doi/10.1103/PhysRevE.80.056117},
	doi = {10.1103/PhysRevE.80.056117},
	abstract = {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 et al. [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.},
	number = {5},
	urldate = {2016-12-15},
	journal = {Physical Review E},
	author = {Lancichinetti, Andrea and Fortunato, Santo},
	year = {2009},
	keywords = {社区探测算法, 社区探测算法综述, 🌟高质量期刊},
	pages = {056117},
}

Downloads: 0

{"_id":"zT7y73RAhgNizCMjz","bibbaseid":"lancichinetti-fortunato-communitydetectionalgorithmsacomparativeanalysis-2009","author_short":["Lancichinetti, A.","Fortunato, S."],"bibdata":{"bibtype":"article","type":"article","title":"Community detection algorithms: A comparative analysis","volume":"80","shorttitle":"Community detection algorithms","url":"http://link.aps.org/doi/10.1103/PhysRevE.80.056117","doi":"10.1103/PhysRevE.80.056117","abstract":"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 et al. [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.","number":"5","urldate":"2016-12-15","journal":"Physical Review E","author":[{"propositions":[],"lastnames":["Lancichinetti"],"firstnames":["Andrea"],"suffixes":[]},{"propositions":[],"lastnames":["Fortunato"],"firstnames":["Santo"],"suffixes":[]}],"year":"2009","keywords":"社区探测算法, 社区探测算法综述, 🌟高质量期刊","pages":"056117","bibtex":"@article{lancichinetti_community_2009,\n\ttitle = {Community detection algorithms: {A} comparative analysis},\n\tvolume = {80},\n\tshorttitle = {Community detection algorithms},\n\turl = {http://link.aps.org/doi/10.1103/PhysRevE.80.056117},\n\tdoi = {10.1103/PhysRevE.80.056117},\n\tabstract = {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 et al. [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.},\n\tnumber = {5},\n\turldate = {2016-12-15},\n\tjournal = {Physical Review E},\n\tauthor = {Lancichinetti, Andrea and Fortunato, Santo},\n\tyear = {2009},\n\tkeywords = {社区探测算法, 社区探测算法综述, 🌟高质量期刊},\n\tpages = {056117},\n}\n\n","author_short":["Lancichinetti, A.","Fortunato, S."],"key":"lancichinetti_community_2009","id":"lancichinetti_community_2009","bibbaseid":"lancichinetti-fortunato-communitydetectionalgorithmsacomparativeanalysis-2009","role":"author","urls":{"Paper":"http://link.aps.org/doi/10.1103/PhysRevE.80.056117"},"keyword":["社区探测算法","社区探测算法综述","🌟高质量期刊"],"metadata":{"authorlinks":{}},"html":""},"bibtype":"article","biburl":"https://bibbase.org/zotero/wybert","dataSources":["TJkbwzD8s2wCxBy6Y"],"keywords":["社区探测算法","社区探测算法综述","🌟高质量期刊"],"search_terms":["community","detection","algorithms","comparative","analysis","lancichinetti","fortunato"],"title":"Community detection algorithms: A comparative analysis","year":2009}