Modularity and community structure in networks
Proceedings of the National Academy of SciencesPublished 24 May 2006Open access
M. E. J. Newman
Citations12,281
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the modularity of a network can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which is called 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.
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.
Keywords
Biochemistry, Genetics and Molecular BiologyPhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
Cambridge University Press eBooksSocial Network Analysis
17,041 Citations1994Stanley Wasserman, Katherine Faust
This paper presents mathematical representation of social networks in the social and behavioral sciences through the lens of dyadic and triadic interaction models, which provide insights into the structure and dynamics of relationships between actors and groups.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
Physical Review EFinding and evaluating community structure in networks
13,892 Citations2004Michelle G. Newman, Michelle Girvan
It is demonstrated that the algorithms proposed are highly effective at discovering community structure in both computer-generated and real-world network data, and can be used to shed light on the sometimes dauntingly complex structure of networked systems.
ScienceNetwork Motifs: Simple Building Blocks of Complex Networks
7,497 Citations2002Ron Milo, Shai S. Shen-Orr +4 more
Network motifs, patterns of interconnections occurring in complex networks at numbers that are significantly higher than those in randomized networks, are defined and may define universal classes of networks.
Physical Review EFinding community structure in very large networks
7,484 Citations2004Aaron Clauset, M. E. J. Newman +1 more
A hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure.
Physical Review EFast algorithm for detecting community structure in networks
5,491 Citations2004M. E. J. Newman
An algorithm is described which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms.
Bell System Technical JournalAn Efficient Heuristic Procedure for Partitioning Graphs
5,218 Citations1970Brian W. Kernighan, Shang Min Lin
A heuristic method for partitioning arbitrary graphs which is both effective in finding optimal partitions, and fast enough to be practical in solving large problems is presented.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
Proceedings of the National Academy of SciencesThe structure of scientific collaboration networks
4,502 Citations2001M. E. J. Newman
It is shown that these collaboration networks form "small worlds," in which randomly chosen pairs of scientists are typically separated by only a short path of intermediate acquaintances.
NatureThe large-scale organization of metabolic networks
4,031 Citations2000H. Jeong, B. Tombor +3 more
This analysis of metabolic networks of 43 organisms representing all three domains of life shows that, despite significant variation in their individual constituents and pathways, these metabolic networks have the same topological scaling properties and show striking similarities to the inherent organization of complex non-biological systems.
NatureFunctional cartography of complex metabolic networks
4,013 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
A methodology is proposed that can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections, which yields a ‘cartographic representation’ of complex networks.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Journal of Statistical Mechanics Theory and ExperimentComparing community structure identification
2,877 Citations2005León Danon, Albert Dı́az-Guilera +2 more
It is found 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.
Proceedings of the National Academy of SciencesDefining and identifying communities in networks
2,453 Citations2004Filippo Radicchi, Claudio Castellano +3 more
This article proposes a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability and applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods.
American Journal of SociologySocial Structure from Multiple Networks. I. Blockmodels of Roles and Positions
2,050 Citations1976Harrison C. White, Scott A. Boorman +1 more
The European Physical Journal BDetecting community structure in networks
2,022 Citations2004M. E. J. Newman
A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
Physical Review ECommunity detection in complex networks using extremal optimization
1,573 Citations2005Jordi Duch, Àlex Arenas
The method outperforms the optimal modularity found by the existing algorithms in the literature and is feasible to be used for the accurate identification of community structure in large complex networks.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSelf-similar community structure in a network of human interactions
1,491 Citations2003Roger Guimerà, León Danon +3 more
The results reveal the self-organization of the network into a state where the distribution of community sizes is self-similar, suggesting that a universal mechanism, responsible for emergence of scaling in other self-organized complex systems, as, for instance, river networks, could also be the underlying driving force in the formation and evolution of social networks.
Advances in Complex SystemsCOMMUNITY STRUCTURE IN JAZZ
1,027 Citations2003PABLO M. GLEISER, LEON DANON
Using a database of jazz recordings, a quantitative analysis of the community size distribution and community structure analysis reveals that these constructions capture essential ingredients of the social interactions between jazz musicians.
ComputerSelf-organization and identification of Web communities
1,007 Citations2002Gary William Flake, Sandra Lawrence +2 more
This work shows that the Web self-organizes and its link structure allows efficient identification of communities and is significant because no central authority or process governs the formation and structure of hyperlinks.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScale-free topology of e-mail networks
952 Citations2002Holger Ebel, Lutz-Ingo Mielsch +1 more
The resulting network exhibits a scale-free link distribution and pronounced small-world behavior, as observed in other social networks, implying that the spreading of e-mail viruses is greatly facilitated in real e- mail networks compared to random architectures.
Bulletin of the London Mathematical SocietySPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
438 Citations1998Norman Biggs
A Spectral Clustering Approach To Finding Communities in Graphs
399 Citations2005Scott R. White, Padhraic Smyth
This paper shows how optimizing the Q function can be reformulated as a spectral relaxation problem and proposes two new spectral clustering algorithms that seek to maximize Q and indicates that the new algorithms are efficient and effective at finding both good clusterings and the appropriate number of clusters across a variety of real-world graph data sets.
BioinformaticsSubnetwork hierarchies of biochemical pathways
366 Citations2003Petter Holme, Mikael Huss +1 more
A method to decompose biochemical networks into subnetworks based on the global geometry of the network is presented and is applied to 43 organisms from the WIT database.
Qucosa (Saxon State and University Library Dresden)Graph partitioning - a survey
72 Citations2005Ulrich Elsner