Fast unfolding of communities in large networks
Journal of Statistical Mechanics Theory and ExperimentPublished 1 October 2008Open access
Vincent D. Blondel, Jean‐Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
Citations21,223
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
This work proposes a heuristic method that is shown to outperform all other known community detection methods in terms of computation time and the quality of the communities detected is very good, as measured by the so-called modularity.
Abstract
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad hoc modular networks.
Keywords
Computer SciencePhysics and Astronomy
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.
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.
Proceedings of the National Academy of SciencesModularity and community structure in networks
12,281 Citations2006M. E. J. Newman
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.
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.
NatureUncovering the overlapping community structure of complex networks in nature and society
5,435 Citations2005Gergely Palla, Imre Derényi +2 more
After defining a set of new characteristic quantities for the statistics of communities, this work applies an efficient technique for exploring overlapping communities on a large scale and finds that overlaps are significant, and the distributions introduced reveal universal features of networks.
Physical Review EFinding community structure in networks using the eigenvectors of matrices
4,801 Citations2006M. E. J. Newman
A modularity matrix plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations, and a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong are proposed.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
Physical Review ENear linear time algorithm to detect community structures in large-scale networks
3,542 Citations2007Usha Nandini Raghavan, Réka Albert +1 more
This paper investigates a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities.
Proceedings of the National Academy of SciencesResolution limit in community detection
3,045 Citations2006Santo Fortunato, Marc Barthélemy
It is found that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.
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.
Physical Review EAnalysis of weighted networks
2,451 Citations2004M. E. J. Newman
It is pointed out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighting graphs to weighted ones as well.
Princeton University Press eBooksThe Structure and Dynamics of Networks
2,292 Citations2011Mark Newman, Albert-Ĺaszló Barabási +1 more
Proceedings of the National Academy of SciencesStructure and tie strengths in mobile communication networks
1,958 Citations2007Jukka‐Pekka Onnela, Jari Saramäki +6 more
It is found that, when it comes to information diffusion, weak and strong ties are both simultaneously ineffective, and this coupling significantly slows the diffusion process, resulting in dynamic trapping of information in communities.
NatureQuantifying social group evolution
1,657 Citations2007Gergely Palla, Albert-Ĺaszló Barabási +1 more
The focus is on networks capturing the collaboration between scientists and the calls between mobile phone users, and it is found that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability.
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.
NatureSelf-similarity of complex networks
1,525 Citations2005Chaoming Song, Shlomo Havlin +1 more
A power-law relation is identified between the number of boxes needed to cover the network and the size of the box, defining a finite self-similar exponent to explain the scale-free nature of complex networks and suggest a common self-organization dynamics.
Journal of Graph Algorithms and ApplicationsComputing Communities in Large Networks Using Random Walks
1,461 Citations2006Pascal Pons, Matthieu Latapy
Physical Review EModularity from fluctuations in random graphs and complex networks
905 Citations2004Roger Guimerà, Marta Sales‐Pardo +1 more
It is shown both numerically and analytically that random graphs and scale-free networks have modularity and it is argued that this fact must be taken into consideration to define statistically significant modularity in complex networks.
Physical Review LettersDetecting Fuzzy Community Structures in Complex Networks with a Potts Model
599 Citations2004Jörg Reichardt, Stefan Bornholdt
A fast community detection algorithm based on a q-state Potts model that allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community.
Proceedings of the National Academy of SciencesExtracting the hierarchical organization of complex systems
552 Citations2007Marta Sales‐Pardo, Roger Guimerà +2 more
An unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks is introduced and validated and an ensemble of hierarchically nested random graphs is defined, which is used to validate the method.
The European Physical Journal BFinding communities in linear time: a physics approach
456 Citations2004F. Wu, Bernardo A. Huberman
The European Physical Journal B (EPJ B) publishes regular articles and colloquia in Condensed Matter and Complex Systems on the range of topics including Solid State and Materials, Computational Methods, Statistical and Nonlinear Physics, and Interdisciplinary Physics.
New Journal of PhysicsAnalysis of the structure of complex networks at different resolution levels
453 Citations2008A Arenas, A Fernández +1 more
The proposed method allows for multiple resolution screening of the modular structure, and its application to two real social networks allows us to find the exact splits reported in the literature, as well as the substructure beyond the actual split.
Physica A Statistical Mechanics and its ApplicationsGeographical dispersal of mobile communication networks
447 Citations2008Renaud Lambiotte, Vincent D. Blondel +5 more
It is shown that the degree distribution in this network has a power-law degree distribution k−5 and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases as d−2, where d is the distance between the customers.
New Journal of PhysicsSize reduction of complex networks preserving modularity
332 Citations2007Àlex Arenas, Jordi Duch +2 more
This work proposes an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining their modularity and compares the modularity obtained by using the extremal optimization algorithm, before and after the size reduction.
Physical Review EMajority model on a network with communities
111 Citations2007Renaud Lambiotte, Marcel Ausloos +1 more
This work focuses on the majority model in a topology consisting of two coupled fully connected networks, thereby mimicking the existence of communities in social networks, and shows that a transition takes place at a value of the interconnectivity parameter.