TY - GEN
T1 - Quickest Detection of Significant Events in Structured Networks
AU - Zou, Shaofeng
AU - Veeravalli, Venugopal V.
AU - Li, Jian
AU - Towsley, Don
N1 - Funding Information:
Research reported in this paper was sponsored in part by the Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196. The work of S. Zou and V. V. Veeravalli was also supported in part by the National Science Foundation (NSF) under grant CCF 16-18658, and by the Air Force Office of Scientific Research (AFOSR) under grant FA9550-16-1-0077.
PY - 2019/2/19
Y1 - 2019/2/19
N2 - We study the problem of quickest detection of dynamic significant events in structured networks. At some unknown time, an event occurs, and a subset of nodes in the network are affected, which undergo a change in the statistics of their observations. It is assumed that the event propagates dynamically along the edges in the network, in that the affected nodes form a connected subgraph. The event propagation dynamics are 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. We construct a Network-CuSum (N-CuSum) algorithm that exploits network structure in a computationally efficient way. We show that N-CuSum is adaptive to unknown propagation dynamics, and first-order asymptotically optimal as the false alarm rate goes to zero.
AB - We study the problem of quickest detection of dynamic significant events in structured networks. At some unknown time, an event occurs, and a subset of nodes in the network are affected, which undergo a change in the statistics of their observations. It is assumed that the event propagates dynamically along the edges in the network, in that the affected nodes form a connected subgraph. The event propagation dynamics are 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. We construct a Network-CuSum (N-CuSum) algorithm that exploits network structure in a computationally efficient way. We show that N-CuSum is adaptive to unknown propagation dynamics, and first-order asymptotically optimal as the false alarm rate goes to zero.
UR - http://www.scopus.com/inward/record.url?scp=85062947611&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062947611&partnerID=8YFLogxK
U2 - 10.1109/ACSSC.2018.8645282
DO - 10.1109/ACSSC.2018.8645282
M3 - Conference contribution
AN - SCOPUS:85062947611
T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers
SP - 1307
EP - 1311
BT - Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
A2 - Matthews, Michael B.
PB - IEEE Computer Society
T2 - 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Y2 - 28 October 2018 through 31 October 2018
ER -