Identify information sources with different start times in complex networks based on sparse observers

doi:10.1088/1674-1056/ad7af4

Abstract The dissemination of information across various locations is an ubiquitous occurrence, however, prevalent methodologies for multi-source identification frequently overlook the fact that sources may initiate dissemination at distinct initial moments. Although there are many research results of multi-source identification, the challenge of locating sources with varying initiation times using a limited subset of observational nodes remains unresolved. In this study, we provide the backward spread tree theorem and source centrality theorem, and develop a backward spread centrality algorithm to identify all the information sources that trigger the spread at different start times. The proposed algorithm does not require prior knowledge of the number of sources, however, it can estimate both the initial spread moment and the spread duration. The core concept of this algorithm involves inferring suspected sources through source centrality theorem and locating the source from the suspected sources with linear programming. Extensive experiments from synthetic and real network simulation corroborate the superiority of our method in terms of both efficacy and efficiency. Furthermore, we find that our method maintains robustness irrespective of the number of sources and the average degree of network. Compared with classical and state-of-the art source identification methods, our method generally improves the AUROC value by 0.1 to 0.2.

Keywords: complex networks information spread source identification backward spread centricity

Received: 14 May 2024
Revised: 13 August 2024
Accepted manuscript online: 14 September 2024

PACS:	89.75.-k	(Complex systems)
	87.23.Ge	(Dynamics of social systems)
	89.75.Fb	(Structures and organization in complex systems)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 62103375, 62006106, 61877055, and 62171413), the Philosophy and Social Science Planning Project of Zhejinag Province, China (Grant No. 22NDJC009Z), the Education Ministry Humanities and Social Science Foundation of China (Grant No. 19YJCZH056), and the Natural Science Foundation of Zhejiang Province, China (Grant Nos. LY23F030003, LY22F030006, and LQ21F020005).

Corresponding Authors: Zhao-Long Hu
E-mail: huzhaolong@zjnu.edu.cn

Cite this article:

Yuan-Zhang Deng(邓元璋), Zhao-Long Hu(胡兆龙), Feilong Lin(林飞龙), Chang-Bing Tang(唐长兵), Hui Wang(王晖), and Yi-Zhen Huang(黄宜真) Identify information sources with different start times in complex networks based on sparse observers 2024 Chin. Phys. B 33 118901

