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

doi:10.1088/1674-1056/abb302

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.

Keywords: temporal network shortest path information spreading

Received: 14 May 2020
Revised: 20 July 2020
Accepted manuscript online: 27 August 2020

PACS:	89.75.Hc	(Networks and genealogical trees)
	87.19.X-	(Diseases)
	87.23.Ge	(Dynamics of social systems)

Fund: 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).

Corresponding Authors: ^†Corresponding author. E-mail: wwzqbx@hotmail.com

Cite this article:

Yixin Ma(马一心), Xiaoyu Xue(薛潇雨), Meng Cai(蔡萌), and Wei Wang(王伟) Shortest path of temporal networks: An information spreading-based approach 2020 Chin. Phys. B 29 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)

[1]	Topological phase transition in network spreading Fuzhong Nian(年福忠) and Xia Zhang(张霞). Chin. Phys. B, 2023, 32(3): 038901.
[2]	A novel similarity measure for mining missing links in long-path networks Yijun Ran(冉义军), Tianyu Liu(刘天宇), Tao Jia(贾韬), and Xiao-Ke Xu(许小可). Chin. Phys. B, 2022, 31(6): 068902.
[3]	Quantum intelligence on protein folding pathways Wen-Wen Mao(毛雯雯), Li-Hua Lv(吕丽花), Yong-Yun Ji(季永运), You-Quan Li(李有泉). Chin. Phys. B, 2020, 29(1): 018702.
[4]	Traffic resource allocation for complex networks Ling Xiang (凌翔), Hu Mao-Bin (胡茂彬), Long Jian-Cheng (龙建成), Ding Jian-Xun (丁建勋), Shi Qin (石琴). Chin. Phys. B, 2013, 22(1): 018904.
[5]	A self-organizing shortest path finding strategy on complex networks Shen Yi(沈毅), Pei Wen-Jiang(裴文江), Wang Kai(王开), and Wang Shao-Ping(王少平). Chin. Phys. B, 2009, 18(9): 3783-3789.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

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

Cite this article:

Online attention