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

被引:268
作者
Rosvall, Martin [1 ]
Esquivel, Alcides V. [1 ]
Lancichinetti, Andrea [1 ,2 ]
West, Jevin D. [1 ,3 ]
Lambiotte, Renaud [4 ]
机构
[1] Umea Univ, Dept Phys, Integrated Sci Lab, SE-90187 Umea, Sweden
[2] Northwestern Univ, Howard Hughes Med Inst, Dept Chem & Biol Engn, Evanston, IL 60208 USA
[3] Univ Washington, Informat Sch, Seattle, WA 98195 USA
[4] Univ Namur, Dept Math & Naxys, B-5000 Namur, Belgium
基金
瑞典研究理事会;
关键词
COMPLEX NETWORKS; HUMAN MOBILITY; MOVEMENT; MODELS; IMPACT;
D O I
10.1038/ncomms5630
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
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.
引用
收藏
页数:13
相关论文
共 63 条
[1]   Link communities reveal multiscale complexity in networks [J].
Ahn, Yong-Yeol ;
Bagrow, James P. ;
Lehmann, Sune .
NATURE, 2010, 466 (7307) :761-U11
[2]  
[Anonymous], 2012, Proceedings of the International Conference on World Wide Web, DOI DOI 10.1145/2187836.2187919
[3]  
[Anonymous], 2003, Internet Mathematics
[4]  
[Anonymous], 2011, PROC 4 ACM INT C WEB, DOI DOI 10.1145/1935826.1935914
[5]   Network discovery by generalized random walks [J].
Asztalos, A. ;
Toroczkai, Z. .
EPL, 2010, 92 (05)
[6]   Phase transitions in contagion processes mediated by recurrent mobility patterns [J].
Balcan, Duygu ;
Vespignani, Alessandro .
NATURE PHYSICS, 2011, 7 (07) :581-586
[7]   Multiscale mobility networks and the spatial spreading of infectious diseases [J].
Balcan, Duygu ;
Colizza, Vittoria ;
Goncalves, Bruno ;
Hu, Hao ;
Ramasco, Jose J. ;
Vespignani, Alessandro .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2009, 106 (51) :21484-21489
[8]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[9]   The architecture of complex weighted networks [J].
Barrat, A ;
Barthélemy, M ;
Pastor-Satorras, R ;
Vespignani, A .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2004, 101 (11) :3747-3752
[10]   Natural Human Mobility Patterns and Spatial Spread of Infectious Diseases [J].
Belik, Vitaly ;
Geisel, Theo ;
Brockmann, Dirk .
PHYSICAL REVIEW X, 2011, 1 (01) :1-5