Comparing community structure identification

Leon Danon; Albert Díaz-Guilera; Jordi Duch; Alex Arenas

doi:10.1088/1742-5468/2005/09/p09008

journal article Sep 01, 2005

Comparing community structure identification

Leon Danon Albert Díaz-Guilera

Jordi Duch Alex Arenas

Journal of Statistical Mechanics: Theory and Experiment Vol. 2005 No. 09 pp. P09008-P09008 · IOP Publishing

View at Publisher Save 10.1088/1742-5468/2005/09/p09008

Abstract

We compare recent approaches to community structure identification in terms of sensitivity
and computational cost. The recently proposed modularity measure is revisited and the
performance of the methods as applied to ad hoc networks with known community
structure, is compared. We find that the most accurate methods tend to be more
computationally expensive, and that both aspects need to be considered when choosing a
method for practical purposes. The work is intended as an introduction as well
as a proposal for a standard benchmark test of community detection methods.

Topics

No keywords indexed for this article. Browse by subject →

References

45

[1]

Statistical mechanics of complex networks

Réka Albert, Albert-László Barabási

Reviews of Modern Physics 2002 10.1103/revmodphys.74.47

[2]

The Structure and Function of Complex Networks

M. E. J. Newman

SIAM Review 2003 10.1137/s003614450342480

[3]

(2003) 10.1093/acprof:oso/9780198515906.001.0001

[4]

Exploring complex networks

Steven H. Strogatz

Nature 2001 10.1038/35065725

[5]

(2002) 10.1002/3527602755

[6]

(2003) 10.1007/b12331

[7]

Eur. Phys. J. (2004) 10.1140/epjb/e2004-00124-y

[8]

(2003)

[9]

Science (2002) 10.1126/science.1073374

[10]

Nature (2005) 10.1038/nature03288

[11]

Bioinformatics (2003) 10.1093/bioinformatics/btg033

[12]

IEEE Comput. (2002) 10.1109/2.989932

[13]

Proc. Nat. Acad. Sci. (2002) 10.1073/pnas.032093399

[14]

Lecture Notes Comput. Sci. (2004) 10.1007/978-3-540-24688-6_137

[15]

(2004)

[16]

(1979)

[17]

An Efficient Heuristic Procedure for Partitioning Graphs

B. W. Kernighan, S. Lin

Bell System Technical Journal 1970 10.1002/j.1538-7305.1970.tb01770.x

[18]

Czech. Math. J. (1973) 10.21136/cmj.1973.101168

[19]

Phys. Rev. (2001) 10.1103/physreve.64.026114

[20]

SIAM J. Matrix Anal. Appl. (1990) 10.1137/0611030

[21]

Phys. Rev. (2003) 10.1103/physreve.68.065103

[22]

Adv. Complex Syst. (2003) 10.1142/s0219525903001067

[23]

Eur. Phys. J. (2004) 10.1140/epjb/e2004-00130-1

[24]

Phys. Rev. (2004) 10.1103/physreve.69.066133

[25]

Finding and evaluating community structure in networks

M. E. J. Newman, M. Girvan

Physical Review E 2004 10.1103/physreve.69.026113

[26]

Phys. Rev. (2005) 10.1103/physreve.71.046101

[27]

Phys. Rev. (2004) 10.1103/physreve.70.025101

[28]

(2005)

[29]

[30]

[31]

Phys. Rev. (2005) 10.1103/physreve.72.027104

[32]

Community structure in social and biological networks

M. Girvan, M. E. J. Newman

Proceedings of the National Academy of Sciences 2002 10.1073/pnas.122653799

[33]

Phys. Rev. (2004) 10.1103/physreve.70.056104

[34]

Proc. Nat. Acad. Sci. (2004) 10.1073/pnas.0400054101

[35]

J. Stat. Mech. (2004) 10.1088/1742-5468/2004/10/p10012

[36]

(2005)

[37]

(2004)

[38]

Lecture Notes Comput. Sci. (2004) 10.1007/978-3-540-30216-2_15

[39]

Eur. Phys. J. (2004) 10.1140/epjb/e2004-00125-x

[40]

