Abstract
Detecting the onset of spreading phenomena in networks, such as viral outbreaks or malware propagation, is critical for timely intervention. This paper introduces a novel framework for the "Quickest Change Detection" (QCD) of dynamic events. Unlike traditional methods that monitor static groups, our approach identifies events as they evolve and expand. We propose two algorithms: S-CuSum for fully connected networks and N-CuSum for general graph topologies. Both are mathematically proven to be asymptotically optimal, minimizing the expected detection delay for a given false alarm constraint while maintaining high computational efficiency.
Introduction
In many real-world scenarios, a threat does not emerge everywhere at once. Instead, it starts at a single point of origin and spreads through a network. Standard QCD techniques are often ill-equipped for such "dynamic" changes because they assume the set of affected sensors is either known or fixed.
The core challenge addressed here is detecting when an event has reached a "significance threshold" of $\eta$ nodes, without prior knowledge of the propagation path, speed, or the specific nodes involved.
Problem Formulation
We consider a network of $L$ nodes where each node provides a stream of observations. Initially, all nodes follow a "pre-change" distribution $f_0$. At some unknown time, an event begins and spreads. Once a node is affected, its observation distribution shifts to $f_1$. The goal is to trigger an alarm as soon as at least $\eta$ nodes have undergone this change, minimizing the delay while keeping the rate of false alarms below a specified level.
Proposed Methodology
The proposed framework leverages the Cumulative Sum (CuSum) statistic, adapted for network dynamics.
S-CuSum (Spartan-CuSum)
For networks where any node can potentially infect any other (fully connected), we introduce S-CuSum. This algorithm calculates local CuSum statistics for every node and then sums the smallest $L - \eta + 1$ values. This "smallest sum" logic ensures that the alarm is only raised when at least $\eta$ nodes exhibit a collective shift in their data statistics. S-CuSum is highly efficient, with a computational complexity of $O(L)$.
N-CuSum (Network-CuSum)
In networks with arbitrary connectivity (e.g., grids or social graphs), the physical proximity of affected nodes is a key indicator of a spreading event. N-CuSum incorporates this spatial information by using a Breadth-First Search (BFS) to identify connected clusters of nodes with high local statistics.
By applying the S-CuSum logic to these connected components, N-CuSum effectively filters out "noise" from isolated nodes that might fluctuate due to random chance, ensuring the alarm reflects a genuine spreading process.
Key Results and Insights
The performance of these algorithms was validated through rigorous mathematical proofs and numerical simulations on various topologies, including a 36-node lattice network.
- Asymptotic Optimality: The authors prove that as the false alarm probability approaches zero, S-CuSum and N-CuSum achieve the minimum possible detection delay.
- Dichotomy of Delay: Research reveals that detection delay is governed by two factors: the propagation speed of the event and the statistical threshold. In fast-spreading events, the threshold dominates; in slow-spreading ones, the physical propagation time is the limiting factor.
- Performance Gains: Simulations demonstrate that N-CuSum significantly outperforms traditional "multi-chart" methods by accounting for network structure. It successfully ignores spurious signals from disconnected nodes, leading to fewer false alarms and faster detection of real threats.
- Scalability: Both algorithms exhibit linear complexity relative to network size ($O(L)$ for S-CuSum and $O(L + |E|)$ for N-CuSum), making them suitable for real-time monitoring of large-scale systems. In a 10,000-step simulation on a 36-node network, the algorithms processed the entire sequence in less than one second on a standard laptop.
Conclusion and Future Directions
This work provides a robust and efficient foundation for monitoring dynamic network threats. Future research will focus on extending these models to handle unknown post-change distributions ($f_1$), decentralized processing where nodes only communicate with neighbors, and heterogeneous networks containing multiple sensor types.
Summary updated