Using higher-order Markov models to reveal flow-based communities in networks
arXiv:1601.03516 · doi:10.1038/srep23194
Abstract
Complex systems made of interacting elements are commonly abstracted as networks, in which nodes are associated with dynamic state variables, whose evolution is driven by interactions mediated by the edges. Markov processes have been the prevailing paradigm to model such a network-based dynamics, for instance in the form of random walks or other types of diffusions. Despite the success of this modelling perspective for numerous applications, it represents an over-simplification of several real-world systems. Importantly, simple Markov models lack memory in their dynamics, an assumption often not realistic in practice. Here, we explore possibilities to enrich the system description by means of second-order Markov models, exploiting empirical pathway information. We focus on the problem of community detection and show that standard network algorithms can be generalized in order to extract novel temporal information about the system under investigation. We also apply our methodology to temporal networks, where we can uncover communities shaped by the temporal correlations in the system. Finally, we discuss relations of the framework of second order Markov processes and the recently proposed formalism of using non-backtracking matrices for community detection.
arXiv comment12 pages, 6 figures - 2 minor corrections
References in corpus (29)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Multilayer Networks
- Resolution limit in community detection
- Temporal Networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Stochastic blockmodels and community structure in networks
- Link communities reveal multiscale complexity in networks
- The performance of modularity maximization in practical contexts
- High-resolution measurements of face-to-face contact patterns in a primary school
- Spectral redemption: clustering sparse networks
- Line Graphs, Link Partitions and Overlapping Communities
- Detecting fuzzy community structures in complex networks with a Potts model
- Spectral methods for network community detection and graph partitioning
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Memory in network flows and its effects on spreading dynamics and community detection
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Mitigation of infectious disease at school: targeted class closure vs school closure
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Diffusion on networked systems is a question of time or structure
- Ranking and clustering of nodes in networks with smart teleportation
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- The stability of a graph partition: A dynamics-based framework for community detection
- Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
- Exploring Temporal Networks with Greedy Walks
- Imperfect spreading on temporal networks
Cited by in corpus (14)
- Random walks and diffusion on networks
- Fundamental structures of dynamic social networks
- The many facets of community detection in complex networks
- Flow-based network analysis of the Caenorhabditis elegans connectome
- Multilayer Network Science: from Cells to Societies
- Effects of memory on spreading processes in non-Markovian temporal networks
- Different approaches to community detection
- Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
- Higher-order models capture changes in controllability of temporal networks
- Measuring dynamical systems on directed hyper-graphs
- Generalized Markov stability of network communities
- Structured networks and coarse-grained descriptions: a dynamical perspective
- Entrograms and coarse graining of dynamics on complex networks
- Counting Causal Paths in Big Times Series Data on Networks