[1] Vosoughi S, Roy D and Sinan Aral S 2018 Science 359 1146
[2] Zarin R, Khaliq H, Khan A, Khan D, Akgül D and Humphries U W 2022 Results Phys. 33 105130
[3] Pastor-Satorras R, Castellano C, Van Mieghem P and Vespignani A 2015 Rev. Mod. Phys. 87 925
[4] Morone F and Makse H A 2015 Nature 524 65
[5] Su Z, Chen L, Ai J, Zheng Y Y and Bie N 2024 Chin. Phys. B 33 058901
[6] Xie M, Zhan X X, Liu C and Zhang Z K 2023 Inf. Process. Manag. 60 103161
[7] Hu Z L, Liu J G, Yang G Y and Ren Z M 2014 Europhys. Lett. 106 18002
[8] Shao Y, Chen L, Chen Y, Liu W and Dai C 2023 Inf. Sci. 635 375
[9] Yang P L, Zhao L J, Dong C, Xu G X and Zhou L X 2023 Chin. Phys. B 32 058901
[10] Liu C and Zhang Z K 2014 Commun. Nonlinear Sci. 19 896
[11] Gao L, Wang W, Pan L, Tang M and Zhang H 2016 Sci. Rep. 6 1
[12] Shah D and Zaman T 2010 ACM SIGMETRICS Perform. Eval. Rev. 38 203
[13] Xu X, Qian T, Xiao Z, Zhang N, Wu J and Zhou F 2024 Expert Syst. Appl. 238 122028
[14] Comin C H and Fontoura Costa L 2011 Phys. Rev. E 84 056105
[15] Shi C, Zhang Q and Chu T 2022 Chin. Phys. B 31 070203
[16] Luo W, Tay W P and Leng M 2013 IEEE Trans. Signal Process. 61 2850
[17] Louni A and Subbalakshmi K 2018 IEEE Trans. Comput. Soc. Syst. 5 335
[18] Chen Z, Zhu K and Ying L 2016 IEEE Trans. Netw. Sci. Eng. 3 17
[19] Liu Y, Li W, Yang C and Wang J 2022 Sci. Rep. 12 5467
[20] Zhu P, Cheng L, Gao C, Wang Z and Li X 2022 IEEE Trans. Netw. Sci. Eng. 9 1853
[21] Yuan S, Liu W, Zeng H and Wang C 2023 Europhys. Lett. 141 60001
[22] Pedro C P, Patrick T and Martin V 2012 Phys. Rev. Lett. 109 068702
[23] Zhang X, Zhang Y, Lv T and Yin Y 2016 Physica A 442 100
[24] Hu Z L, Han X, Lai Y C and Wang W X 2017 Roy. Soc. Open Sci. 4 170091
[25] Fu L, Shen Z, Wang W X, Fan Y and Di Z 2016 Europhys. Lett. 113 18006
[26] Hu Z L, Shen Z, Han J, Peng H, Lu J F, Jia R, Zhu X B and Zhao D 2019 Physica A 527 121262
[27] Wang H J, Zhang F F and Sun K J 2021 Phys. Lett. A 393 127184
[28] Hu Z L, Han J, Peng H, Lu J F, Zhu X B, Jia R and Li M 2022 IEEE Trans. Netw. Sci. Eng. 9 3515
[29] Robert P, Lu X, Krzysztof S, Szymański B K and Hołyst J A 2018 Sci. Rep. 8 2508
[30] Tang W, Ji F and Tay W P 2018 IEEE Trans. Inf. Foren. Sec. 13 3035
[31] Wang C, Man Z, Yuan S and Zhang G 2022 Europhys. Lett. 139 21002
[32] Wang H J, Hu Z L, Tao L, Shao S and Wang S Z 2023 Sci. Rep. 13 5692
[33] Yang F, Li C, Peng Y, Liu J, Yao Y, Wen J and Yang S 2023 Soft Comput. 27 16059
[34] Wang H J, Hu Z L, Shao S Y, Zhang F F and Tao L 2024 Phys. Rev. E 109 014311
[35] Hu Z L, Wang H J, Sun L, Tang C B and Li M 2024 Expert Syst. Appl. 256 124946
[36] Ma Z W, Wang H J, Hu Z L, Zhu X B, Huang Y Z and Huang F L 2024 Phys. Lett. A 523 129772
[37] Yin F, Shao X, Ji M and Wu J 2021 J. Med. Int. Res. 23 e25734
[38] Nsoesie E O, Cesare N, Müller M and Ozonoff A 2020 J. Med. Int. Res. 22 e24425
[39] Ji F, Tay W P and Varshney L R 2017 IEEE Trans. Signal Process. 65 2517
[40] Zhu K and Ying L 2014 IEEE/ACM Trans. Netw. 24 408
[41] Prakash B A, Vreeken J and Faloutsos C 2014 Knowl. Inf. Syst. 38 35
[42] Jiang J, Wen S, Yu S, Xiang Y and Zhou W 2015 IEEE Trans. Inf. Foren. Sec. 10 2616
[43] Ali S S, Anwar T, Rastogi A and Rizvi S A M 2019 Proceedings of the 28th ACM International Conference on Information and Knowledge Management, November 3-7, 2019, Beijing, China, p. 891
[44] Lokhov A Y, Mézard M, Ohta H and Zdeborová L 2014 Phys. Rev. E 90 012801
[45] Altarelli F, Braunstein A, Alejandro L D, Lage-Castellanos A and Zecchina R 2014 Phys. Rev. Lett. 112 118701
[46] Wang Z, Wang C, Pei J and Ye X 2017 Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, p. 217
[47] Peng S L, Wang H J, Peng H, Zhu X B, Li X, Han J, Zhao D and Hu Z L 2023 Chaos 33 083125
[48] Cheng L, Li X, Han Z, Luo T, Ma L and Zhu P 2022 Chaos, Solitons and Fractals 159 112139
[49] Shen Z, Cao S, Wang W X, Di Z and Stanley H E 2016 Phys. Rev. E 93 032301
[50] Paluch R, Gajewski L G, Hołyst J A and Szymanski B K 2020 Future Gener. Comput. Syst. 112 1070
[51] Hu Z L, Shen Z, Cao S, Podobnik B, Yang B, Wang W X and Lai Y C 2018 Sci. Rep. 8 2685
[52] Hu Z L, Wang L and Tang C B 2019 Chaos 29 063117
[53] Spinelli B, Celis L E and Thiran P 2019 IEEE Trans. Netw. Sci. Eng. 6 86
[54] Wang H J and Sun K J 2020 Europhys. Lett. 131 48001
[55] Gajewski Ł, Paluch R, Suchecki K, Sulik A, Szymanski B K and Hołyst J A 2022 Sci. Rep. 12 5079
[56] Ma Z W, Sun L, Ding Z G, Huang Y Z and Hu Z L 2024 Chin. Phys. B 33 028902
[57] Gajewski Ł, Szymanski B K and Hołyst J A 2019 Physica A 519 34
[58] Hu Z L, Shen Z, Tang C B, Xie B B and Lu J F 2018 Phys. Lett. A 382 931
[59] Hanley J A and McNeil B J 1982 Radiology 143 29
[60] Prasse B and Van Mieghem P 2020 IEEE Trans. Netw. Sci. Eng. 7 2755
[61] Ma C, Chen H S, Li X, Lai Y C and Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 124
[62] Pech R, Hao D, Lee Y L, Yuan Y and Zhou T 2019 Physica A 528 121319
[63] Ahmad I, Akhtar M U, Noor S and Shahnaz A 2020 Sci. Rep. 10 364
[64] Erdos P and Rényi A 1960 Publ. Math. Inst. Hungarian Acad. Sci. 5 17
[65] Barabási A and Albert R 1999 Science 286 509
[66] Guimera R, Danon L, Diaz-Guilera A, Giralt F and Arenas A 2003 Phys. Rev. E 68 065103
[67] Rossi R and Ahmed N 2015 Proceedings of the AAAI conference on artificial intelligence, January 25-30, 2015, Austin, Texas, USA, p. 4292
[68] Leskovec J, Huttenlocher D and Kleinberg J 2010 Proceedings of the SIGCHI conference on human factors in computing systems, April 10- 15, 2010, Atlanta, Georgia, USA, p. 1361
[69] Adamic L A and Glance N 2005 Proceedings of the 3rd international workshop on Link discovery, August 21-25, 2005, New York, USA, p. 36
[70] Newman M E 2002 Phys. Rev. Lett. 89 208701
[71] Holme P and Saramäki J 2012 Phys. Rep. 519 97
[72] Jiang J, Wen S, Yu S, Xiang Y and Zhou W 2018 IEEE Trans. Depend. Sec. Comput. 15 166
[73] Chai Y, Wang Y and Zhu L 2021 IEEE Trans. Inf. Foren. Sec. 16 2621
[74] Zhang H, Qian S, Fang Q and Xu C 2020 IEEE Trans. Multimedia 23 4441
[75] Ling C, Jiang J, Wang J and Liang Z 2022 Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, August 14-18, 2022, Washington, DC, USA, p. 1010
[76] Wan P, Wang X, Pang G, Wang L and Min G 2023 Expert Syst. Appl. 213 119239

