Using higher-order Markov models to reveal flow-based communities in networks

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.

12 pages, 6 figures - 2 minor corrections

References in corpus (10)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Mitigation of infectious disease at school: targeted class closure vs school closure
• 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