Detecting Changes in Dynamic Events Over Networks
Detecting Changes in Dynamic Events Over Networks
复制标题
DOI：
10.1109/tsipn.2017.2696264
复制
发表时间：
2017-06-01
影响因子：
3.2
通讯作者：
Song, Le
中科院分区：
文献类型：
--
作者：
Li, Shuang;Xie, Yao;Song, Le
大量网络流事件数据越来越多地应用于社交网络分析、互联网流量监控和医疗保健分析等各种应用中。流事件数据是连续时间内发生的离散观察，两个事件之间的精确时间间隔携带有关底层系统动态的大量信息。如何使用这些流事件数据快速检测这些动态系统的变化？在本文中，我们提出了一种新颖的网络多维事件数据变化点检测框架。我们将问题转化为顺序假设检验，并导出点过程的似然比，这些似然比是通过类似于期望最大化 (EM) 的算法有效计算的，该算法是无参数的并且可以以分布式方式计算。我们得出了误报率的高度准确的理论特征，并且表明该方法可以通过随时间和网络聚合本地统计数据来提供微弱信号检测。最后，我们在 Twitter 和 Memetracker 的数值示例和真实数据集上展示了我们的算法的良好性能。
Large volumes of networked streaming event data are becoming increasingly available in a wide variety of applications such as social network analysis, Internet traffic monitoring, and health care analytics. Streaming event data are discrete observations occurring in continuous time, and the precise time interval between two events carries substantial information about the dynamics of the underlying systems. How does one promptly detect changes in these dynamic systems using these streaming event data? In this paper, we propose a novel change-point detection framework for multidimensional event data over networks. We cast the problem into a sequential hypothesis test, and we derive the likelihood ratios for point processes, which are computed efficiently via an expectation-maximization (EM) like algorithm that is parameter free and can be computed in a distributed manner. We derive a highly accurate theoretical characterization of the falsealarm rate, and we show that the method can provide weak signal detection by aggregating local statistics over time and networks. Finally, we demonstrate the good performance of our algorithm on numerical examples and real-world datasets from Twitter and Memetracker.