Shortest path of temporal networks: An information spreading-based approach

doi:10.1088/1674-1056/abb302

中国物理B ›› 2020, Vol. 29 ›› Issue (12): 128902-.doi: 10.1088/1674-1056/abb302

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇

收稿日期:2020-05-14 修回日期:2020-07-20 接受日期:2020-08-27 出版日期:2020-12-01 发布日期:2020-12-02

Shortest path of temporal networks: An information spreading-based approach

Yixin Ma(马一心)^1,2, Xiaoyu Xue(薛潇雨)^1,2, Meng Cai(蔡萌)³, and Wei Wang(王伟)^2,†

¹ College of Cybersecurity, Sichuan University, Chengdu 610065, China; ² Cybersecurity Research Institute, Sichuan University, Chengdu 610065, China; ³ School of Humanities and Social Sciences, Xi'an Jiaotong University, Xi'an 710049, China

Received:2020-05-14 Revised:2020-07-20 Accepted:2020-08-27 Online:2020-12-01 Published:2020-12-02
Contact: ^†Corresponding author. E-mail: wwzqbx@hotmail.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grant No. 61903266), China Postdoctoral Science Foundation (Grant No. 2018M631073), China Postdoctoral Science Special Foundation (Grant No. 2019T120829), the Fundamental Research Funds for the Central Universities, China, and Sichuan Science and Technology Program, China (Grant No. 20YYJC4001).

摘要/Abstract

Abstract: The shortest path is a widely studied network science problem and has attracted great attention. Nevertheless, it draws little attention in temporal networks, in which temporal edges determine information dissemination. In this paper, we propose an information spreading-based method to calculate the shortest paths distribution in temporal networks. We verify our method on both artificial and real-world temporal networks and obtain a good agreement. We further generalize our method to identify influential nodes and found an effective method. Finally, we verify the influential nodes identifying method on four networks.

Key words: temporal network, shortest path, information spreading

中图分类号: (Networks and genealogical trees)

89.75.Hc

87.19.X- (Diseases) 87.23.Ge (Dynamics of social systems)

. [J]. 中国物理B, 2020, 29(12): 128902-.

Yixin Ma(马一心), Xiaoyu Xue(薛潇雨), Meng Cai(蔡萌), and Wei Wang(王伟). Shortest path of temporal networks: An information spreading-based approach[J]. Chin. Phys. B, 2020, 29(12): 128902-.

参考文献

