title: Memory in network flows and its effects on spreading dynamics and community detection.
abstract: 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.
authors.affiliation: Integrated Science Lab, Department of Physics, Umeå University, Linnaeus va¨g 24 , SE-901 87 Umeå, Sweden.
authors.forename: Martin
authors.initials: M
authors.lastname: Rosvall
authors.affiliation: Integrated Science Lab, Department of Physics, Umeå University, Linnaeus va¨g 24 , SE-901 87 Umeå, Sweden.
authors.forename: Alcides V
authors.initials: AV
authors.lastname: Esquivel
authors.affiliation: 1] Integrated Science Lab, Department of Physics, Umeå University, Linnaeus va¨g 24 , SE-901 87 Umeå, Sweden [2] Department of Chemical and Biological Engineering, Howard Hughes Medical Institute (HHMI), Northwestern University, Evanston, Illinois 60208, USA.
authors.forename: Andrea
authors.initials: A
authors.lastname: Lancichinetti
authors.affiliation: 1] Integrated Science Lab, Department of Physics, Umeå University, Linnaeus va¨g 24 , SE-901 87 Umeå, Sweden [2] Information School, University of Washington, Seattle, Washington 98195, USA.
authors.forename: Jevin D
authors.initials: JD
authors.lastname: West
authors.affiliation: Department of Mathematics and Naxys, University of Namur, 5000 Namur, Belgium.
authors.forename: Renaud
authors.initials: R
authors.lastname: Lambiotte
mesh_terms: D000465:Algorithms; D004196:Disease Outbreaks; D004812:Epidemiologic Methods; D006801:Humans; D033181:Information Dissemination; D007257:Information Theory; D008390:Markov Chains; D015233:Models, Statistical; D011336:Probability; D014186:Transportation; D014481:United States