Modularity and community structure in networks

M. E. J. Newman

doi:10.1073/pnas.0601602103

Edited by Brian Skyrms, University of California, Irvine, CA, and approved April 19, 2006 (received for review February 26, 2006)

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.

Footnotes

*E-mail: mejn{at}umich.edu
Author contributions: M.E.J.N. designed research, performed research, analyzed data, and wrote the paper.
↵ † Adamic, L. A. & Glance, N., WWW-2005 Workshop on the Weblogging Ecosystem, May 10–14, 2005, Chiba, Japan.
Conflict of interest statement: No conflicts declared.
This paper was submitted directly (Track II) to the PNAS office.
© 2006 by The National Academy of Sciences of the USA