Nature (2005) 10.1038/nature03607

[41]

Phys. Rev. Lett. (2004) 10.1103/physrevlett.93.218701

[42]

(1976)

[43]

J. Stat. Mech. (2005)

[44]

Finding community structure in very large networks

Aaron Clauset, M. E. J. Newman, Cristopher Moore

Physical Review E 2004 10.1103/physreve.70.066111

[45]

(2002)

Cited By

2,099

Collective behavior of blood indicators in lung cancer

Xiong-Fei Jiang, Long Xiong · 2026

Chinese Journal of Physics

Benchmarking overlapping community detection methods for applications in human connectomics

Annie G. Bryant, Aditi Jha · 2026

Network Neuroscience

Multi-Graph Contrastive Learning for Community Detection in Multi-Layer Networks

Songen Cao, Xiaoyi Lv · 2025

IEEE Transactions on Emerging Topic...

Rearranging 'indivisible' blocks for community detection

Peng Gang Sun, Xunlian Wu · 2022

IEEE Transactions on Knowledge and...

VIASCKDE Index: A Novel Internal Cluster Validity Index for Arbitrary-Shaped Clusters Based on the Kernel Density Estimation

Ali Şenol · 2022

Computational Intelligence and Neur...

Evolutionary Multi-Objective Optimization Algorithm for Community Detection in Complex Social Networks

Tanveerulhuq Shaik, Vadlamani Ravi · 2020

SN Computer Science

Accuracy, robustness and scalability of dimensionality reduction methods for single-cell RNA-seq analysis

Shiquan Sun, Jiaqiang Zhu · 2019

Genome Biology

Community Detection in Multi-Layer Networks Using Joint Nonnegative Matrix Factorization

Xiaoke Ma, Di Dong · 2019

IEEE Transactions on Knowledge and...

Hidden community detection in social networks

Kun He, Yingru Li · 2018

Information Sciences

Metrics for Community Analysis

Tanmoy Chakraborty, Ayushi Dalmia · 2017

ACM Computing Surveys

A multi-objective discrete cuckoo search algorithm with local search for community detection in complex networks

Xu Zhou, Yanheng Liu · 2016

Modern Physics Letters B

Modular Brain Networks

Olaf Sporns, Richard F. Betzel · 2016

Annual Review of Psychology

Community detection in social networks

Punam Bedi, Chhavi Sharma · 2016

WIREs Data Mining and Knowledge Dis...

The modular and integrative functional architecture of the human brain

Maxwell A. Bertolero, B. T. Thomas Yeo · 2015

Proceedings of the National Academy...

A Multiobjective Evolutionary Algorithm Based on Similarity for Community Detection From Signed Social Networks

Chenlong Liu, Jing Liu · 2014

IEEE Transactions on Cybernetics

A New Measure of Centrality for Brain Networks

Karen E. Joyce, Paul J. Laurienti · 2010

PLoS ONE

Community detection in networks with positive and negative links

V. A. Traag, Jeroen Bruggeman · 2009

Physical Review E

Complex modular structure of large-scale brain networks

M. Valencia, M. A. Pastor · 2009

Chaos: An Interdisciplinary Journal...

Benchmark graphs for testing community detection algorithms

Andrea Lancichinetti, Santo Fortunato · 2008

Physical Review E

Community detection as an inference problem

M. B. Hastings · 2006

Physical Review E

Metrics

2,099

Citations

45

References

Details

Published: Sep 01, 2005
Vol/Issue: 2005(09)
Pages: P09008-P09008
License: View

Authors

Departament de Física de la Matèria Condensada, Universitat de Barcelona 1 , 08028 Barcelona, Spain; Universitat de Barcelona Institute of Complex Systems (UBICS), Universitat de Barcelona 2 , 08028 Barcelona, Spain

Departament d'Enginyeria Informàtica i Matemàtiques Universität Rovira i Virgili Tarragona 43007 Spain

Cite This Article

Leon Danon, Albert Díaz-Guilera, Jordi Duch, et al. (2005). Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09), P09008-P09008. https://doi.org/10.1088/1742-5468/2005/09/p09008

Comparing community structure identification

You May Also Like