Community detection in complex networks using extremal optimization
Physical Review EPublished 24 August 2005Open access
Jordi Duch, Àlex Arenas
Citations1,573
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 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.
Abstract
We propose a method to find the community structure in complex networks based on an extremal optimization of the value of modularity. The method outperforms the optimal modularity found by the existing algorithms in the literature giving a better understanding of the community structure. We present the results of the algorithm for computer-simulated and real networks and compare them with other approaches. The efficiency and accuracy of the method make it feasible to be used for the accurate identification of community structure in large complex networks.
Keywords
PsychologyPhysics and Astronomy
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex 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.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
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.
NatureExploring complex networks
8,339 Citations2001Steven H. Strogatz
This work aims to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture.
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.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
Physical Review LettersSolvable Model of a Spin-Glass
4,298 Citations1975David C. Sherrington, Scott Kirkpatrick
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.
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.
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScientific collaboration networks. I. Network construction and fundamental results
2,057 Citations2001M. E. J. Newman
Using computer databases of scientific papers in physics, biomedical research, and computer science, a network of collaboration between scientists in each of these disciplines is constructed, and a number of measures of centrality and connectedness in the same networks are studied.
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.
Physical Review LettersPunctuated equilibrium and criticality in a simple model of evolution
1,524 Citations1993Per Bak, Kim Sneppen
A simple and robust model of biological evolution of an ecology of interacting species that self-organizes into a critical steady state with intermittent coevolutionary avalanches of all sizes and exhibits ``punctuated equilibrium'' behavior.
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.
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.
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.
Journal of Statistical Mechanics Theory and ExperimentDetecting network communities: a new systematic and efficient algorithm
364 Citations2004Luca Donetti, Miguel A Muñoz
Proceedings of the National Academy of SciencesCurvature of co-links uncovers hidden thematic layers in the World Wide Web
353 Citations2002Jean‐Pierre Eckmann, Elisha Moses
It is demonstrated here how thematic relationships can be located precisely by looking only at the graph of hyperlinks, gleaning content and context from the Web without having to read what is in the pages.
Physical Review LettersOptimization with Extremal Dynamics
341 Citations2001Stefan Boettcher, Allon G. Percus
This work uses extremal optimization to elucidate the phase transition in the 3-coloring problem, and provides independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.
Artificial IntelligenceNature's way of optimizing
286 Citations2000Stefan Boettcher, Allon G. Percus
The method, called Extremal Optimization, successively eliminates extremely undesirable components of sub-optimal solutions in a manner that proves competitive with, and often superior to, more elaborate stochastic optimization procedures.
Physical Review LettersModularity and Extreme Edges of the Internet
212 Citations2003Kasper Astrup Eriksen, Ingve Simonsen +2 more
The spectral properties of a diffusion process taking place on the Internet network focusing on the slowest decaying modes are studied to use the fraction of nodes participating in slow decaying modes as a general measure of the modularity of a network.
The European Physical Journal BCommunity analysis in social networks
172 Citations2004A. Arenas, L. Danon +3 more
The analysis reveals the community structure and provides a useful visualising technique, and it is found that the networks’ community structure is topologically self-similar using the Horton-Strahler index.
Physical Review EIdentifying communities within energy landscapes
158 Citations2005Claire P. Massen, Jonathan P. K. Doye
The definition of the modularity has been refined, making it more appropriate for networks such as these where multiple edges and self-connections are not included, and communities that are comparable to those expected from landscape analyses are found.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsExtremal optimization for graph partitioning
138 Citations2001Stefan Boettcher, Allon G. Percus
Numerical results demonstrate that extremal optimization maintains consistent accuracy for increasing system sizes, with an approximation error decreasing over run time roughly as a power law t(-0.4).