Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
Top Cited Papers
- 1 July 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 1 (2) , 76-90
Abstract
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.Keywords
All Related Versions
Funding Information
- Belgian Programme of Interuniversity Attraction Poles
- ARC
- French Community of Belgium
- FP7
- European Commission
- FNRS
- European Commission
- EPSRC (EP/I017267/1)
This publication has 65 references indexed in Scilit:
- Markov Dynamics as a Zooming Lens for Multiscale Community Detection: Non Clique-Like Communities and the Field-of-View LimitPLOS ONE, 2012
- Finding and Testing Network Communities by Lumped Markov ChainsPLOS ONE, 2011
- Graph nodes clustering with the sigmoid commute-time kernel: A comparative studyData & Knowledge Engineering, 2009
- Mesoscopic Structure Conditions the Emergence of Cooperation on Social NetworksPLOS ONE, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Extracting the hierarchical organization of complex systemsProceedings of the National Academy of Sciences, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- On quasi-stationary distributions in absorbing continuous-time finite Markov chainsJournal of Applied Probability, 1967