TY - GEN
T1 - Bayes-optimal methods for finding the source of a cascade
AU - Sridhar, Anirudh
AU - Poor, H. Vincent
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021
Y1 - 2021
N2 - We study the problem of estimating the source of a network cascade. The cascade initially starts from a single vertex and spreads deterministically over time, but only a noisy version of the propagation is observable. The goal is then to design a stopping time and estimator that will estimate the source well while ensuring the number of affected vertices is not too large. We rigorously formulate a Bayesian approach to the problem. If vertices can be labelled by vectors in Euclidean space (which is natural in spatial networks), the optimal estimator is the conditional mean estimator, and we derive an explicit form for the optimal stopping time under minimal assumptions on the cascade dynamics. We study the performance of the optimal stopping time on lattices, and show that a computationally efficient but suboptimal stopping time which compares the posterior variance to a threshold has near-optimal performance.
AB - We study the problem of estimating the source of a network cascade. The cascade initially starts from a single vertex and spreads deterministically over time, but only a noisy version of the propagation is observable. The goal is then to design a stopping time and estimator that will estimate the source well while ensuring the number of affected vertices is not too large. We rigorously formulate a Bayesian approach to the problem. If vertices can be labelled by vectors in Euclidean space (which is natural in spatial networks), the optimal estimator is the conditional mean estimator, and we derive an explicit form for the optimal stopping time under minimal assumptions on the cascade dynamics. We study the performance of the optimal stopping time on lattices, and show that a computationally efficient but suboptimal stopping time which compares the posterior variance to a threshold has near-optimal performance.
KW - Network cascade
KW - Optimal stopping theory
KW - Sequential estimation
KW - Stochastic optimization
UR - http://www.scopus.com/inward/record.url?scp=85115066517&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115066517&partnerID=8YFLogxK
U2 - 10.1109/ICASSP39728.2021.9414392
DO - 10.1109/ICASSP39728.2021.9414392
M3 - Conference contribution
AN - SCOPUS:85115066517
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 5190
EP - 5194
BT - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2021
Y2 - 6 June 2021 through 11 June 2021
ER -