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

The problem

In today’s connected world, pressing problems call for efficient mapping and modeling of flow pathways – for example how information, people, and different species move through social and biological systems. To understand and mitigate seasonal outbreaks, range shifts of species, and other important organizational phenomena of complex systems, researchers across the sciences use tools from network science.

Today researchers rely on one-step models of flows on networks. However, this conventional approach ignores that the flow direction often depends on more than a single step, that is, where the flows come from. Recent evidence suggests that such higher-order information about real flow pathways is critical for capturing all-important phenomena in the dynamics and function of the system. This evidence exposes a shortcoming of conventional approaches and raises a major scientific question: How can we comprehend the higher-order effects of flow pathways in a barrage of data to understand the continuously changing organization of social and biological systems?

The solution

To comprehend the higher-order effects,  Rosvall et al. 2014 introduced so-called memory networks in which the direction of flows depends on the weights of the outgoing links and, importantly, where the flows come from. With the memory networks, they were able to investigate the higher-order effects on three common network science applications: disease spreading, node ranking, and community detection.

In various systems, from email communication and journal citations to patient movements and air travel, they found that capturing higher-order effects have important consequences. For example, memory networks reveal system organizations that better correspond to actual structures, including increased return flows that confine flows in smaller and more overlapping groups. Previously, researchers have tried to reveal such structures with heuristic algorithms, but the new approach uses more data rather than additional assumptions.

Researchers throughout the sciences should find the methods available on http://www.mapequation.org useful for analyzing increasingly available pathway data.

Read the original paper

Martin Rosvall, Alcides V. Esquivel, Andrea Lancichinetti, Jevin D. West, and Renaud Lambiotte, Memory in network flows and its effects on spreading dynamics and community detection, Nature Comm. 5, 4630 (2014)