INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
Prev
|
|
|
Identify information sources with different start times in complex networks based on sparse observers |
Yuan-Zhang Deng(邓元璋)1, Zhao-Long Hu(胡兆龙)1,†, Feilong Lin(林飞龙)1, Chang-Bing Tang(唐长兵)2, Hui Wang(王晖)1, and Yi-Zhen Huang(黄宜真)3 |
1 School of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China; 2 School of Physics and Electronic Information Engineering, Zhejiang Normal University, Jinhua 321004, China; 3 School of Information Engineering, Jinhua Polytechnic, Jinhua 321016, China |
|
|
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.
|
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] Erdős 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 |
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|