Locating the propagation source on complex networks with Propagation Centrality algorithm
详细信息 查看全文
- 作者：Fan Yang fanyang2014@lzu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Ruisheng Zhang ; zhangrs@lzu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; ; Yabing Yao ; Yongna Yuan
- 关键词：Complex networks ; Propagation source location ; Susceptible-Infected (SI) model ; Rationality Observation Value (ROV) ; Propagation Centrality (PC) algorithm ; Sparse observation
- 刊名：Knowledge-Based Systems
- 出版年：2016
- 出版时间：15 May 2016
- 年：2016
- 卷：100
- 期：Complete
- 页码：112-123
- 全文大小：12997 K
文摘
Propagation source location is an important problem which can help authorities developing control strategies on complex networks. In this paper, we study this problem by assuming that there is a single propagation source and the spreading process on networks follows the Susceptible-Infected (SI) model. We define a Rationality Observation Value (ROV) on infected tree that has a fixed root and propose the corresponding measuring method. Using ROV, we construct a source estimator for tree graph and generalize it to arbitrary graph. Based on the generalized estimator, a novel Propagation Centrality (PC) algorithm is proposed, which could locate the propagation source on arbitrary graph with complexity O(N3). With PC algorithm, source location is converted into finding out a Breadth-First-Search (BFS) spanning tree with the maximal ROV from infected graph. We perform extensive simulations on a series of synthetic and real networks, the results show that PC performs better than other 5 existing methods. More importantly, the results also show that PC performs stable on the infected graph with sparse observation phenomenon.