Quickest Detection of Significant Events in Structured Networks

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.