dorsal/arxiv
View SchemaModularity and community structure in networks
| Authors | M. E. J. Newman |
|---|---|
| Categories | |
| ArXiv ID | physics/0602124 |
| URL | https://arxiv.org/abs/physics/0602124 |
| DOI | 10.1073/pnas.0601602103 |
| Journal | Proc. Natl. Acad. Sci. USA 103, 8577-8582 (2006) |
Abstract
Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.
{
"annotation_id": "605754c9-cc87-41c8-9e9c-46ef447eaa87",
"date_created": "2026-03-02T18:01:07.017000Z",
"date_modified": "2026-03-02T18:01:07.017000Z",
"file_hash": "43acdaae874fc13cd9bf5a44ed6b6ffdbc42c7c6c97b454dcde441ab2164ee98",
"private": false,
"record": {
"abstract": "Many networks of interest in the sciences, including a variety of social and\nbiological networks, are found to divide naturally into communities or modules.\nThe problem of detecting and characterizing this community structure has\nattracted considerable recent attention. One of the most sensitive detection\nmethods is optimization of the quality function known as \"modularity\" over the\npossible divisions of a network, but direct application of this method using,\nfor instance, simulated annealing is computationally costly. Here we show that\nthe modularity can be reformulated in terms of the eigenvectors of a new\ncharacteristic matrix for the network, which we call the modularity matrix, and\nthat this reformulation leads to a spectral algorithm for community detection\nthat returns results of better quality than competing methods in noticeably\nshorter running times. We demonstrate the algorithm with applications to\nseveral network data sets.",
"arxiv_id": "physics/0602124",
"authors": [
"M. E. J. Newman"
],
"categories": [
"physics.data-an",
"cond-mat.stat-mech",
"physics.soc-ph"
],
"doi": "10.1073/pnas.0601602103",
"journal_ref": "Proc. Natl. Acad. Sci. USA 103, 8577-8582 (2006)",
"title": "Modularity and community structure in networks",
"url": "https://arxiv.org/abs/physics/0602124"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "dc331092-8eb5-459c-9cde-8c7ad2b20b73",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}