Detecting the overlapping and hierarchical community structure in complex networks
New Journal of PhysicsPublished 10 March 2009Open access
Andrea Lancichinetti, Santo Fortunato, János Kertész
Citations1,960
SJR quartileQ1
SJR score0.94
SNIP0.93
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
The first algorithm that finds both overlapping communities and the hierarchical structure is presented, based on the local optimization of a fitness function, enabling different hierarchical levels of organization to be investigated.
Abstract
Abstract. Many networks in nature, society and technology are characterized by a mesoscopic level of organization, with groups of nodes forming tightly connected units, called communities or modules, that are only weakly linked to each other. Uncovering this community structure is one of the most important problems in the field of complex networks. Networks often show a hierarchical organization, with communities embedded within other communities; moreover, nodes can be shared between different communities. Here we present the first algorithm that finds both overlapping communities and the hierarchical structure. The method is based on the local optimization of a fitness function. Community structure is revealed by peaks in the fitness histogram. The resolution can be tuned by a parameter enabling to investigate different hierarchical levels of organization. Tests on real and artificial networks give excellent results. PACS numbers: 89.75.-k, 89.75.Hc, 05.40-a, 89.75.Fb, 87.23.GeDetecting the overlapping and hierarchical community structure in complex networks 2 1.
Keywords
Biochemistry, Genetics and Molecular BiologyPhysics 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.
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.
Social network analysis methods and applications
18,142 Citations2007Stanley Wasserman, Katherine Faust
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 SciencesCluster analysis and display of genome-wide expression patterns
16,395 Citations1998Michael B. Eisen, Paul T. Spellman +2 more
A system of cluster analysis for genome-wide expression data from DNA microarray hybridization is described that uses standard statistical algorithms to arrange genes according to similarity in pattern of gene expression, finding in the budding yeast Saccharomyces cerevisiae that clustering gene expression data groups together efficiently genes of known similar function.
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.
Physics ReportsComplex networks: Structure and dynamics
11,022 Citations2006Stefano Boccaletti, Vito Latora +3 more
The major concepts and results recently achieved in the study of the structure and dynamics of complex networks are reviewed, and the relevant applications of these ideas in many different disciplines are summarized, ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering.
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.
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.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
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.
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.
RePEc: Research Papers in EconomicsEvolution of networks from biological nets to the Internet and WWW
2,053 Citations2003S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The aim of the text is to understand networks and the basic principles of their structural organization and evolution, so even students without a deep knowledge of mathematics and statistical physics will be able to rely on this as a reference.
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.
The European Physical Journal BHierarchical structure in financial markets
2,017 Citations1999Rosario N. Mantegna
A hierarchical arrangement of stocks traded in a financial market is found by investigating the daily time series of the logarithm of stock price and the hierarchical tree of the subdominant ultrametric space associated with the graph provides a meaningful economic taxonomy.
Behavior Research Methods, Instruments, & ComputersThe University of South Florida free association, rhyme, and word fragment norms
1,973 Citations2004Douglas L. Nelson, Cathy L. McEvoy +1 more
The database will be useful for investigators interested in cuing, priming, recognition, network theory, linguistics, and implicit testing applications, and for evaluating the predictive value of free association probabilities as compared with other measures, such as similarity ratings and co-occurrence norms.
Journal of Multivariate AnalysisComparing clusterings—an information based distance
1,560 Citations2006Marina Meilă
This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set, called variation of information (VI), and presents it from an axiomatic point of view, showing that it is the only ''sensible'' criterion for compare partitions that is both aligned to the lattice and convexely additive.
Oxford University Press eBooksEvolution of Networks
1,528 Citations2003S. N. Dorogovt︠s︡ev, J. F. F. Mendes
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.
Cambridge University Press eBooksEvolution and Structure of the Internet
1,335 Citations2004Romualdo Pastor‐Satorras, Alessandro Vespignani
Viewed in this analysis from a statistical physics perspective, the Internet is perceived as a developing system that evolves through the addition and removal of nodes and links, allowing the authors to outline the dynamical theory that can appropriately describe the Internet's macroscopic evolution.
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 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 LettersSynchronization Reveals Topological Scales in Complex Networks
854 Citations2006Àlex Arenas, Albert Dı́az-Guilera +1 more
The analysis is based on the full dynamics towards synchronization of a system of coupled oscillators and provides a useful connection between synchronization dynamics, complex networks topology, and spectral graph analysis.
Proceedings of the Royal Society B Biological SciencesThe emergent properties of a dolphin social network
824 Citations2003David Lusseau
Despite its small size, the Doubtful Sound community of bottlenose dolphins has the same characteristics of a scale-free power-law network, and the ability for two individuals to be in contact is unaffected by the random removal of individuals.
NatureCompartments revealed in food-web structure
794 Citations2003Ann E. Krause, Kenneth A. Frank +3 more
It is shown that a method for detecting compartments from the social networking science identified significant compartments in three of five complex, empirical food webs.
Physical Review EFinding local community structure in networks
789 Citations2005Aaron Clauset
This work defines both a measure of local community structure and an algorithm that infers the hierarchy of communities that enclose a given vertex by exploring the graph one vertex at a time, and uses this algorithm to extract meaningful local clustering information in the large recommender network of an online retailer.
Proceedings of the Royal Society B Biological SciencesIdentifying the role that animals play in their social networks
723 Citations2004David Lusseau, M. E. J. Newman
The network is found to be similar to human social networks in some respects but different in some others, such as the level of assortative mixing by degree within the population, which elucidates some of the means by which the network forms and evolves.
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.
Physica A Statistical Mechanics and its ApplicationsIdentification of overlapping community structure in complex networks using fuzzy -means clustering
521 Citations2006Shihua Zhang, Rui‐Sheng Wang +1 more
A novel algorithm to identify overlapping communities in complex networks by the combination of a new modularity function based on generalizing NG's Q function, an approximation mapping of network nodes into Euclidean space and fuzzy c-means clustering is devised.
ScienceLife's Complexity Pyramid
506 Citations2002Zoltán N. Oltvai, Albert-Ĺaszló Barabási
Two new studies that investigate both biological networks of intracellular components and nonbiological networks such as the World Wide Web are discussed, explaining that all networks seem to be organized according to the same distinct principles.
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.
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.
Physical Review ERobustness of community structure in networks
350 Citations2008Brian Karrer, Elizaveta Levina +1 more
It is shown that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure.
Physical Review ELocal method for detecting communities
292 Citations2005James P. Bagrow, Erik M. Bollt
A method of community detection that is computationally inexpensive and possesses physical significance to a member of a social network is proposed and is local in the sense that a community can be detected within a network without requiring knowledge of the entire network.
Complex systems and interdisciplinary scienceLarge Scale Structure and Dynamics of Complex Networks
255 Citations2007Guido Caldarelli, Alessandro Vespignani
This book is the culmination of three years of research effort on a multidisciplinary project in which physicists, mathematicians, computer scientists and social scientists worked together to arrive at a unifying picture of complex networks.
Theoretical Population BiologyThe structure of food webs
220 Citations1979Stuart L. Pimm
For nonrandom models of species interaction there is a precipitous decrease in stability as connectance increases, however, the range of stability for different models of the same connectance is large; stability also depends on how the species interactions are organized.
Computational ComplexityCommunity Structure in Graphs
213 Citations2011Santo Fortunato, Claudio Castellano
The European Physical Journal BLimited resolution in complex network community detection with Potts model approach
188 Citations2007Jussi M. Kumpula, Jari Saramäki +2 more
The q-state Potts community detection method introduced by Reichardt and Bornholdt also has a resolution threshold, and the model contains a parameter by which this threshold can be tuned, but no a priori principle is known to select the proper value.
Physica D Nonlinear PhenomenaSynchronization processes in complex networks
163 Citations2006Àlex Arenas, Albert Dı́az-Guilera +1 more
An extended analysis, based on the dynamics towards synchronization of a system of coupled oscillators, of the hierarchy of communities in complex networks, provides a useful connection between synchronization dynamics, complex networks topology and spectral graph analysis.
Lecture notes in computer scienceStructural Inference of Hierarchies in Networks
142 Citations2008Aaron Clauset, Cristopher Moore +1 more
This work gives a precise definition of hierarchical structure, gives a generic model for generating arbitrary hierarchical structure in a random graph, and describes a statistically principled way to learn the set of hierarchical features that most plausibly explain a particular real-world network.
Lecture notes in computer scienceEfficient Identification of Overlapping Communities
133 Citations2005Jeffrey Baumes, Mark Goldberg +1 more
This paper presents an efficient algorithm for finding overlapping communities in social networks that is significantly more efficient than the previous algorithm by Baumes et al and also produces clusters of a comparable or better quality.
The European Physical Journal CSearch for charginos and neutralinos in e $^+$ e $^-$ collisions at centre-of-mass energies near 183 GeV and constraints on the MSSM parameter space
31 Citations1999R. Barate et al.