Modularity optimization by conformational space annealing
Physical Review EPublished 17 May 2012
Juyong Lee, Steven P. Gross, Jooyoung Lee
Citations57
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 modularity optimization method, Mod-CSA, based on stochastic global optimization algorithm, conformational space annealing (CSA), which outperforms simulatedAnnealing in terms of both efficiency and accuracy, and finds higher modularity partitions with less computational resources required.
Abstract
We propose a modularity optimization method, Mod-CSA, based on stochastic global optimization algorithm, conformational space annealing (CSA). Our method outperforms simulated annealing in terms of both efficiency and accuracy, finding higher modularity partitions with less computational resources required. The high modularity values found by our method are higher than, or equal to, the largest values previously reported. In addition, the method can be combined with other heuristic methods, and implemented in parallel fashion, allowing it to be applicable to large graphs with more than 10,000 nodes.
Keywords
Computer SciencePhysics 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.
Journal of Statistical Mechanics Theory and ExperimentFast unfolding of communities in large networks
21,223 Citations2008Vincent D. Blondel, Jean‐Loup Guillaume +2 more
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.
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.
Physics ReportsCommunity detection in graphs
11,324 Citations2009Santo Fortunato
A thorough exposition of community structure, or clustering, is attempted, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists.
Journal of the American Statistical AssociationObjective Criteria for the Evaluation of Clustering Methods
5,815 Citations1971Telmo Menezes
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.
Proceedings of the National Academy of SciencesMaps of random walks on complex networks reveal community structure
4,688 Citations2008Martin Rosvall, Carl T. Bergstrom
An information theoretic approach is introduced that reveals community structure in weighted and directed networks of large-scale biological and social systems and reveals a directional pattern of citation from the applied fields to the basic sciences.
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.
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.
Physical Review ECommunity detection algorithms: A comparative analysis
2,218 Citations2009Andrea Lancichinetti, Santo Fortunato
Three recent algorithms introduced by Rosvall and Bergstrom and Ronhovde and Nussinov have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.
NatureLink communities reveal multiscale complexity in networks
1,941 Citations2010Yong‐Yeol Ahn, James P. Bagrow +1 more
It is implied that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.
Computer Science ReviewGraph clustering
1,574 Citations2007Satu Elisa Schaeffer
This survey overviews the definitions and methods for graph clustering, that is, finding sets of ''related'' vertices in graphs, and presents global algorithms for producing a clustering for the entire vertex set of an input graph.
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.
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.
Proceedings of the National Academy of SciencesMonte Carlo-minimization approach to the multiple-minima problem in protein folding.
1,478 Citations1987Zhi Li, Harold A. Scheraga
The Monte Carlo-minimization method has located the lowest-energy minimum thus far reported for the brain pentapeptide [Met5]enkephalin in the absence of water, presumably it is the global minimum-energy structure.
IEEE Transactions on Knowledge and Data EngineeringOn Modularity Clustering
1,221 Citations2008Ulrik Brandes, Daniel Delling +5 more
The conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts is proved and an Integer Linear Programming formulation is given.
Physical Review EPerformance of modularity maximization in practical contexts
950 Citations2010Benjamin H. Good, Yves-Alexandre de Montjoye +1 more
It is shown that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum, implying that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts.
Scale-Free Networks
753 Citations2007Guido Caldarelli
Journal of Statistical Mechanics Theory and ExperimentCartography of complex networks: modules and universal roles
750 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
It is demonstrated that one can (i) find modules in complex networks and (ii) classify nodes into universal roles according to their pattern of within- and between-module connections, which yields a ‘cartographic representation’ of complex networks.
The European Physical Journal BModularity-maximizing graph communities via mathematical programming
340 Citations2008Gunjan Agarwal, David Kempe
This paper introduces the technique of rounding mathematical programs to the problem of modularity maximization, presenting two novel algorithms that perform comparably or better than past algorithms, while being more efficient than exhaustive techniques.
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.
Journal of Computational ChemistryNew optimization method for conformational energy calculations on polypeptides: Conformational space annealing
301 Citations1997Jooyoung Lee, Harold A. Scheraga +1 more
Physica A Statistical Mechanics and its ApplicationsAdvanced modularity-specialized label propagation algorithm for detecting communities in networks
241 Citations2009Xin Liu, Tsuyoshi Murata
Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks and offers a fair compromise between accuracy and speed.
Physical Review EEfficient modularity optimization by multistep greedy algorithm and vertex mover refinement
165 Citations2008Philipp Schuetz, Amedeo Caflisch
A multistep extension of the greedy algorithm (MSG) that allows the merging of more than one pair of communities at each iteration step to prevent the premature condensation into few large communities is presented.
Proceedings of the National Academy of SciencesEnergy-based <i>de novo</i> protein folding by conformational space annealing and an off-lattice united-residue force field: Application to the 10-55 fragment of staphylococcal protein A and to apo calbindin D9K
147 Citations1999Jooyoung Lee, Adam Liwo +1 more
It appears that the CSA method with the UNRES force field, which is based on the thermodynamic hypothesis, can be used in prediction of protein structures in real time.
Physical Review LettersUnbiased Global Optimization of Lennard-Jones Clusters for<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>N</mml:mi><mml:mo>≤</mml:mo><mml:mn>201</mml:mn></mml:math>Using the Conformational Space Annealing Method
138 Citations2003Julian Lee, In‐Ho Lee +1 more
The conformational space annealing method is applied to the Lennard-Jones clusters and found all known lowest energy configurations up to 201 atoms, without using extra information of the problem such as the structures of the known global energy minima.
Physical Review EColumn generation algorithms for exact modularity maximization in networks
129 Citations2010Daniel Aloise, Sonia Cafieri +4 more
Four algorithms for maximizing modularity maximization using the powerful column generation methods for linear and non linear integer programming and their performance is compared on problems from the literature.
PLoS Computational BiologyIn Search of the Biological Significance of Modular Structures in Protein Networks
121 Citations2007Zhi Wang, Jianzhi Zhang
Using computer simulation, it is demonstrated that a higher-than-expected modularity can arise during network growth through a simple model of gene duplication, without natural selection for modularity.
The European Physical Journal BFinding community structures in complex networks using mixed integer optimisation
81 Citations2007Guangyong Xu, Sophia Tsoka +1 more
Comparative results with other approaches from the literature show that the proposed methodology has superior performance while global optimum is guaranteed.
PLoS Computational BiologyTopological Cluster Analysis Reveals the Systemic Organization of the Caenorhabditis elegans Connectome
79 Citations2011Yunkyu Sohn, Myung-kyu Choi +3 more
The modularity-based community detection method for directed, weighted networks is used to examine hierarchically organized modules in the complete wiring diagram (connectome) of Caenorhabditis elegans and to investigate their topological properties.
Physical Review EAdaptive clustering algorithm for community detection in complex networks
73 Citations2008Zhen-Qing Ye, Songnian Hu +1 more
This work introduced a different adaptive clustering algorithm capable of extracting modules from complex networks with considerable accuracy and robustness and shows the superiority of this algorithm to find communities that are parallel with the appropriate organization in reality.
Proteins Structure Function and Bioinformatics<i>De novo</i> protein structure prediction by dynamic fragment assembly and conformational space annealing
61 Citations2011Juyong Lee, Juyong Lee +7 more
Test results on 30 small single‐domain proteins and 13 template‐free modeling targets of the 8th Critical Assessment of protein Structure Prediction show that the current method provides comparable and complementary prediction results to existing top methods.
Biophysical JournalMultiple Sequence Alignment by Conformational Space Annealing
43 Citations2008Keehyoung Joo, Jinwoo Lee +5 more
MSACSA provides not just the global minimum alignment but also many distinct low-lying suboptimal alignments for a given objective function, due to the fact that conformational space annealing can maintain conformational diversity while searching for the conformations with low energies.
Computer Physics CommunicationsEfficient parallel algorithms in global optimization of potential energy functions for peptides, proteins, and crystals
39 Citations2000Jooyoung Lee, Jarosław Pillardy +7 more
This paper provides several examples of parallel implementations of global optimization algorithms developed in the laboratory and most of the methods are parallelized on the algorithmic level and one example of fine-grain parallelism is given, in which the function evaluation itself is computationally expensive.
Lecture notes in computer scienceExperimental Algorithms
29 Citations2008Catherine C. McGeoch
Bargaining with reading habit is no need and what will be given by this experimental algorithms 7th international workshop wea 2008 provincetown may 30 june 1, how can you bargain with the thing that has many benefits for you?