.png){kind=icon}
.png){kind=icon}
Return
Estimating multiple propagation sources in large-scale networks using dynamic programming: Modelling and method
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ins.2025.122881.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Accurately estimating the propagation sources is an effective strategy to control the propagation process in networks. There are two open problems in multiple source estimation: (i) how to accurately and efficiently estimate the sources with limited observers but without special prior knowledge, such as source number or initial propagation time, (ii) how to design an unified algorithm to estimate single and multiple sources. This paper models the source estimation problem as a 0-1 integer programming problem and designs a dynamic programming based method for obtaining its optimal solution. In problem modelling stage, we define an infection time sequence concordance (ITSC) and propose a fast algorithm to calculate ITSC. Based on ITSC, multiple source estimation is modelled as a 0-1 integer programming problem. In method design stage, since the modelled problem is a multi-stage decision process, we propose a dynamic programming based multiple source estimator (DPMSE) to efficiently find the optimal solution. DPMSE is designed based on limited observers and does not require special prior knowledge, meanwhile, it integrates single and multiple source estimation into an unified algorithm. Moreover, DPMSE is the first dynamic programming based source estimation method. Experimental results on large-scale networks show the accuracy and efficiency of DPMSE.
Keywords:
Multiple propagation source estimation
0-1 integer programming
Multi-stage decision process
Dynamic programming based multiple source
estimator (DPMSE)
Journal
IF:
6.8
Papers:
540
Citations:
6.2W
Organization
No organization information available