1
|
Peng SL, Wang HJ, Peng H, Zhu XB, Li X, Han J, Zhao D, Hu ZL. NLSI: An innovative method to locate epidemic sources on the SEIR propagation model. CHAOS (WOODBURY, N.Y.) 2023; 33:083125. [PMID: 37549113 DOI: 10.1063/5.0152859] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/02/2023] [Accepted: 07/12/2023] [Indexed: 08/09/2023]
Abstract
Epidemics pose a significant threat to societal development. Accurately and swiftly identifying the source of an outbreak is crucial for controlling the spread of an epidemic and minimizing its impact. However, existing research on locating epidemic sources often overlooks the fact that epidemics have an incubation period and fails to consider social behaviors like self-isolation during the spread of the epidemic. In this study, we first take into account isolation behavior and introduce the Susceptible-Exposed-Infected-Recovered (SEIR) propagation model to simulate the spread of epidemics. As the epidemic reaches a certain threshold, government agencies or hospitals will report the IDs of some infected individuals and the time when symptoms first appear. The reported individuals, along with their first and second-order neighbors, are then isolated. Using the moment of symptom onset reported by the isolated individuals, we propose a node-level classification method and subsequently develop the node-level-based source identification (NLSI) algorithm. Extensive experiments demonstrate that the NLSI algorithm is capable of solving the source identification problem for single and multiple sources under the SEIR propagation model. We find that the source identification accuracy is higher when the infection rate is lower, and a sparse network structure is beneficial to source localization. Furthermore, we discover that the length of the isolation period has little impact on source localization, while the length of the incubation period significantly affects the accuracy of source localization. This research offers a novel approach for identifying the origin of the epidemic associated with our defined SEIR model.
Collapse
Affiliation(s)
- Shui-Lin Peng
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| | - Hong-Jue Wang
- School of Information, Beijing Wuzi University, Beijing 101149, China
| | - Hao Peng
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| | - Xiang-Bin Zhu
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| | - Xiang Li
- College of Science, National University of Defense Technology, Changsha 410073, China
| | - Jianmin Han
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| | - Dandan Zhao
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| | - Zhao-Long Hu
- College of Computer Science and Technology, Zhejiang Normal University, Jinhua 321004, China
| |
Collapse
|
2
|
Zhao Y, Li C, Shi D, Chen G, Li X. Ranking cliques in higher-order complex networks. CHAOS (WOODBURY, N.Y.) 2023; 33:073139. [PMID: 37463096 DOI: 10.1063/5.0147721] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/25/2023] [Accepted: 06/20/2023] [Indexed: 07/20/2023]
Abstract
Traditional network analysis focuses on the representation of complex systems with only pairwise interactions between nodes. However, the higher-order structure, which is beyond pairwise interactions, has a great influence on both network dynamics and function. Ranking cliques could help understand more emergent dynamical phenomena in large-scale complex networks with higher-order structures, regarding important issues, such as behavioral synchronization, dynamical evolution, and epidemic spreading. In this paper, motivated by multi-node interactions in a topological simplex, several higher-order centralities are proposed, namely, higher-order cycle (HOC) ratio, higher-order degree, higher-order H-index, and higher-order PageRank (HOP), to quantify and rank the importance of cliques. Experiments on both synthetic and real-world networks support that, compared with other traditional network metrics, the proposed higher-order centralities effectively reduce the dimension of a large-scale network and are more accurate in finding a set of vital nodes. Moreover, since the critical cliques ranked by the HOP and the HOC are scattered over a complex network, the HOP and the HOC outperform other metrics in ranking cliques that are vital in maintaining the network connectivity, thereby facilitating network dynamical synchronization and virus spread control in applications.
Collapse
Affiliation(s)
- Yang Zhao
- Adaptive Networks and Control Lab, Department of Electronic Engineering, School of Information Science and Technology, Fudan University, Shanghai 200433, China
| | - Cong Li
- Adaptive Networks and Control Lab, Department of Electronic Engineering, School of Information Science and Technology, Fudan University, Shanghai 200433, China
| | - Dinghua Shi
- Department of Mathematics, College of Science, Shanghai University, Shanghai 200444, China
| | - Guanrong Chen
- Department of Electrical Engineering, City University of Hong Kong, Hong Kong 999077, China
| | - Xiang Li
- Institute of Complex Networks and Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China
- State Key Laboratory of Intelligent Autonomous Systems, the Frontiers Science Center for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China
| |
Collapse
|
3
|
Liu S, Gao H. The Structure Entropy-Based Node Importance Ranking Method for Graph Data. ENTROPY (BASEL, SWITZERLAND) 2023; 25:941. [PMID: 37372285 DOI: 10.3390/e25060941] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/24/2023] [Revised: 06/11/2023] [Accepted: 06/13/2023] [Indexed: 06/29/2023]
Abstract
Due to its wide application across many disciplines, how to make an efficient ranking for nodes in graph data has become an urgent topic. It is well-known that most classical methods only consider the local structure information of nodes, but ignore the global structure information of graph data. In order to further explore the influence of structure information on node importance, this paper designs a structure entropy-based node importance ranking method. Firstly, the target node and its associated edges are removed from the initial graph data. Next, the structure entropy of graph data can be constructed by considering the local and global structure information at the same time, in which case all nodes can be ranked. The effectiveness of the proposed method was tested by comparing it with five benchmark methods. The experimental results show that the structure entropy-based node importance ranking method performs well on eight real-world datasets.
Collapse
Affiliation(s)
- Shihu Liu
- School of Mathematics and Computer Science, Yunnan Minzu University, Kunming 650504, China
| | - Haiyan Gao
- School of Mathematics and Computer Science, Yunnan Minzu University, Kunming 650504, China
| |
Collapse
|
4
|
Bhattacharya R, Nagwani NK, Tripathi S. Detecting influential nodes with topological structure via Graph Neural Network approach in social networks. INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY : AN OFFICIAL JOURNAL OF BHARATI VIDYAPEETH'S INSTITUTE OF COMPUTER APPLICATIONS AND MANAGEMENT 2023; 15:2233-2246. [PMID: 37256031 PMCID: PMC10163927 DOI: 10.1007/s41870-023-01271-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 11/05/2022] [Accepted: 04/05/2023] [Indexed: 06/01/2023]
Abstract
Detecting influential nodes in complex social networks is crucial due to the enormous amount of data and the constantly changing behavior of existing topologies. Centrality-based and machine-learning approaches focus mostly on node topologies or feature values in their evaluation of nodes' relevance. However, both network topologies and node attributes should be taken into account when determining the influential value of nodes. This research has proposed a deep learning model called Graph Convolutional Networks (GCN) to discover the significant nodes in graph-based large datasets. A deep learning framework for identifying influential nodes with structural centrality via Graph Convolutional Networks called DeepInfNode has been developed. The proposed approach measures up contextual information from Susceptible-Infected-Recovered (SIR) model trials to measure the rate of infection to develop node representations. In the experimental section, acquired experimental results indicate that the suggested model has a higher F1 and Area under the curve (AUC) value. The findings indicate that the strategy is both effective and precise in terms of suggesting new linkages. The proposed DeepInfNode model outperforms state-of-the-art approaches on a variety of publicly available standard graph datasets, achieving an increase in performance of up to 99.1% of accuracy.
Collapse
Affiliation(s)
- Riju Bhattacharya
- Department of Computer Science and Engineering, National Institute of Technology Raipur, GE Road, Raipur, Chhattisgarh 492010 India
| | - Naresh Kumar Nagwani
- Department of Computer Science and Engineering, National Institute of Technology Raipur, GE Road, Raipur, Chhattisgarh 492010 India
| | - Sarsij Tripathi
- Department of Computer Science and Engineering, Motilal Nehru National Institute of Technology, Allahabad, Prayagraj, Uttar Pradesh 211004 India
| |
Collapse
|
5
|
Zhang M, Wang X, Jin L, Song M, Li Z. A new approach for evaluating node importance in complex networks via deep learning methods. Neurocomputing 2022. [DOI: 10.1016/j.neucom.2022.05.010] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/18/2022]
|
6
|
Zhao J, Wen T, Jahanshahi H, Cheong KH. The random walk-based gravity model to identify influential nodes in complex networks. Inf Sci (N Y) 2022. [DOI: 10.1016/j.ins.2022.07.084] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/31/2022]
|
7
|
Li Z, Huang X. Identifying influential spreaders by gravity model considering multi-characteristics of nodes. Sci Rep 2022; 12:9879. [PMID: 35701528 PMCID: PMC9197977 DOI: 10.1038/s41598-022-14005-3] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/14/2022] [Accepted: 05/31/2022] [Indexed: 11/09/2022] Open
Abstract
How to identify influential spreaders in complex networks is a topic of general interest in the field of network science. Therefore, it wins an increasing attention and many influential spreaders identification methods have been proposed so far. A significant number of experiments indicate that depending on a single characteristic of nodes to reliably identify influential spreaders is inadequate. As a result, a series of methods integrating multi-characteristics of nodes have been proposed. In this paper, we propose a gravity model that effectively integrates multi-characteristics of nodes. The number of neighbors, the influence of neighbors, the location of nodes, and the path information between nodes are all taken into consideration in our model. Compared with well-known state-of-the-art methods, empirical analyses of the Susceptible-Infected-Recovered (SIR) spreading dynamics on ten real networks suggest that our model generally performs best. Furthermore, the empirical results suggest that even if our model only considers the second-order neighborhood of nodes, it still performs very competitively.
Collapse
Affiliation(s)
- Zhe Li
- Software College, Shenyang University of Technology of China, Shenyang, 110870, People's Republic of China.
| | - Xinyu Huang
- Software College, Northeastern University of China, Shenyang, 110819, People's Republic of China.
| |
Collapse
|
8
|
|
9
|
Identifying and Ranking Influential Nodes in Complex Networks Based on Dynamic Node Strength. ALGORITHMS 2021. [DOI: 10.3390/a14030082] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
Identifying and ranking the node influence in complex networks is an important issue. It helps to understand the dynamics of spreading process for designing efficient strategies to hinder or accelerate information spreading. The idea of decomposing network to rank node influence is adopted widely because of low computational complexity. Of this type, decomposition is a dynamic process, and each iteration could be regarded as an inverse process of spreading. In this paper, we propose a new ranking method, Dynamic Node Strength Decomposition, based on decomposing network. The spreading paths are distinguished by weighting the edges according to the nodes at both ends. The change of local structure in the process of decomposition is considered. Our experimental results on four real networks with different sizes show that the proposed method can generate a more monotonic ranking list and identify node influence more effectively.
Collapse
|
10
|
Shang Q, Zhang B, Li H, Deng Y. Identifying influential nodes: A new method based on network efficiency of edge weight updating. CHAOS (WOODBURY, N.Y.) 2021; 31:033120. [PMID: 33810754 DOI: 10.1063/5.0033197] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/14/2020] [Accepted: 02/15/2021] [Indexed: 06/12/2023]
Abstract
Identification of influential nodes in complex networks is an area of exciting growth since it can help us to deal with various problems. Furthermore, identifying important nodes can be used across various disciplines, such as disease, sociology, biology, engineering, just to name a few. Hence, how to identify influential nodes more accurately deserves further research. Traditional identification methods usually only focus on the local or global information of the network. However, only focusing on a part of the information in the network will lead to the loss of information, resulting in inaccurate results. In order to address this problem, an identification method based on network efficiency of edge weight updating is proposed, which can effectively incorporate both global and local information of the network. Our proposed method avoids the lack of information in the network and ensures the accuracy of the results as much as possible. Moreover, by introducing the iterative idea of weight updating, some dynamic information is also introduced into our proposed method, which is more convincing. Varieties of experiments have been carried out on 11 real-world data sets to demonstrate the effectiveness and superiority of our proposed method.
Collapse
Affiliation(s)
- Qiuyan Shang
- Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Bolong Zhang
- School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Hanwen Li
- Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Yong Deng
- Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu 610054, China
| |
Collapse
|
11
|
Zhao G, Jia P, Zhou A, Zhang B. InfGCN: Identifying influential nodes in complex networks with graph convolutional networks. Neurocomputing 2020. [DOI: 10.1016/j.neucom.2020.07.028] [Citation(s) in RCA: 17] [Impact Index Per Article: 4.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/01/2022]
|
12
|
Yang PL, Xu GQ, Yu Q, Guo JW. An adaptive heuristic clustering algorithm for influence maximization in complex networks. CHAOS (WOODBURY, N.Y.) 2020; 30:093106. [PMID: 33003925 DOI: 10.1063/1.5140646] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/29/2019] [Accepted: 08/08/2020] [Indexed: 06/11/2023]
Abstract
Influence maximization research in the real world allows us to better understand, accelerate spreading processes for innovations and products, and effectively analyze, predict, and control the spread of diseases, rumors, and computer viruses. In this paper, we first put forward a new path-based node similarity measure, named the dynamic local similarity index, which can be dynamically adjusted to the optimal mode according to network topology characteristics. Compared to the Katz index with high complexity and an LP index with a limited application range, the proposed index achieves an excellent balance between complexity and precision. Second, combining the extended neighborhood coreness with the minimum distance, a novel strategy is presented for selecting initial centers of clusters, which is helpful for speeding up clustering convergence and avoiding local optimum, especially in non-connected networks. Subsequently, we present an adaptive heuristic clustering algorithm, which can find the seed set with maximum collective influence through clustering. The empirical results on four real datasets show the effectiveness and efficiency of the proposed algorithm, which compares favorably to several state-of-the-art algorithms.
Collapse
Affiliation(s)
- Ping-Le Yang
- School of Management, Shanghai University, Shanghai 200444, China
| | - Gui-Qiong Xu
- School of Management, Shanghai University, Shanghai 200444, China
| | - Qin Yu
- School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China
| | - Jia-Wen Guo
- School of Management, Shanghai University, Shanghai 200444, China
| |
Collapse
|
13
|
Ran Y, Deng X, Wang X, Jia T. A generalized linear threshold model for an improved description of the spreading dynamics. CHAOS (WOODBURY, N.Y.) 2020; 30:083127. [PMID: 32872812 DOI: 10.1063/5.0011658] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/23/2020] [Accepted: 07/27/2020] [Indexed: 06/11/2023]
Abstract
Many spreading processes in our real-life can be considered as a complex contagion, and the linear threshold (LT) model is often applied as a very representative model for this mechanism. Despite its intensive usage, the LT model suffers several limitations in describing the time evolution of the spreading. First, the discrete-time step that captures the speed of the spreading is vaguely defined. Second, the synchronous updating rule makes the nodes infected in batches, which cannot take individual differences into account. Finally, the LT model is incompatible with existing models for the simple contagion. Here, we consider a generalized linear threshold (GLT) model for the continuous-time stochastic complex contagion process that can be efficiently implemented by the Gillespie algorithm. The time in this model has a clear mathematical definition, and the updating order is rigidly defined. We find that the traditional LT model systematically underestimates the spreading speed and the randomness in the spreading sequence order. We also show that the GLT model works seamlessly with the susceptible-infected or susceptible-infected-recovered model. One can easily combine them to model a hybrid spreading process in which simple contagion accumulates the critical mass for the complex contagion that leads to the global cascades. Overall, the GLT model we proposed can be a useful tool to study complex contagion, especially when studying the time evolution of the spreading.
Collapse
Affiliation(s)
- Yijun Ran
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Xiaomin Deng
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Xiaomeng Wang
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Tao Jia
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| |
Collapse
|
14
|
Jiang C, Liu X, Zhang J, Yu X. Compact models for influential nodes identification problem in directed networks. CHAOS (WOODBURY, N.Y.) 2020; 30:053126. [PMID: 32491886 DOI: 10.1063/5.0005452] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/24/2020] [Accepted: 04/23/2020] [Indexed: 06/11/2023]
Abstract
Influential nodes identification problem (INIP) is one of the most important problems in complex networks. Existing methods mainly deal with this problem in undirected networks, while few studies focus on it in directed networks. Moreover, the methods designed for identifying influential nodes in undirected networks do not work for directed networks. Therefore, in this paper, we investigate INIP in directed networks. We first propose a novel metric to assess the influence effect of nodes in directed networks. Then, we formulate a compact model for INIP and prove it to be NP-Complete. Furthermore, we design a novel heuristic algorithm for the proposed model by integrating a 2-opt local search into a greedy framework. The experimental results show that, in most cases, the proposed methods outperform traditional measure-based heuristic methods in terms of accuracy and discrimination.
Collapse
Affiliation(s)
- Cheng Jiang
- School of Management Engineering, Capital University of Economics and Business, Beijing 100070, China
| | - Xueyong Liu
- School of Management Engineering, Capital University of Economics and Business, Beijing 100070, China
| | - Jun Zhang
- School of Management Engineering, Capital University of Economics and Business, Beijing 100070, China
| | - Xiao Yu
- School of Engineering, University of Chinese Academy of Sciences, Beijing 100049, China
| |
Collapse
|
15
|
Influential Nodes Identification in Complex Networks via Information Entropy. ENTROPY 2020; 22:e22020242. [PMID: 33286016 PMCID: PMC7516697 DOI: 10.3390/e22020242] [Citation(s) in RCA: 48] [Impact Index Per Article: 12.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 11/09/2019] [Revised: 02/17/2020] [Accepted: 02/19/2020] [Indexed: 12/11/2022]
Abstract
Identifying a set of influential nodes is an important topic in complex networks which plays a crucial role in many applications, such as market advertising, rumor controlling, and predicting valuable scientific publications. In regard to this, researchers have developed algorithms from simple degree methods to all kinds of sophisticated approaches. However, a more robust and practical algorithm is required for the task. In this paper, we propose the EnRenew algorithm aimed to identify a set of influential nodes via information entropy. Firstly, the information entropy of each node is calculated as initial spreading ability. Then, select the node with the largest information entropy and renovate its l-length reachable nodes’ spreading ability by an attenuation factor, repeat this process until specific number of influential nodes are selected. Compared with the best state-of-the-art benchmark methods, the performance of proposed algorithm improved by 21.1%, 7.0%, 30.0%, 5.0%, 2.5%, and 9.0% in final affected scale on CEnew, Email, Hamster, Router, Condmat, and Amazon network, respectively, under the Susceptible-Infected-Recovered (SIR) simulation model. The proposed algorithm measures the importance of nodes based on information entropy and selects a group of important nodes through dynamic update strategy. The impressive results on the SIR simulation model shed light on new method of node mining in complex networks for information spreading and epidemic prevention.
Collapse
|
16
|
Jia P, Dong W, Yang S, Zhan Z, Tu L, Lai S. Spatial Lifecourse Epidemiology and Infectious Disease Research. Trends Parasitol 2020; 36:235-238. [PMID: 32044243 PMCID: PMC7172117 DOI: 10.1016/j.pt.2019.12.012] [Citation(s) in RCA: 19] [Impact Index Per Article: 4.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/23/2019] [Revised: 12/27/2019] [Accepted: 12/27/2019] [Indexed: 01/02/2023]
Abstract
Spatial lifecourse epidemiology aims to utilize advanced spatial, location-aware, and artificial intelligence technologies to investigate long-term effects of measurable biological, environmental, behavioral, and psychosocial factors on individual risk for chronic diseases. It could also further the research on infectious disease dynamics, risks, and consequences across the life course.
Collapse
Affiliation(s)
- Peng Jia
- School of Resources and Environmental Science, Wuhan University, Wuhan, China; Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Hong Kong, China; International Initiative on Spatial Lifecourse Epidemiology (ISLE), Hong Kong, China. @hotmail.com
| | - Weihua Dong
- State Key Laboratory of Remote Sensing Science, Beijing Normal University, Beijing, 100875, China; Faculty of Geography, Beijing Normal University, Beijing, 100875, China
| | - Shujuan Yang
- West China School of Public Health/West China Fourth Hospital, Sichuan University, Chengdu, Sichuan, 610041, China; International Initiative on Spatial Lifecourse Epidemiology (ISLE), Hong Kong, China
| | - Zhicheng Zhan
- State Key Laboratory of Remote Sensing Science, Beijing Normal University, Beijing, 100875, China; Faculty of Geography, Beijing Normal University, Beijing, 100875, China
| | - La Tu
- Department of Information Art and Design, Tsinghua University, Beijing, 100084, China
| | - Shengjie Lai
- WorldPop, School of Geography and Environmental Science, University of Southampton, Southampton, SO17 1BJ, UK; Flowminder Foundation, Stockholm, SE-113 55, Sweden; School of Public Health, Fudan University, Key Laboratory of Public Health Safety, Ministry of Education, Shanghai 200032, China
| |
Collapse
|
17
|
Hu ZL, Wang L, Tang CB. Locating the source node of diffusion process in cyber-physical networks via minimum observers. CHAOS (WOODBURY, N.Y.) 2019; 29:063117. [PMID: 31266325 DOI: 10.1063/1.5092772] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/14/2019] [Accepted: 05/31/2019] [Indexed: 06/09/2023]
Abstract
Locating the source node that initiates a diffusion process is an increasingly popular topic that contributes new insights into the maintenance of cyber security, rumor detection in social media, digital surveillance of infectious diseases, etc. Existing studies select the observers randomly or select them heuristically according to the network centrality or community measures. However, there still lacks a method to identify the minimum set of observers for accurately locating the source node of information diffusion in cyber physical networks. Here, we fill this knowledge gap by proposing a greedy optimization algorithm by analyzing the differences of the propagation delay. We use extensive simulations with both synthetic and empirical networks to show that the number of observers can be substantially decreased: Our method only uses a small fraction of nodes (10%-20%) as observers in most networks, whereas the conventional random selection methods have to use 2-3 times more nodes as observers. Interestingly, if a network has a large proportion of low-degree nodes (e.g., karate network), it is necessary to recruit more observers. In particular, the periphery nodes that are only connected with one edge must be observers. Combining our greedy optimization algorithm with the diffusion-back method, the performance of source localization is robust against noise.
Collapse
Affiliation(s)
- Z L Hu
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, People's Republic of China
| | - L Wang
- Mathematical Modelling of Infectious Diseases Unit, Institut Pasteur, UMR2000, CNRS, 75015 Paris, France
| | - C B Tang
- College of Physics and Electronic Information Engineering, Zhejiang Normal University, Jinhua 321004, People's Republic of China
| |
Collapse
|