DOI: 10.1088/1742-5468/2005/09/p09008. Comparing community structure identification

Comparing community structure identification

10.1088/1742-5468/2005/09/p09008

Crossref journal-article

IOP Publishing

Journal of Statistical Mechanics: Theory and Experiment (266)

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.

Bibliography

Danon, L., DÃaz-Guilera, A., Duch, J., & Arenas, A. (2005). Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 2005(09), P09008âP09008.

Authors 4

Leon Danon (first)
Albert Díaz-Guilera (additional)
Jordi Duch (additional)
Alex Arenas (additional)

References 45 Referenced 2,014

10.1103/RevModPhys.74.47 / Rev. Mod. Phys. (2002)
10.1137/S003614450342480 / SIAM Rev. (2003)
10.1093/acprof:oso/9780198515906.001.0001 (2003)
10.1038/35065725 / Nature (2001)
10.1002/3527602755 (2002)
10.1007/b12331 (2003)
10.1140/epjb/e2004-00124-y / Eur. Phys. J. (2004)
{'year': '2003', 'key': '8-1'} (2003)
10.1126/science.1073374 / Science (2002)
10.1038/nature03288 / Nature (2005)
10.1093/bioinformatics/btg033 / Bioinformatics (2003)
10.1109/2.989932 / IEEE Comput. (2002)
10.1073/pnas.032093399 / Proc. Nat. Acad. Sci. (2002)
10.1007/978-3-540-24688-6_137 / Lecture Notes Comput. Sci. (2004)
{'year': '2004', 'key': '15-1'} (2004)
{'year': '1979', 'key': '16-1'} (1979)
10.1002/j.1538-7305.1970.tb01770.x / Bell Syst. Tech. J. (1970)
10.21136/CMJ.1973.101168 / Czech. Math. J. (1973)
10.1103/PhysRevE.64.026114 / Phys. Rev. (2001)
10.1137/0611030 / SIAM J. Matrix Anal. Appl. (1990)
10.1103/PhysRevE.68.065103 / Phys. Rev. (2003)
10.1142/S0219525903001067 / Adv. Complex Syst. (2003)
10.1140/epjb/e2004-00130-1 / Eur. Phys. J. (2004)
10.1103/PhysRevE.69.066133 / Phys. Rev. (2004)
10.1103/PhysRevE.69.026113 / Phys. Rev. (2004)
10.1103/PhysRevE.71.046101 / Phys. Rev. (2005)
10.1103/PhysRevE.70.025101 / Phys. Rev. (2004)
{'year': '2005', 'key': '28-1'} (2005)
{'volume': '2', 'key': '29-1', 'first-page': '1214'}
{'key': '30-1', 'first-page': 'II-128-33'}
10.1103/PhysRevE.72.027104 / Phys. Rev. (2005)
10.1073/pnas.122653799 / Proc. Nat. Acad. Sci. (2002)
10.1103/PhysRevE.70.056104 / Phys. Rev. (2004)
10.1073/pnas.0400054101 / Proc. Nat. Acad. Sci. (2004)
10.1088/1742-5468/2004/10/P10012 / J. Stat. Mech. (2004)
{'year': '2005', 'key': '36-1'} (2005)
{'year': '2004', 'key': '37-1'} (2004)
10.1007/978-3-540-30216-2_15 / Lecture Notes Comput. Sci. (2004)
10.1140/epjb/e2004-00125-x / Eur. Phys. J. (2004)
10.1038/nature03607 / Nature (2005)
10.1103/PhysRevLett.93.218701 / Phys. Rev. Lett. (2004)
{'year': '1976', 'key': '42-1'} (1976)
{'key': '43-1', 'first-page': 'P02001', 'volume': '2005', 'year': '2005', 'journal-title': 'J. Stat. Mech.', 'ISSN': 'https://id.crossref.org/issn/1742-5468', 'issn-type': 'print'} / J. Stat. Mech. (2005)
10.1103/PhysRevE.70.066111 / Phys. Rev. (2004)
{'year': '2002', 'key': '45-1'} (2002)

Dates