[1]	Dynamic analysis of major public health emergency transmission considering the dual-layer coupling of community-resident complex networks Peng Yang(杨鹏), Ruguo Fan(范如国), Yibo Wang(王奕博), and Yingqing Zhang(张应青). Chin. Phys. B, 2024, 33(7): 070206.
[2]	Identifying influential spreaders in complex networks based on density entropy and community structure Zhan Su(苏湛), Lei Chen(陈磊), Jun Ai(艾均), Yu-Yu Zheng(郑雨语), and Na Bie(别娜). Chin. Phys. B, 2024, 33(5): 058901.
[3]	Prediction of collapse process and tipping points for mutualistic and competitive networks with k-core method Dongli Duan(段东立), Feifei Bi(毕菲菲), Sifan Li(李思凡), Chengxing Wu(吴成星), Changchun Lv(吕长春), and Zhiqiang Cai(蔡志强). Chin. Phys. B, 2024, 33(5): 050201.
[4]	Effects of individual heterogeneity on social contagions Fu-Zhong Nian(年福忠) and Yu Yang(杨宇). Chin. Phys. B, 2024, 33(5): 058705.
[5]	A multilayer network diffusion-based model for reviewer recommendation Yiwei Huang(黄羿炜), Shuqi Xu(徐舒琪), Shimin Cai(蔡世民), and Linyuan Lü(吕琳媛). Chin. Phys. B, 2024, 33(3): 038901.
[6]	Source localization in signed networks with effective distance Zhi-Wei Ma(马志伟), Lei Sun(孙蕾), Zhi-Guo Ding(丁智国), Yi-Zhen Huang(黄宜真), and Zhao-Long Hu(胡兆龙). Chin. Phys. B, 2024, 33(2): 028902.
[7]	Important edge identification in complex networks based on local and global features Jia-Hui Song(宋家辉). Chin. Phys. B, 2023, 32(9): 098901.
[8]	Self-similarity of complex networks under centrality-based node removal strategy Dan Chen(陈单), Defu Cai(蔡德福), and Housheng Su(苏厚胜). Chin. Phys. B, 2023, 32(9): 098903.
[9]	Stability and multistability of synchronization in networks of coupled phase oscillators Yun Zhai(翟云), Xuan Wang(王璇), Jinghua Xiao(肖井华), and Zhigang Zheng(郑志刚). Chin. Phys. B, 2023, 32(6): 060503.
[10]	Identification of key recovering node for spatial networks Zijian Yan(严子健), Yongxiang Xia(夏永祥), Lijun Guo(郭丽君), Lingzhe Zhu(祝令哲), Yuanyuan Liang(梁圆圆), and Haicheng Tu(涂海程). Chin. Phys. B, 2023, 32(6): 068901.
[11]	AG-GATCN: A novel method for predicting essential proteins Peishi Yang(杨培实), Pengli Lu(卢鹏丽), and Teng Zhang(张腾). Chin. Phys. B, 2023, 32(5): 058902.
[12]	Topological phase transition in network spreading Fuzhong Nian(年福忠) and Xia Zhang(张霞). Chin. Phys. B, 2023, 32(3): 038901.
[13]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[14]	SLGC: Identifying influential nodes in complex networks from the perspectives of self-centrality, local centrality, and global centrality Da Ai(艾达), Xin-Long Liu(刘鑫龙), Wen-Zhe Kang(康文哲), Lin-Na Li(李琳娜), Shao-Qing Lü(吕少卿), and Ying Liu(刘颖). Chin. Phys. B, 2023, 32(11): 118902.
[15]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Identify information sources with different start times in complex networks based on sparse observers

Cite this article:

Online attention