[1] Newman M E J 2003 SIAM Rev. Soc. Ind. Appl. Math. 45 167 DOI: 10.1137/S003614450342480
[2] Hufnagel L, Brockmann D and Geisel T 2004 Proc. Natl. Acad. Sci. India Sect. B Biol. Sci. 101 15124 DOI: 10.1073/pnas.0308344101
[3] Hidalgo C, Klinger B, Barabasi A L and Hausmann R 2007 Bull. Am. Phys. Soc. 52 No. 1 http://meetings.aps.org/link/BAPS.2007.MAR.A22.6
[4] Liljeros F, Edling C R, Amaral L A N, Stanley H E and Åberg Y Nature 411 907 DOI: 10.1038/350821402001
[5] Cohen R and Havlin S2010 Complex networks: structure, robustness and function (Cambridge: Cambridge University Press)
[6] Newman M2018 Networks (Oxford: Oxford University Press)
[7] Holme P and Saramäki J Phys. Rep. 519 97 DOI: 10.1016/j.physrep.2012.03.0012012
[8] Sekara V, Stopczynski A and Lehmann S Proc. Natl. Acad. Sci. USA 113 9977 DOI: 10.1073/pnas.16028031132016
[9] Stopczynski A, Sekara V, Sapiezynski P, Cuttone A, Madsen M M, Larsen J E and Lehmann S 2014 PloS one 9 DOI: 10.1371/journal.pone.0095978
[10] Casteigts A, Flocchini P, Quattrociocchi W and Santoro N 2012 International Conference on Ad-Hoc Networks and Wireless 27 387 DOI: 10.1080/17445760.2012.668546
[11] Koher A, Lentz H HK, Hövel P and Sokolov I M 2016 PloS One 11 DOI: 10.1371/journal.pone.0151209
[12] Valdano E, Ferreri L, Poletto C and Colizza V 2015 Phys. Rev. X 5 021005 DOI: 10.1103/PhysRevX.5.021005
[13] Chakrabarti D, Wang Y, Wang C, Leskovec J and Faloutsos C 2008 ACM Trans. Inf. Syst. Secur. 10 1 DOI: 10.1145/1284680.1284681
[14] Mieghem P V, Omic J and Kooij R IEEE ACM Trans. Netw. 17 1 DOI: 10.1109/TNET.2008.9256232008
[15] Wang Y, Chakrabarti D, Wang C,Faloutsos C 2003 Proceedings of 22nd International Symposium on Reliable Distributed Systems 25 DOI: 10.1109/RELDIS.2003.1238052
[16] Youssef M and Scoglio C J. Theor. Biol. 283 136 DOI: 10.1016/j.jtbi.2011.05.0292011
[17] Koher A, Lentz H H K, Gleeson J P and Hövel P 2019 Phys. Rev. X 9 031017 DOI: 10.1103/PhysRevX.9.031017
[18] Karrer B and Newman M EJ Phys. Rev. E 82 016101 DOI: 10.1103/PhysRevE.82.0161012010
[19] Lokhov A Y, Mèzard M, Ohta H and Zdeborová L Phys. Rev. E 90 012801 DOI: 10.1103/PhysRevE.90.0128012014
[20] Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X and Zhang Y C Phys. Rep. 651 1 DOI: 10.1016/j.physrep.2016.07.0022016
[21] Zhan X X, Liu C, Zhou G, Zhang Z K, Sun G Q, Zhu J J and Jin Z 2018 Appl. Math. Comput. 332 437 DOI: 10.1016/j.amc.2018.03.050
[22] Kan J Q and Zhang H F Commun. Nonlinear Sci. Numer. Simul. 44 193 DOI: 10.1016/j.cnsns.2016.08.0072017
[23] Liu C, Zhan X X, Zhang Z K, Sun G Q and Hui P M New J. Phys. 17 113045 DOI: 10.1088/1367-2630/17/11/1130452015
[24] Ma C, Chen H S, Li X, Lai Y C and Zhang H F SIAM J. Appl. Dyn. Syst. 19 124 DOI: 10.1137/19M12540402020
[25] Gong Y, Liu P, Cheng L, Chen G, Zhou Y, Zhang X and Xu W 2020 J. Flood Risk Manag. 13 e12586 DOI: 10.1111/jfr3.12586
[26] Newman M EJ, Strogatz S H and Watts D J Phys. Rev. E 64 026118 DOI: 10.1103/PhysRevE.64.0261182001
[27] Dorogovtsev S N, Mendes J F F and Samukhin A N Nucl. Phys. B 653 307 DOI: 10.1016/S0550-3213(02)01119-72003
[28] van der Hofstad R, Hooghiemstra G and Van Mieghem P 2005 Random Structures & Algorithms 27 76 DOI: 10.1002/rsa.20063
[29] van der Hofstad R and Hooghiemstra G J .Math. Phys. 49 125209 DOI: 10.1063/1.29829272008
[30] Asher E E, Sanhedrai H, Panduranga N K, Cohen R and Havlin S Phys. Rev. E 101 022313 DOI: 10.1103/PhysRevE.101.0223132020
[31] Katzav E, Nitzan M, ben Avraham D, Krapivsky P L, Kühn R, Ross N and Biham O Europhys. Lett. 111 26006 DOI: 10.1209/0295-5075/111/260062015
[32] Nitzan M, Katzav E, Kühn R and Biham O Phys. Rev. E 93 062309 DOI: 10.1103/PhysRevE.93.0623092016
[33] Dorogovtsev S N, Mendes J F, Samukhin A N and Zyuzin A Y Phys. Rev. E 78 056106 DOI: 10.1103/PhysRevE.78.0561062008
[34] Xu S, Teng C, Zhou Y, Peng J, Zhang Y and Zhang Z K Physica A 527 121267 DOI: 10.1016/j.physa.2019.1212672019
[35] Wu H, Cheng J, Huang S, Ke Y, Lu Y and Xu Y Proceedings of the VLDB Endowment 7 721 DOI: 10.14778/2732939.27329452014
[36] Qiu L Q, Yu J F, Fan X, Jia W and Gao W W IEEE Access 7 42052 DOI: 10.1109/Access.62876392019
[37] Kumar R and Calders T2017 Advances in Database Technology, EDBT 2017: Proceedings of the 20th International Conference on Extending Database Technology, March 21-24, 2017, Venice, Italy 270
[38] Chen Y C, Zhu W Y, Peng W C, Lee W C and Lee S Y 2014 ACM Trans. Intell. Syst. Technol. 5 1 DOI: 10.1145/2532549
[39] Erd\Hos P and Rènyi A1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[40] Perra N, Gon\ccalves B, Pastor-Satorras R and Vespignani A Sci. Rep. 2 469 DOI: 10.1038/srep004692012
[41] Fournet J and Barrat A 2014 PloS One 9 DOI: 10.1371/journal.pone.0107878
[42] Vanhems P, Barrat A, Cattuto C, Pinton J F, Khanafer N, Règis C, Kim B, Comte B and Voirin N 2013 PloS One 8 DOI: 10.1371/journal.pone.0073970
[43] Lokhov A Y2014 Dynamic cavity method and problems on graphs, Ph. D. Dissertation (Paris: Paris 11)

