Optimal partition and effective dynamics of complex networks
Proceedings of the National Academy of SciencesPublished 26 February 2008Open access
E Weinan, Tiejun Li, Eric Vanden‐Eijnden
Citations109
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 develops the necessary ingredients for an optimal partition strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on networks, and shows that when theMarkov chain is lumpable, it is recovered the partition with respect to which the chain is Lumpable.
Abstract
Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.
Keywords
MathematicsPhysics and Astronomy
Springer series in statisticsThe Elements of Statistical Learning
24,344 Citations2001Trevor Hastie, J. Friedman +1 more
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.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction
19,345 Citations2013Trevor Hastie, Robert Tibshirani +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
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 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.
Journal of Anthropological ResearchAn Information Flow Model for Conflict and Fission in Small Groups
4,661 Citations1977Wayne Zachary
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.
Applied and Computational Harmonic AnalysisDiffusion maps
2,345 Citations2006Ronald R. Coifman, Stéphane Lafon
It is shown that eigenfunctions of Markov matrices can be used to construct coordinates called diffusion maps that generate representations of complex geometric structures that prove to be useful in the context of data parametrization and dimensionality reduction.
Princeton University Press eBooksThe Structure and Dynamics of Networks
2,292 Citations2011Mark Newman, Albert-Ĺaszló Barabási +1 more
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 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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceDiffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization
619 Citations2006Stéphane Lafon, A.B. Lee
It is shown that the quantization distortion in diffusion space bounds the error of compression of the operator, thus giving a rigorous justification for k-means clustering in diffusionspace and a precise measure of the performance of general clustering algorithms.
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.
SIAM Journal on Numerical AnalysisOn the Approximation of Complicated Dynamical Behavior
521 Citations1999Michael Dellnitz, Oliver Junge
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.
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.
Linear Algebra and its ApplicationsIdentification of almost invariant aggregates in reversible nearly uncoupled Markov chains
328 Citations2000Peter Deuflhard, Wilhelm Huisinga +2 more
A robust algorithm is worked out on the basis of some detailed perturbation analysis and illustrated at a simple molecular system to identify the almost invariant aggregates together with the (small) probabilities of transitions between them.
Proceedings of the National Academy of SciencesOptimal prediction and the Mori–Zwanzig representation of irreversible processes
322 Citations2000Alexandre J. Chorin, Ole H. Hald +1 more
A relation between optimal prediction and the statistical mechanics of irreversible processes is pointed out, and a version of the Mori-Zwanzig formalism is used to produce a higher-order optimal prediction method.
Theory of Probability and Its ApplicationsOn Stochastic Processes Defined by Differential Equations with a Small Parameter
297 Citations1966R. Z. Has’minskiĭ
Physical Review EMethod to find community structures based on information centrality
294 Citations2004Santo Fortunato, Vito Latora +1 more
An algorithm of hierarchical clustering that consists in finding and removing iteratively the edge with the highest information centrality is developed that is very effective especially when the communities are very mixed and hardly detectable by the other methods.
Lecture notes in computer scienceNetwork Brownian Motion: A New Method to Measure Vertex-Vertex Proximity and to Identify Communities and Subcommunities
135 Citations2004Haijun Zhou, Reinhard Lipowsky
In this paper, the proximity index between two nearest-neighboring vertices of a network is measured by a biased Brown- ian particle which moves on the network, and it is used by an agglomerative hierarchical algorithm to identify the community structure of the network.
Lecture notes in computer scienceOn the Spectrum and Structure of Internet Topology Graphs
90 Citations2002Danica Vukadinović Greetham, Polly Huang +1 more
This paper finds that the normalized Laplacian spectrum of a graphpro vides a concise fingerprint of the corresponding network topology, and relates this multiplicity to the sizes of certain subgraphs and obtains a new structural classification of the nodes in the AS graphs, which is also plausible in networking terms.
Lecture notes in computational science and engineeringComputation of Essential Molecular Dynamics by Subdivision Techniques
61 Citations1999Peter Deuflhard, Michael Dellnitz +2 more
The paper suggests the direct computation of these objects via eigenmodes of the associated Frobenius-Perron operator by means of a multilevel subdivision algorithm.
Multiscale Modeling and SimulationConditional Expectations and Renormalization
58 Citations2003Alexandre J. Chorin
This work addresses the problem of actually finding these conditional expectations in the Hamiltonian case, and starts from Hald's observation that if the full system is Hamiltonian, then so is the reduced system whose right-hand sides are conditional expectations.
Communications on Pure and Applied MathematicsUnresolved computation and optimal predictions
44 Citations1999Alexandre J. Chorin, Anton P. Kast +1 more
Lecture notes in computer scienceCommunities Detection in Large Networks
27 Citations2004Andrea Capocci, Vito D. P. Servedio +2 more
An algorithm to detect community structure in complex networks based on spectral methods and takes into account weights and links orientations is developed, which proves to be successful both in clustering words, and in uncovering mental association patterns.