DOI: 10.1073/pnas.0601602103. Modularity and community structure in networks

Modularity and community structure in networks

10.1073/pnas.0601602103

Crossref journal-article

Proceedings of the National Academy of Sciences

Proceedings of the National Academy of Sciences (341)

Abstract

Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.

Bibliography

Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577â8582.

Authors 1

M. E. J. Newman (first)

References 32 Referenced 9,211

10.1038/30918
10.1126/science.286.5439.509
10.1126/science.298.5594.824
10.1103/RevModPhys.74.47
10.1080/00018730110112519
10.1137/S003614450342480
10.1140/epjb/e2004-00124-y
10.1088/1742-5468/2005/09/P09008
10.1109/2.989932
10.1073/pnas.122653799
10.1093/bioinformatics/btg033
10.1038/nature03288
U. Elsner Graph Partitioning: A Survey (Technische Universität Chemnitz, Chemnitz, Germany, Technical Report 97-27. (1997). / Graph Partitioning: A Survey by Elsner U. (1997)
P.-O. Fjällström Linköping Electronic Articles in Computer and Information Science Vol. 3 Available at www.ep.liu.se/ea/cis/1998/006. Accessed May 10 2006. (1998).
10.1086/226141
10.1017/CBO9780511815478
10.1103/PhysRevE.69.026113
10.1103/PhysRevE.69.066133
10.1103/PhysRevE.72.027104
F. R. K. Chung (Am. Math. Soc. Providence RI no. 92. (1997).
10.21136/CMJ.1973.101168
10.1137/0611030
10.1086/jar.33.4.3629752
10.1073/pnas.0400054101
10.1002/j.1538-7305.1970.tb01770.x
10.1103/PhysRevE.70.066111
10.1142/S0219525903001067
10.1038/35036627
10.1103/PhysRevE.68.065103
X. Guardiola R. Guimerà A. Arenas A. Diaz-Guilera D. Streib L. A. N. Amaral e-Print Archive http://xxx.lanl.gov/abs/cond-mat/0206240. (2002).
10.1073/pnas.98.2.404
S. White P. Smyth eds H. Kargupta J. Srivastava C. Kamath A. Goodman (Society for Industrial and Applied Mathematics Philadelphia) pp. 274–285 (2005). (10.1137/1.9781611972757.25)

Dates

Type	When
Created	19 years, 3 months ago (May 24, 2006, 8:36 p.m.)
Deposited	7 months, 4 weeks ago (Jan. 8, 2025, 9:01 p.m.)
Indexed	7 minutes ago (Sept. 6, 2025, 7:36 a.m.)
Issued	19 years, 3 months ago (June 6, 2006)
Published	19 years, 3 months ago (June 6, 2006)
Published Online	19 years, 3 months ago (June 6, 2006)
Published Print	19 years, 3 months ago (June 6, 2006)

Funders 0

None

BibTeX

@article{Newman_2006, title={Modularity and community structure in networks}, volume={103}, ISSN={1091-6490}, url={http://dx.doi.org/10.1073/pnas.0601602103}, DOI={10.1073/pnas.0601602103}, number={23}, journal={Proceedings of the National Academy of Sciences}, publisher={Proceedings of the National Academy of Sciences}, author={Newman, M. E. J.}, year={2006}, month=jun, pages={8577–8582} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        9,
        6
      ]
    ],
    "date-time": "2025-09-06T11:36:05Z",
    "timestamp": 1757158565647,
    "version": "3.32.0"
  },
  "reference-count": 32,
  "publisher": "Proceedings of the National Academy of Sciences",
  "issue": "23",
  "content-domain": {
    "domain": [
      "www.pnas.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2006,
        6,
        6
      ]
    ]
  },
  "abstract": "<jats:p>Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as \u201cmodularity\u201d over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.</jats:p>",
  "DOI": "10.1073/pnas.0601602103",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2006,
        5,
        25
      ]
    ],
    "date-time": "2006-05-25T00:36:00Z",
    "timestamp": 1148517360000
  },
  "page": "8577-8582",
  "update-policy": "https://doi.org/10.1073/pnas.cm10313",
  "source": "Crossref",
  "is-referenced-by-count": 9211,
  "title": "Modularity and community structure in networks",
  "prefix": "10.1073",
  "volume": "103",
  "author": [
    {
      "given": "M. E. J.",
      "family": "Newman",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109"
        }
      ]
    }
  ],
  "member": "341",
  "published-online": {
    "date-parts": [
      [
        2006,
        6,
        6
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_3_3_1_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/30918"
    },
    {
      "key": "e_1_3_3_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.286.5439.509"
    },
    {
      "key": "e_1_3_3_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.298.5594.824"
    },
    {
      "key": "e_1_3_3_4_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.74.47"
    },
    {
      "key": "e_1_3_3_5_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/00018730110112519"
    },
    {
      "key": "e_1_3_3_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/S003614450342480"
    },
    {
      "key": "e_1_3_3_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1140/epjb/e2004-00124-y"
    },
    {
      "key": "e_1_3_3_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/1742-5468/2005/09/P09008"
    },
    {
      "key": "e_1_3_3_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/2.989932"
    },
    {
      "key": "e_1_3_3_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.122653799"
    },
    {
      "key": "e_1_3_3_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/bioinformatics/btg033"
    },
    {
      "key": "e_1_3_3_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/nature03288"
    },
    {
      "key": "e_1_3_3_13_2",
      "volume-title": "Graph Partitioning: A Survey",
      "author": "Elsner U.",
      "year": "1997",
      "unstructured": "U. Elsner Graph Partitioning: A Survey (Technische Universit\u00e4t Chemnitz, Chemnitz, Germany, Technical Report 97-27. (1997)."
    },
    {
      "key": "e_1_3_3_14_2",
      "unstructured": "P.-O. Fj\u00e4llstr\u00f6m Link\u00f6ping Electronic Articles in Computer and Information Science Vol. 3 Available at www.ep.liu.se/ea/cis/1998/006. Accessed May 10 2006. (1998)."
    },
    {
      "key": "e_1_3_3_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1086/226141"
    },
    {
      "key": "e_1_3_3_16_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1017/CBO9780511815478"
    },
    {
      "key": "e_1_3_3_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.69.026113"
    },
    {
      "key": "e_1_3_3_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.69.066133"
    },
    {
      "key": "e_1_3_3_19_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.72.027104"
    },
    {
      "key": "e_1_3_3_20_2",
      "unstructured": "F. R. K. Chung (Am. Math. Soc. Providence RI no. 92. (1997)."
    },
    {
      "key": "e_1_3_3_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.21136/CMJ.1973.101168"
    },
    {
      "key": "e_1_3_3_22_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0611030"
    },
    {
      "key": "e_1_3_3_23_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1086/jar.33.4.3629752"
    },
    {
      "key": "e_1_3_3_24_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.0400054101"
    },
    {
      "key": "e_1_3_3_25_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/j.1538-7305.1970.tb01770.x"
    },
    {
      "key": "e_1_3_3_26_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.70.066111"
    },
    {
      "key": "e_1_3_3_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1142/S0219525903001067"
    },
    {
      "key": "e_1_3_3_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/35036627"
    },
    {
      "key": "e_1_3_3_29_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.68.065103"
    },
    {
      "key": "e_1_3_3_30_2",
      "unstructured": "X. Guardiola R. Guimer\u00e0 A. Arenas A. Diaz-Guilera D. Streib L. A. N. Amaral e-Print Archive http://xxx.lanl.gov/abs/cond-mat/0206240. (2002)."
    },
    {
      "key": "e_1_3_3_31_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.98.2.404"
    },
    {
      "key": "e_1_3_3_32_2",
      "doi-asserted-by": "crossref",
      "unstructured": "S. White P. Smyth eds H. Kargupta J. Srivastava C. Kamath A. Goodman (Society for Industrial and Applied Mathematics Philadelphia) pp. 274\u2013285 (2005).",
      "DOI": "10.1137/1.9781611972757.25"
    }
  ],
  "container-title": "Proceedings of the National Academy of Sciences",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://pnas.org/doi/pdf/10.1073/pnas.0601602103",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        1,
        9
      ]
    ],
    "date-time": "2025-01-09T02:01:23Z",
    "timestamp": 1736388083000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://pnas.org/doi/full/10.1073/pnas.0601602103"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2006,
        6,
        6
      ]
    ]
  },
  "references-count": 32,
  "journal-issue": {
    "issue": "23",
    "published-print": {
      "date-parts": [
        [
          2006,
          6,
          6
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1073/pnas.0601602103"
  ],
  "URL": "http://dx.doi.org/10.1073/pnas.0601602103",
  "relation": {},
  "ISSN": [
    "0027-8424",
    "1091-6490"
  ],
  "subject": [],
  "container-title-short": "Proc. Natl. Acad. Sci. U.S.A.",
  "published": {
    "date-parts": [
      [
        2006,
        6,
        6
      ]
    ]
  },
  "assertion": [
    {
      "value": "2006-02-26",
      "order": 0,
      "name": "received",
      "label": "Received",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    },
    {
      "value": "2006-06-06",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}