Type	When
Created	19 years, 11 months ago (Sept. 26, 2005, 11:13 p.m.)
Deposited	8 months, 3 weeks ago (Dec. 12, 2024, 6:13 a.m.)
Indexed	26 minutes ago (Sept. 3, 2025, 10:16 p.m.)
Issued	20 years ago (Sept. 1, 2005)
Published	20 years ago (Sept. 1, 2005)
Published Online	19 years, 11 months ago (Sept. 26, 2005)
Published Print	20 years ago (Sept. 1, 2005)

Funders 0

None

BibTeX

@article{Danon_2005, title={Comparing community structure identification}, volume={2005}, ISSN={1742-5468}, url={http://dx.doi.org/10.1088/1742-5468/2005/09/p09008}, DOI={10.1088/1742-5468/2005/09/p09008}, number={09}, journal={Journal of Statistical Mechanics: Theory and Experiment}, publisher={IOP Publishing}, author={Danon, Leon and Díaz-Guilera, Albert and Duch, Jordi and Arenas, Alex}, year={2005}, month=sep, pages={P09008–P09008} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        9,
        4
      ]
    ],
    "date-time": "2025-09-04T02:16:06Z",
    "timestamp": 1756952166938,
    "version": "3.30.2"
  },
  "reference-count": 45,
  "publisher": "IOP Publishing",
  "issue": "09",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2005,
            9,
            26
          ]
        ],
        "date-time": "2005-09-26T00:00:00Z",
        "timestamp": 1127692800000
      },
      "content-version": "vor",
      "delay-in-days": 25,
      "URL": "https://iopscience.iop.org/page/copyright"
    },
    {
      "start": {
        "date-parts": [
          [
            2005,
            9,
            26
          ]
        ],
        "date-time": "2005-09-26T00:00:00Z",
        "timestamp": 1127692800000
      },
      "content-version": "tdm",
      "delay-in-days": 25,
      "URL": "https://iopscience.iop.org/info/page/text-and-data-mining"
    }
  ],
  "content-domain": {
    "domain": [
      "iopscience.iop.org"
    ],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2005,
        9,
        1
      ]
    ]
  },
  "abstract": "<jats:p>We compare recent approaches to community structure identification in terms of sensitivity\nand computational cost. The recently proposed modularity measure is revisited and the\nperformance of the methods as applied to <jats:italic>ad hoc</jats:italic> networks with known community\nstructure, is compared. We find that the most accurate methods tend to be more\ncomputationally expensive, and that both aspects need to be considered when choosing a\nmethod for practical purposes. The work is intended as an introduction as well\nas a proposal for a standard benchmark test of community detection methods.</jats:p>",
  "DOI": "10.1088/1742-5468/2005/09/p09008",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2005,
        9,
        27
      ]
    ],
    "date-time": "2005-09-27T03:13:42Z",
    "timestamp": 1127790822000
  },
  "page": "P09008-P09008",
  "update-policy": "https://doi.org/10.1088/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 2014,
  "title": "Comparing community structure identification",
  "prefix": "10.1088",
  "volume": "2005",
  "author": [
    {
      "given": "Leon",
      "family": "Danon",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Albert",
      "family": "D\u00edaz-Guilera",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Jordi",
      "family": "Duch",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Alex",
      "family": "Arenas",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "266",
  "published-online": {
    "date-parts": [
      [
        2005,
        9,
        26
      ]
    ]
  },
  "reference": [
    {
      "key": "1-1",
      "doi-asserted-by": "publisher",
      "first-page": "47",
      "DOI": "10.1103/RevModPhys.74.47",
      "volume": "74",
      "year": "2002",
      "journal-title": "Rev. Mod. Phys.",
      "ISSN": "https://id.crossref.org/issn/0034-6861",
      "issn-type": "print"
    },
    {
      "key": "2-1",
      "doi-asserted-by": "publisher",
      "first-page": "167",
      "DOI": "10.1137/S003614450342480",
      "volume": "45",
      "year": "2003",
      "journal-title": "SIAM Rev.",
      "ISSN": "https://id.crossref.org/issn/0036-1445",
      "issn-type": "print"
    },
    {
      "year": "2003",
      "key": "3-1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/acprof:oso/9780198515906.001.0001"
    },
    {
      "key": "4-1",
      "doi-asserted-by": "publisher",
      "first-page": "268",
      "DOI": "10.1038/35065725",
      "volume": "410",
      "year": "2001",
      "journal-title": "Nature",
      "ISSN": "https://id.crossref.org/issn/0028-0836",
      "issn-type": "print"
    },
    {
      "year": "2002",
      "key": "5-1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/3527602755"
    },
    {
      "year": "2003",
      "key": "6-1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/b12331"
    },
    {
      "key": "7-1",
      "doi-asserted-by": "publisher",
      "first-page": "321",
      "DOI": "10.1140/epjb/e2004-00124-y",
      "volume": "38",
      "year": "2004",
      "journal-title": "Eur. Phys. J.",
      "ISSN": "https://id.crossref.org/issn/1434-6028",
      "issn-type": "print"
    },
    {
      "year": "2003",
      "key": "8-1"
    },
    {
      "key": "9-1",
      "doi-asserted-by": "publisher",
      "first-page": "1551",
      "DOI": "10.1126/science.1073374",
      "volume": "297",
      "year": "2002",
      "journal-title": "Science",
      "ISSN": "https://id.crossref.org/issn/0036-8075",
      "issn-type": "print"
    },
    {
      "key": "10-1",
      "doi-asserted-by": "publisher",
      "first-page": "895",
      "DOI": "10.1038/nature03288",
      "volume": "433",
      "year": "2005",
      "journal-title": "Nature",
      "ISSN": "https://id.crossref.org/issn/0028-0836",
      "issn-type": "print"
    },
    {
      "key": "11-1",
      "doi-asserted-by": "publisher",
      "first-page": "532",
      "DOI": "10.1093/bioinformatics/btg033",
      "volume": "19",
      "year": "2003",
      "journal-title": "Bioinformatics",
      "ISSN": "https://id.crossref.org/issn/1367-4803",
      "issn-type": "print"
    },
    {
      "key": "12-1",
      "doi-asserted-by": "publisher",
      "first-page": "66",
      "DOI": "10.1109/2.989932",
      "volume": "35",
      "year": "2002",
      "journal-title": "IEEE Comput."
    },
    {
      "key": "13-1",
      "doi-asserted-by": "publisher",
      "first-page": "5825",
      "DOI": "10.1073/pnas.032093399",
      "volume": "99",
      "year": "2002",
      "journal-title": "Proc. Nat. Acad. Sci.",
      "ISSN": "https://id.crossref.org/issn/0027-8424",
      "issn-type": "print"
    },
    {
      "key": "14-1",
      "doi-asserted-by": "publisher",
      "first-page": "1062",
      "DOI": "10.1007/978-3-540-24688-6_137",
      "volume": "3038",
      "year": "2004",
      "journal-title": "Lecture Notes Comput. Sci.",
      "ISSN": "https://id.crossref.org/issn/1611-3349",
      "issn-type": "print"
    },
    {
      "year": "2004",
      "key": "15-1"
    },
    {
      "year": "1979",
      "key": "16-1"
    },
    {
      "key": "17-1",
      "doi-asserted-by": "publisher",
      "first-page": "291",
      "DOI": "10.1002/j.1538-7305.1970.tb01770.x",
      "volume": "49",
      "year": "1970",
      "journal-title": "Bell Syst. Tech. J.",
      "ISSN": "https://id.crossref.org/issn/0005-8580",
      "issn-type": "print"
    },
    {
      "key": "18-1",
      "doi-asserted-by": "publisher",
      "first-page": "298",
      "DOI": "10.21136/CMJ.1973.101168",
      "volume": "23",
      "year": "1973",
      "journal-title": "Czech. Math. J.",
      "ISSN": "https://id.crossref.org/issn/0011-4642",
      "issn-type": "print"
    },
    {
      "key": "19-1",
      "doi-asserted-by": "publisher",
      "first-page": "026114",
      "DOI": "10.1103/PhysRevE.64.026114",
      "volume": "64",
      "year": "2001",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "20-1",
      "doi-asserted-by": "publisher",
      "first-page": "430",
      "DOI": "10.1137/0611030",
      "volume": "11",
      "year": "1990",
      "journal-title": "SIAM J. Matrix Anal. Appl.",
      "ISSN": "https://id.crossref.org/issn/0895-4798",
      "issn-type": "print"
    },
    {
      "key": "21-1",
      "doi-asserted-by": "publisher",
      "first-page": "065103",
      "DOI": "10.1103/PhysRevE.68.065103",
      "volume": "68",
      "year": "2003",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "22-1",
      "doi-asserted-by": "publisher",
      "first-page": "565",
      "DOI": "10.1142/S0219525903001067",
      "volume": "6",
      "year": "2003",
      "journal-title": "Adv. Complex Syst.",
      "ISSN": "https://id.crossref.org/issn/0219-5259",
      "issn-type": "print"
    },
    {
      "key": "23-1",
      "doi-asserted-by": "publisher",
      "first-page": "373",
      "DOI": "10.1140/epjb/e2004-00130-1",
      "volume": "38",
      "year": "2004",
      "journal-title": "Eur. Phys. J.",
      "ISSN": "https://id.crossref.org/issn/1434-6028",
      "issn-type": "print"
    },
    {
      "key": "24-1",
      "doi-asserted-by": "publisher",
      "first-page": "066133",
      "DOI": "10.1103/PhysRevE.69.066133",
      "volume": "69",
      "year": "2004",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "25-1",
      "doi-asserted-by": "publisher",
      "first-page": "026113",
      "DOI": "10.1103/PhysRevE.69.026113",
      "volume": "69",
      "year": "2004",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "26-1",
      "doi-asserted-by": "publisher",
      "first-page": "046101",
      "DOI": "10.1103/PhysRevE.71.046101",
      "volume": "71",
      "year": "2005",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "27-1",
      "doi-asserted-by": "publisher",
      "first-page": "025101",
      "DOI": "10.1103/PhysRevE.70.025101",
      "volume": "70",
      "year": "2004",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "year": "2005",
      "key": "28-1"
    },
    {
      "volume": "2",
      "key": "29-1",
      "first-page": "1214"
    },
    {
      "key": "30-1",
      "first-page": "II-128-33"
    },
    {
      "key": "31-1",
      "doi-asserted-by": "publisher",
      "first-page": "027104",
      "DOI": "10.1103/PhysRevE.72.027104",
      "volume": "72",
      "year": "2005",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "32-1",
      "doi-asserted-by": "publisher",
      "first-page": "7821",
      "DOI": "10.1073/pnas.122653799",
      "volume": "99",
      "year": "2002",
      "journal-title": "Proc. Nat. Acad. Sci.",
      "ISSN": "https://id.crossref.org/issn/0027-8424",
      "issn-type": "print"
    },
    {
      "key": "33-1",
      "doi-asserted-by": "publisher",
      "first-page": "056104",
      "DOI": "10.1103/PhysRevE.70.056104",
      "volume": "70",
      "year": "2004",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "key": "34-1",
      "doi-asserted-by": "publisher",
      "first-page": "2658",
      "DOI": "10.1073/pnas.0400054101",
      "volume": "101",
      "year": "2004",
      "journal-title": "Proc. Nat. Acad. Sci.",
      "ISSN": "https://id.crossref.org/issn/0027-8424",
      "issn-type": "print"
    },
    {
      "key": "35-1",
      "doi-asserted-by": "crossref",
      "first-page": "P10012",
      "DOI": "10.1088/1742-5468/2004/10/P10012",
      "volume": "2004",
      "year": "2004",
      "journal-title": "J. Stat. Mech.",
      "ISSN": "https://id.crossref.org/issn/1742-5468",
      "issn-type": "print"
    },
    {
      "year": "2005",
      "key": "36-1"
    },
    {
      "year": "2004",
      "key": "37-1"
    },
    {
      "key": "38-1",
      "doi-asserted-by": "publisher",
      "first-page": "181",
      "DOI": "10.1007/978-3-540-30216-2_15",
      "volume": "3243",
      "year": "2004",
      "journal-title": "Lecture Notes Comput. Sci.",
      "ISSN": "https://id.crossref.org/issn/1611-3349",
      "issn-type": "print"
    },
    {
      "key": "39-1",
      "doi-asserted-by": "publisher",
      "first-page": "331",
      "DOI": "10.1140/epjb/e2004-00125-x",
      "volume": "38",
      "year": "2004",
      "journal-title": "Eur. Phys. J.",
      "ISSN": "https://id.crossref.org/issn/1434-6028",
      "issn-type": "print"
    },
    {
      "key": "40-1",
      "doi-asserted-by": "publisher",
      "first-page": "814",
      "DOI": "10.1038/nature03607",
      "volume": "435",
      "year": "2005",
      "journal-title": "Nature",
      "ISSN": "https://id.crossref.org/issn/0028-0836",
      "issn-type": "print"
    },
    {
      "key": "41-1",
      "doi-asserted-by": "publisher",
      "first-page": "218701",
      "DOI": "10.1103/PhysRevLett.93.218701",
      "volume": "93",
      "year": "2004",
      "journal-title": "Phys. Rev. Lett.",
      "ISSN": "https://id.crossref.org/issn/0031-9007",
      "issn-type": "print"
    },
    {
      "year": "1976",
      "key": "42-1"
    },
    {
      "key": "43-1",
      "first-page": "P02001",
      "volume": "2005",
      "year": "2005",
      "journal-title": "J. Stat. Mech.",
      "ISSN": "https://id.crossref.org/issn/1742-5468",
      "issn-type": "print"
    },
    {
      "key": "44-1",
      "doi-asserted-by": "publisher",
      "first-page": "066111",
      "DOI": "10.1103/PhysRevE.70.066111",
      "volume": "70",
      "year": "2004",
      "journal-title": "Phys. Rev.",
      "ISSN": "https://id.crossref.org/issn/1063-651X",
      "issn-type": "print"
    },
    {
      "year": "2002",
      "key": "45-1"
    }
  ],
  "container-title": "Journal of Statistical Mechanics: Theory and Experiment",
  "original-title": [],
  "link": [
    {
      "URL": "https://iopscience.iop.org/article/10.1088/1742-5468/2005/09/P09008",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://iopscience.iop.org/article/10.1088/1742-5468/2005/09/P09008/pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://iopscience.iop.org/article/10.1088/1742-5468/2005/09/P09008/pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "syndication"
    },
    {
      "URL": "https://iopscience.iop.org/article/10.1088/1742-5468/2005/09/P09008/pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        12,
        12
      ]
    ],
    "date-time": "2024-12-12T11:13:54Z",
    "timestamp": 1734002034000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://iopscience.iop.org/article/10.1088/1742-5468/2005/09/P09008"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2005,
        9,
        1
      ]
    ]
  },
  "references-count": 45,
  "journal-issue": {
    "issue": "09",
    "published-online": {
      "date-parts": [
        [
          2005,
          9,
          26
        ]
      ]
    },
    "published-print": {
      "date-parts": [
        [
          2005,
          9,
          1
        ]
      ]
    }
  },
  "URL": "http://dx.doi.org/10.1088/1742-5468/2005/09/P09008",
  "relation": {},
  "ISSN": [
    "1742-5468"
  ],
  "subject": [],
  "container-title-short": "J. Stat. Mech.",
  "published": {
    "date-parts": [
      [
        2005,
        9,
        1
      ]
    ]
  },
  "assertion": [
    {
      "value": "Comparing community structure identification",
      "name": "article_title",
      "label": "Article Title"
    },
    {
      "value": "Journal of Statistical Mechanics: Theory and Experiment",
      "name": "journal_title",
      "label": "Journal Title"
    },
    {
      "value": "paper",
      "name": "article_type",
      "label": "Article Type"
    },
    {
      "value": "IOP Publishing Ltd",
      "name": "copyright_information",
      "label": "Copyright Information"
    },
    {
      "value": "2005-08-15",
      "name": "date_received",
      "label": "Date Received",
      "group": {
        "name": "publication_dates",
        "label": "Publication dates"
      }
    },
    {
      "value": "2005-09-05",
      "name": "date_accepted",
      "label": "Date Accepted",
      "group": {
        "name": "publication_dates",
        "label": "Publication dates"
      }
    },
    {
      "value": "2005-09-26",
      "name": "date_epub",
      "label": "Online publication date",
      "group": {
        "name": "publication_dates",
        "label": "Publication dates"
      }
    }
  ]
}