中国物理B ›› 2024, Vol. 33 ›› Issue (11): 118901-118901.doi: 10.1088/1674-1056/ad7af4

• • 上一篇    

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. 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
  • 收稿日期:2024-05-14 修回日期:2024-08-13 接受日期:2024-09-14 出版日期:2024-11-15 发布日期:2024-11-15
  • 基金资助:
    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).

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. 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
  • Received:2024-05-14 Revised:2024-08-13 Accepted:2024-09-14 Online:2024-11-15 Published:2024-11-15
  • Contact: Zhao-Long Hu E-mail:huzhaolong@zjnu.edu.cn
  • Supported by:
    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).

PDF (PC)

3

赞

摘要： 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.

关键词: complex networks, information spread, source identification, backward spread centricity

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.

Key words: complex networks, information spread, source identification, backward spread centricity

中图分类号:  (Complex systems)

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