Memory in network flows and its effects on spreading dynamics and community detection

By Martin Rosvall, Alcides Viamontes Esquivel, Andrea Lancichinetti, Jevin D. West, Renaud Lambiotte. 2013

392 citations recorded by the source corpus.

Random walks on networks is the standard tool for modelling spreading processes in social and biological systems. This first-order Markov approach is used in conventional community detection, ranking and spreading analysis, although it ignores a potentially important feature of the dynamics: where flow moves to may depend on where it comes from. Here we analyse pathways from different systems, and although we only observe marginal consequences for disease spreading, we show that ignoring the effects of second-order Markov dynamics has important consequences for community detection, ranking and information spreading. For example, capturing dynamics with a second-order Markov model allows us to reveal actual travel patterns in air traffic and to uncover multidisciplinary journals in scientific communication. These findings were achieved only by using more available data and making no additional assumptions, and therefore suggest that accounting for higher-order memory in network flows can help us better understand how real systems are organized and function. Random walks are standard tools for modelling dynamics in networks but usually neglect the possibility that the next step may depend on the previous ones. Rosvall et al. study the paths taken in various systems and show that memory effects play an important role and can uncover informative organization.

Subfields: Statistical and Nonlinear Physics, Transportation

How researchers see this paper

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

In Statistical and Nonlinear Physics

In Transportation

Citations in the corpus

Community detection in networks: A user guide (2016, background): “The map equation has also been extended to random walks whose transition probabilities depend on earlier steps too (higher-order Markov dynamics) [44,45], retaining memory of the (recent) past.”
Random walks and diffusion on networks (2016, background): “In [250], Rosvall et al.”
Simplicial closure and higher-order link prediction (2018, methodology): “This is in sharp contrast to other notions of “higher-order models” generalizing graph data, such as multiplex networks (17) and higher-order Markov chain models (18, 19), which are successful but still rooted in a pairwise representation paradigm.”