Generalized Markov stability of network communities
arXiv:1904.09877 · doi:10.1103/PhysRevE.101.052301
Abstract
We address the problem of community detection in networks by introducing a general definition of Markov stability, based on the difference between the probability fluxes of a Markov chain on the network at different time scales. The specific implementation of the quality function and the resulting optimal community structure thus become dependent both on the type of Markov process and on the specific Markov times considered. For instance, if we use a natural Markov chain dynamics and discount its stationary distribution -- that is, we take as reference process the dynamics at infinite time -- we obtain the standard formulation of the Markov stability. Notably, the possibility to use finite-time transition probabilities to define the reference process naturally allows detecting communities at different resolutions, without the need to consider a continuous-time Markov chain in the small time limit. The main advantage of our general formulation of Markov stability based on dynamical flows is that we work with lumped Markov chains on network partitions, having the same stationary distribution of the original process. In this way the form of the quality function becomes invariant under partitioning, leading to a self-consistent definition of community structures at different aggregation scales.
References in corpus (45)
- Fast unfolding of communities in large networks
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Critical phenomena in complex networks
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Finding statistically significant communities in networks
- The map equation
- Random walks and diffusion on networks
- Line Graphs, Link Partitions and Overlapping Communities
- The ground truth about metadata and community detection in networks
- Analysis of the structure of complex networks at different resolution levels
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- The Statistical Physics of Real-World Networks
- Narrow scope for resolution-limit-free community detection
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Community detection in networks: Structural communities versus ground truth
- Localization of maximal entropy random walk
- LinkRank: Finding communities in directed networks
- The many facets of community detection in complex networks
- Significant Scales in Community Structure
- Deciphering Network Community Structure by Surprise
- Detecting communities using asymptotical Surprise
- Ranking and clustering of nodes in networks with smart teleportation
- Surprise maximization reveals the community structure of complex networks
- Exploring the limits of community detection strategies in complex networks
- Finding and testing network communities by lumped Markov chains
- A New Metric for Quality of Network Community Structure
- Efficient community detection of network flows for varying Markov times and bipartite networks
- Topologically biased random walk with application for community finding in networks
- Using higher-order Markov models to reveal flow-based communities in networks
- The Grand Canonical ensemble of weighted networks
- Maximal entropy random walk in community finding
- Thermodynamics of the Minimum Description Length on Community Detection