Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks

By Renaud Lambiotte, Jean-Charles Delvenne, Mauricio Barahona. IEEE Transactions on Network Science and Engineering, 2008

600 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/6189cfff004291a423951759fed23a57bd67d114

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Multi-scale brain networks (2016, unknown): “The clusters correspond to collections of detected partitions that are all highly similar to one another—the absence of clusters suggests that if community structure exists at different scales, then it is short-lived and possibly of less interest (Lambiotte et al., 2014).”
Community detection in networks: A user guide (2016, background): “For instance, Newman-Girvan’s modularity is a special case of a general quality function, called stability, expressing the persistence of a random walk within communities (Delvenne et al., 2010; Lambiotte et al., 2008).”
Ranking in interconnected multilayer networks reveals versatile nodes (2013, methodology): “For example, random walks have been used to rank Web pages [26] and sports teams [27], optimize searches [28], investigate the efficiency of network navigation [29, 30], characterize cyclic structures in networks [31], and coarse-grain networks to illuminate meso-scale features such as community str”
Mathematical Formulation of Multilayer Networks (2013, background): “For multiplex networks, for example, the most sensible normalization constant is typically the number of layers L.”