The DOI matches its Crossref record; 84 of the 84 references it cites were found in a registry or an index.
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Open accessAbstract
Most methods proposed to uncover communities in complex networks rely on combinatorial graph properties. Usually an edge-counting quality function, such as modularity, is optimized over all partitions of the graph compared against a null random graph model. Here we introduce a systematic dynamical framework to design and analyze a wide variety of quality functions for community detection. The quality of a partition is measured by its Markov Stability, a time-parametrized function defined in terms of the statistical properties of a Markov process taking place on the graph. The Markov process provides a dynamical sweeping across all scales in the graph, and the time scale is an intrinsic parameter that uncovers communities at different resolutions. This dynamic-based community detection leads to a compound optimization, which favours communities of comparable centrality (as defined by the stationary distribution), and provides a unifying framework for spectral algorithms, as well as different heuristics for community detection, including versions of modularity and Potts model. Our dynamic framework creates a systematic link between different stochastic dynamics and their corresponding notions of optimal communities under distinct (node and edge) centralities. We show that the Markov Stability can be computed efficiently to find multi-scale community structure in large networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
Self-citationThe Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
SIMPSON, E. H. (1949) · Nature · doi:10.1038/163688a0 · Cited by 14,164
Finding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 2×
“Recently, there has been extensive research on the detection of communities and hierarchies in real world systems, ranging from social systems to technological and bio-chemical systems (for a review see [6]).”
BackgroundComplex networks: structure and dynamics
BOCCALETTI, S., LATORA, V, MORENO, Y., CHAVEZ, M., & HWANG, D. (2006) · Physics Reports · doi:10.1016/j.physrep.2005.10.009 · Cited by 11,010
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 2×
“ics on social networks and other kinds of consensus problems [52], [83], linearization of synchronization [3], [84] and power networks [54], among others.”
BackgroundCoordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Finding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761
Maps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Information Flow and Cooperative Control of Vehicle Formations
Fax, J. A., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834433 · Cited by 4,579
The Architecture of Complexity
Simon, H. A. (1991) · Facets of Systems Science · doi:10.1007/978-1-4899-0718-9_31 · Cited by 4,433
On Measures of Entropy and Information
Rényi, A. (1961) · Project Euclid (Cornell University) · Cited by 4,031
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
Factoring and weighting approaches to status scores and clique identification
Bonacich, P. (1972) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.1972.9989806 · Cited by 3,207
Benchmark graphs for testing community detection algorithms
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008) · Physical Review E · doi:10.1103/physreve.78.046110 · Cited by 3,051
Strogatz, S. H. (2000) · Physica D: Nonlinear Phenomena · doi:10.1016/s0167-2789(00)00094-4 · Cited by 3,051
Non-negative Matrices and Markov Chains
Seneta, E. (1981) · Springer Series in Statistics · doi:10.1007/0-387-32792-4 · Cited by 2,807
Singular Perturbation Methods in Control: Analysis and Design
Kokotović, P., Khalil, H. K., & O'Reilly, J. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971118 · Cited by 2,485
Coifman, R. R., & Lafon, S. (2006) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2006.04.006 · Cited by 2,342
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171 · cited 1×
“This relationship is particularly relevant when the network is composed of tightly-knit modules or communities [4], [5], [6], [7], [8], [9], which can lead, for instance, to partially coherent dynamics [10], [11], or to the emergence of co-operation [12] and coexistence of heterogeneous ideas in a…”
BackgroundCommunity Structure in Time-Dependent, Multiscale, and Multiplex Networks
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010) · Science · doi:10.1126/science.1184819 · Cited by 2,123
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Synchronization in Small-World Systems
Barahona, M., & Pecora, L. M. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.054101 · Cited by 1,638
Self-citationSome Unique Properties of Eigenvector Centrality
Bonacich, P. (2007) · Social Networks · doi:10.1016/j.socnet.2007.04.002 · Cited by 1,572 · cited 1×
“This will be particularly important in networks whose node eigencentrality is not fully captured by the degree centrality [62], e.”
BackgroundComparing clusterings—an information based distance
Meilă, M. (2007) · Journal of Multivariate Analysis · doi:10.1016/j.jmva.2006.11.013 · Cited by 1,546
Computing Communities in Large Networks Using Random Walks
Pons, P., & Latapy, M. (2006) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00124 · Cited by 1,501
Singular perturbation methods in control: analysis and design
(1987) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(87)90148-0 · Cited by 1,339
Community Structure in Directed Networks
Leicht, E. A., & Newman, M. E. J. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.118703 · Cited by 1,116
A First Course in Stochastic Models
Tijms, H. C. (2003) · Wiley eBooks · doi:10.1002/047001363x · Cited by 1,047
A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory
Fiedler, M. (1975) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1975.101357 · Cited by 1,042
Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
Odentrantz, J. (2000) · Technometrics · doi:10.1080/00401706.2000.10485734 · Cited by 973
Hirschman, A. (1964) · American Economic Review · Cited by 951
Performance of modularity maximization in practical contexts
Good, B. H., de Montjoye, Y.-A., & Clauset, A. (2010) · Physical Review E · doi:10.1103/physreve.81.046106 · Cited by 937
Synchronization in complex oscillator networks and smart grids
Dörfler, F., Chertkov, M., & Bullo, F. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1212134110 · Cited by 879
Synchronization Reveals Topological Scales in Complex Networks
Arenas, A., Díaz-Guilera, A., & Pérez-Vicente, C. J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.114102 · Cited by 848
λ1, Isoperimetric inequalities for graphs, and superconcentrators
Alon, N., & Milman, V. D. (1985) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(85)90092-9 · Cited by 839
Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues
Brémaud, P. (1999) · Texts in Applied Mathematics · doi:10.1007/978-1-4757-3124-8 · Cited by 781
Graph Clustering Via a Discrete Uncoupling Process
Van Dongen, S. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040608635 · Cited by 750
Diffusion Kernels on Graphs and Other Discrete Input Spaces
Kondor, R., & Lafferty, J. (2002) · Cited by 725
Energy Landscapes: Applications to Clusters, Biomolecules and Glasses
Wales, D. J. (2004) · Cited by 647
A Random Walks View of Spectral Segmentation.
Meilă, M., & Shi, J. (2001) · Cited by 623
Aggregation of Variables in Dynamic Systems
Simon, H. A., & Ando, A. (1961) · Econometrica · doi:10.2307/1909285 · Cited by 562
Aggregation of Variables in Dynamic Systems
Simon, H. A. (1977) · Boston Studies in the Philosophy of Science · doi:10.1007/978-94-010-9521-1_12 · Cited by 550
Extracting the hierarchical organization of complex systems
Sales-Pardo, M., Guimerà, R., Moreira, A. A., & Amaral, L. A. N. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0703740104 · Cited by 535
Stability of graph communities across time scales
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0903215107 · Cited by 475
Self-citationAnalysis of the structure of complex networks at different resolution levels
Arenas, A., Fernández, A., & Gómez, S. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/5/053039 · Cited by 446
Non-Negative Matrices and Markov Chains.
Isham, V., & Seneta, E. (1983) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2982031 · Cited by 439
SPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
Biggs, N. (1998) · Bulletin of the London Mathematical Society · doi:10.1112/s0024609397223611 · Cited by 433
Narrow scope for resolution-limit-free community detection
Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011) · Physical Review E · doi:10.1103/physreve.84.016114 · Cited by 353
Robustness of community structure in networks
Karrer, B., Levina, E., & Newman, M. E. J. (2008) · Physical Review E · doi:10.1103/physreve.77.046119 · Cited by 350
Laplacian Dynamics and Multiscale Modular Structure in Networks
Lambiotte, R., Delvenne, J., & Barahona, M. (2008) · doi:10.48550/arxiv.0812.1770 · Cited by 345
Self-citationSize reduction of complex networks preserving modularity
Arenas, A., Duch, J., Fernández, A., & Gómez, S. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/176 · Cited by 330
A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
Sussman, D. L., Tang, M., Fishkind, D. E., & Priebe, C. E. (2012) · Journal of the American Statistical Association · doi:10.1080/01621459.2012.699795 · Cited by 254
Multiresolution community detection for megascale networks by information-based replica correlations
Ronhovde, P., & Nussinov, Z. (2009) · Physical Review E · doi:10.1103/physreve.80.016109 · Cited by 245
On quasi-stationary distributions in absorbing continuous-time finite Markov chains
Darroch, J. N., & Seneta, E. (1967) · Journal of Applied Probability · doi:10.1017/s0021900200025341 · Cited by 241
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
Lovasz, L., & Simonovits, M. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89553 · Cited by 190
On Finding Graph Clusterings with Maximum Modularity
Brandes, U., Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., & Wagner, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74839-7_12 · Cited by 182
Finding communities in directed networks
Kim, Y., Son, S.-W., & Jeong, H. (2010) · Physical Review E · doi:10.1103/physreve.81.016103 · Cited by 172
Spectral centrality measures in complex networks
Perra, N., & Fortunato, S. (2008) · Physical Review E · doi:10.1103/physreve.78.036107 · Cited by 158
Mesoscopic Structure Conditions the Emergence of Cooperation on Social Networks
Lozano, S., Arenas, À., & Sánchez, Á. (2008) · PLoS ONE · doi:10.1371/journal.pone.0001892 · Cited by 152
Schaub, M. T., Delvenne, J., Yaliraki, S. N., & Barahona, M. (2012) · PLoS ONE · doi:10.1371/journal.pone.0032210 · Cited by 148
Self-citationMajority model on a network with communities
Lambiotte, R., Ausloos, M., & Hołyst, J. A. (2007) · Physical Review E · doi:10.1103/physreve.75.030101 · Cited by 111
Self-citationFlow graphs: Interweaving dynamics and structure
Lambiotte, R., Sinatra, R., Delvenne, J., Evans, T., Barahona, M., & Latora, V. (2011) · Physical Review E · doi:10.1103/physreve.84.017102 · Cited by 98
Self-citationCentrality measures and thermodynamic formalism for complex networks
Delvenne, J., & Libert, A.-S. (2011) · Physical Review E · doi:10.1103/physreve.83.046117 · Cited by 90
Self-citationGeneralized master equations for non-Poisson dynamics on networks
Hoffmann, T., Porter, M. A., & Lambiotte, R. (2012) · Physical Review E · doi:10.1103/physreve.86.046102 · Cited by 89
Self-citationObservability and coarse graining of consensus dynamics through the external equitable partition
O’Clery, N., Yuan, Y., Stan, G.-B. V., & Barahona, M. (2013) · Physical Review E · doi:10.1103/physreve.88.042805 · Cited by 85
Self-citationGraph nodes clustering with the sigmoid commute-time kernel: A comparative study
Yen, L., Fouss, F., Decaestecker, C., Francq, P., & Saerens, M. (2008) · Data & Knowledge Engineering · doi:10.1016/j.datak.2008.10.006 · Cited by 82
Fenn, D. J., Porter, M. A., McDonald, M., Williams, S., Johnson, N. F., & Jones, N. S. (2009) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.3184538 · Cited by 82
The Stability of a Graph Partition: A Dynamics-Based Framework for Community Detection
Delvenne, J., Schaub, M. T., Yaliraki, S. N., & Barahona, M. (2013) · Modeling and simulation in science, engineering & technology · doi:10.1007/978-1-4614-6729-8_11 · Cited by 76
Self-citationFinding and Testing Network Communities by Lumped Markov Chains
Piccardi, C. (2011) · PLoS ONE · doi:10.1371/journal.pone.0027028 · Cited by 70
Synchronization and modularity in complex networks
Arenas, À., & Dı́az-Guilera, A. (2007) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2007-00066-2 · Cited by 69
Delmotte, A., Tate, E. W., Yaliraki, S. N., & Barahona, M. (2011) · Physical Biology · doi:10.1088/1478-3975/8/5/055010 · Cited by 63
Self-citationInterest communities and flow roles in directed networks: the Twitter network of the UK riotsPreprint
Vangelov, B., Yaliraki, S. N., & Barahona, M. (2016) · Cited by 57
Self-citationDynamics On and Of Complex Networks
Ganguly, N., Mukherjee, A., & Deutsch, A. (2009) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4751-3 · Cited by 53
Barreira, L. (2012) · Universitext · doi:10.1007/978-3-642-28090-0_5 · Cited by 52
Four proofs for the Cheeger inequality and graph partition algorithms
Chung, F. (2007) · Cited by 40
MULTI-SCALE COMMUNITY DETECTION USING STABILITY AS OPTIMISATION CRITERION IN A GREEDY ALGORITHM
Martelot, E. L., & Hankin, C. (2011) · International Conference on Knowledge Discovery and Information Retrieval · doi:10.5220/0003655002160225 · Cited by 33
Maximal entropy random walk in community detection
Ochab, J. K., & Burda, Z. (2013) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2013-01730-6 · Cited by 31
Multi-scale Modularity and Dynamics in Complex Networks
Lambiotte, R. (2013) · Modeling and simulation in science, engineering & technology · doi:10.1007/978-1-4614-6729-8_7 · Cited by 14
Self-citation
Cited by
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Self-citationBetzel, R. F., & Bassett, D. S. (2017) · NeuroImage · doi:10.1016/j.neuroimage.2016.11.006 · Cited by 587
Augmented reality in support of intelligent manufacturing – A systematic literature review
Egger, J., & Masood, T. (2020) · Computers & Industrial Engineering · doi:10.1016/j.cie.2019.106195 · Cited by 391
Equivalence between modularity optimization and maximum likelihood methods for community detection
Newman, M. E. J. (2016) · Physical Review E · doi:10.1103/physreve.94.052315 · Cited by 344
Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison
De Domenico, M., & Biamonte, J. (2016) · Physical Review X · doi:10.1103/physrevx.6.041062 · Cited by 160
Metadata
- Authors
- Lambiotte, R., Delvenne, J.-C., & Barahona, M.
- Venue
- IEEE Transactions on Network Science and Engineering
- Published
- 2014-07-01
- Volume
- 1
- Issue
- 2
- Pages
- 76-90
- ISSN
- 2327-4697 (ISSN-L)
- OpenAlex
- W2008209917
- Cited by
- 398
- References
- 84
- FWCI
- 12.31
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.