Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
arXiv:1502.04381 · doi:10.1109/TNSE.2015.2391998
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.
Extended version of arXiv:0812.1770, 'Laplacian Dynamics and Multiscale Modular Structure in Networks', by the same authors, with new content; published in Transactions on Network Science and Engineering; 16 pages; 11 figs
References in corpus (18)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Benchmark graphs for testing community detection algorithms
- Hierarchical structure and the prediction of missing links in networks
- Statistical Mechanics of Community Detection
- Community structure in directed networks
- Extracting the hierarchical organization of complex systems
- Analysis of the structure of complex networks at different resolution levels
- Narrow scope for resolution-limit-free community detection
- Robustness of community structure in networks
- Size reduction of complex networks preserving modularity
- Spectral centrality measures in complex networks
- Majority Model on a network with communities
- Synchronization and modularity in complex networks
- Maximal entropy random walk in community finding
- Modular networks with hierarchical organization: The dynamical implications of complex structure