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.

@article{newman2006modularity, author = {Newman, M. E. J.}, title = {Modularity and community structure in networks}, journal = {Proceedings of the National Academy of Sciences}, year = {2006}, volume = {103}, number = {23}, pages = {8577--8582}, doi = {10.1073/pnas.0601602103}, keywords = {clustering, community, graph, modularity, network, structure}, 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.} }

%0 = article %A = Newman, M. E. J. %D = 2006 %T = Modularity and community structure in networks

@article{clauset-2004-70, author = {Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher}, title = {Finding community structure in very large networks}, journal = {Physical Review E}, year = {2004}, volume = {70}, pages = {066111}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187}, keywords = {community, detection, gn, large, network, newman, structure} }

%0 = article %A = Clauset, Aaron and Newman, M.E.J. and Moore, Cristopher %D = 2004 %T = Finding community structure in very large networks %U = http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0408187

@article{1035162, author = {Kumar, Ravi and Novak, Jasmine and Raghavan, Prabhakar and Tomkins, Andrew}, title = {Structure and evolution of blogspace}, journal = {Commun. ACM}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2004}, volume = {47}, number = {12}, pages = {35--39}, url = {http://doi.acm.org/10.1145/1035134.1035162}, issn = {0001-0782}, keywords = {blogging, seminar2006, structure, community} }

%0 = article %A = Kumar, Ravi and Novak, Jasmine and Raghavan, Prabhakar and Tomkins, Andrew %C = New York, NY, USA %D = 2004 %I = ACM Press %T = Structure and evolution of blogspace %U = http://doi.acm.org/10.1145/1035134.1035162

We propose and study a set of algorithms for discovering community structure in networks - natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.

@article{newman2004finding, author = {Newman, M.E.J. and Girvan, M.}, title = {Finding and evaluating community structure in networks}, journal = {Physical Review E}, year = {2004}, volume = {69}, pages = {026113}, url = {http://arxiv.org/abs/cond-mat/0308217}, doi = {10.1103/PhysRevE.69.026113}, keywords = {community, detection, girvan, gn, modularity, network, newman, structure}, abstract = {We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems. } }

%0 = article %A = Newman, M.E.J. and Girvan, M. %D = 2004 %T = Finding and evaluating community structure in networks %U = http://arxiv.org/abs/cond-mat/0308217

We describe a method for the automatic identification of communities of practice from email logs within an organization. We use a betweenness centrality algorithm that can rapidly find communities within a graph representing information flows. We apply this algorithm to an email corpus of nearly one million messages collected over a two-month span, and show that the method is effective at identifying true communities, both formal and informal, within these scale-free graphs. This approach also enables the identification of leadership roles within the communities. These studies are complemented by a qualitative evaluation of the results in the field.

@inbook{tyler2003email, author = {Tyler, Joshua R. and Wilkinson, Dennis M. and Huberman, Bernardo A.}, title = {Email as Spectroscopy: Automated Discovery of Community Structure within Organizations}, booktitle = {Communities and technologies}, publisher = {Kluwer, B.V.}, address = {Deventer, The Netherlands, The Netherlands}, year = {2003}, pages = {81--96}, url = {http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0303264}, keywords = {gn, detection, email, structure, community}, abstract = {We describe a method for the automatic identification of communities of practice from email logs within an organization. We use a betweenness centrality algorithm that can rapidly find communities within a graph representing information flows. We apply this algorithm to an email corpus of nearly one million messages collected over a two-month span, and show that the method is effective at identifying true communities, both formal and informal, within these scale-free graphs. This approach also enables the identification of leadership roles within the communities. These studies are complemented by a qualitative evaluation of the results in the field.} }

%0 = inbook %A = Tyler, Joshua R. and Wilkinson, Dennis M. and Huberman, Bernardo A. %B = Communities and technologies} %C = Deventer, The Netherlands, The Netherlands %D = 2003 %I = Kluwer, B.V. %T = Email as Spectroscopy: Automated Discovery of Community Structure within Organizations} %U = http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0303264

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known--a collaboration network and a food web--and find that it detects significant and informative community divisions in both cases.

@article{gn02community, author = {Girvan, Michelle and Newman, M.E.J.}, title = {Community structure in social and biological networks}, journal = {Proceedings of the National Academy of Science}, year = {2002}, volume = {99}, number = {12}, pages = {7821-7826}, keywords = {social, gn, detection, structure, community, network}, abstract = {A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known---a collaboration network and a food web---and find that it detects significant and informative community divisions in both cases.} }

%0 = article %A = Girvan, Michelle and Newman, M.E.J. %D = 2002 %T = Community structure in social and biological networks