Shortest path of temporal networks: An information spreading-based approach

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Fuzhong Nian(年福忠) and Xia Zhang(张霞). Topological phase transition in network spreading[J]. 中国物理B, 2023, 32(3): 38901-038901.
[2]	Dan-Dan Zhao(赵丹丹), Wang-Xin Peng(彭王鑫), Hao Peng(彭浩), and Wei Wang(王伟). Effects of heterogeneous adoption thresholds on contact-limited social contagions[J]. 中国物理B, 2022, 31(6): 68906-068906.
[3]	Yijun Ran(冉义军), Tianyu Liu(刘天宇), Tao Jia(贾韬), and Xiao-Ke Xu(许小可). A novel similarity measure for mining missing links in long-path networks[J]. 中国物理B, 2022, 31(6): 68902-068902.
[4]	Dong-Jie Qian(钱冬杰). Explosive synchronization in a mobile network in the presence of a positive feedback mechanism[J]. 中国物理B, 2022, 31(1): 10503-010503.
[5]	Yu-Wei Yan(严玉为), Yuan Jiang(蒋沅), Rong-Bin Yu(余荣斌), Song-Qing Yang(杨松青), and Cheng Hong(洪成). Cascading failures of overload behaviors using a new coupled network model between edges[J]. 中国物理B, 2022, 31(1): 18901-018901.
[6]	Fuzhong Nian(年福忠), Jingzhou Li(李经洲), and Xin Guo(郭鑫). Evolution mechanism of Weibo top news competition[J]. 中国物理B, 2021, 30(12): 128901-128901.
[7]	Dongli Duan(段东立), Tao Chai(柴涛), Xixi Wu(武茜茜), Chengxing Wu(吴成星), Shubin Si(司书宾), and Genqing Bian(边根庆). Identification of unstable individuals in dynamic networks[J]. 中国物理B, 2021, 30(9): 90501-090501.
[8]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[9]	Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Dynamical robustness of networks based on betweenness against multi-node attack[J]. 中国物理B, 2021, 30(5): 50501-050501.
[10]	Xiao-Long Peng(彭小龙) and Yi-Dan Zhang(张译丹). Contagion dynamics on adaptive multiplex networks with awareness-dependent rewiring[J]. 中国物理B, 2021, 30(5): 58901-058901.
[11]	. [J]. 中国物理B, 2021, 30(4): 48901-.
[12]	. [J]. 中国物理B, 2020, 29(12): 128901-.
[13]	苏桂锋, 李晓温, 张小兵, 张一. Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks[J]. 中国物理B, 2020, 29(8): 88904-088904.
[14]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.
[15]	凌翔, 王晓坤, 陈俊杰, 刘冬, 朱孔金, 郭宁. Major impact of queue-rule choice on the performance of dynamic networks with limited buffer size[J]. 中国物理B, 2020, 29(1): 18901-018901.