TY - JOUR
T1 - Quickest Detection of Dynamic Events in Networks
AU - Zou, Shaofeng
AU - Veeravalli, Venugopal V.
AU - Li, Jian
AU - Towsley, Don
N1 - Funding Information:
Manuscript received July 17, 2018; revised October 10, 2019; accepted October 13, 2019. Date of publication October 18, 2019; date of current version March 17, 2020. This work was supported in part by the Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196. S. Zou and V. V. Veeravalli were supported in part by the National Science Foundation (NSF) under Grant CCF 16-18658 and in part by the Air Force Office of Scientific Research (AFOSR) under Grant FA9550-16-1-0077. This article was presented in part at the 2018 IEEE International Conference on Acoustics, Speech, and Signal Processing, and in part at the Asilomar Conference on Signals, Systems, and Computers.
PY - 2020/4
Y1 - 2020/4
N2 - The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a 'significant' event, i.e., when the event has affected no fewer than \eta nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results.
AB - The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a 'significant' event, i.e., when the event has affected no fewer than \eta nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results.
KW - Adaptive algorithms
KW - Network-CuSum (N-CuSum)
KW - Spartan-CuSum (S-CuSum)
KW - asymptotic optimality
KW - event propagation
KW - structured network
UR - http://www.scopus.com/inward/record.url?scp=85082394798&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082394798&partnerID=8YFLogxK
U2 - 10.1109/TIT.2019.2948350
DO - 10.1109/TIT.2019.2948350
M3 - Article
AN - SCOPUS:85082394798
VL - 66
SP - 2280
EP - 2295
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
SN - 0018-9448
IS - 4
M1 - 8876873
ER -