Quickest Detection of Dynamic Events in Networks
Quickest Detection of Dynamic Events in Networks
复制标题
DOI：
10.1109/tit.2019.2948350
复制
发表时间：
2018-07
影响因子：
2.5
通讯作者：
Shaofeng Zou;V. Veeravalli;Jian Li;D. Towsley
中科院分区：
文献类型：
--
作者：
Shaofeng Zou;V. Veeravalli;Jian Li;D. Towsley
研究了网络中动态事件的快速检测问题。在某个未知的时间，一个事件发生了，网络中的许多节点受到该事件的影响，因为它们的观测数据发生了变化。假设事件是动态的，它可以沿着网络的边缘传播，并且随着时间的推移影响越来越多的节点。假定事件传播动力学是未知的。目标是设计一种序列算法，能够在控制误报率的同时，尽快检测到“重要”事件，即当事件影响不少于$\eta $节点时。首先研究了全连通网络，然后将研究结果推广到任意连通网络。结果表明，所设计的算法对未知的传播动态具有较强的适应性，并在虚警率趋于零时证明了算法的一阶渐近最优性。该算法在每个时间步的网络大小计算复杂度都是线性的，这对在线实现至关重要。数值模拟验证了理论结果。
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.