Memory in Network Flows and Its Effects on Community Detection, Ranking, and Spreading

When: Friday, November 15, 2013 at 3:00 pm
Where: DA 5th fl
Speaker: Andrea Lancichinetti
Organization: Department of Chemical and Biological Engineering, Northewestern University
Sponsor: MoBS Lab

It is a paradigm to capture the spread of information and disease with random flow on networks. This conventional first-order Markov approach ignores a potentially important feature of the dynamics: where flow moves to may depend on where it comes from. We analyzed multi-step pathways from different systems and show that ignoring the effects of second-order Markov dynamics has some important consequences for community detection and ranking, but only marginal consequences for disease spreading through air travel. However, when focusing on the travel patterns themselves, we observed that random flow on networks understates the effect of communities and exaggerates the effect of highly connected nodes. For example, capturing dyanmics with a second-order Markov model allows us to differentiate airport hubs from popular destinations and reveal actual travel patterns in air traffic, as well as to uncover multidisciplinary journals and ranking that favor specialized 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.