Detecting Change Points in the Large-Scale Structure of Evolving Networks
Detecting Change Points in the Large-Scale Structure of Evolving Networks
复制标题
DOI：
10.1609/aaai.v29i1.9574
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Leto Peel;A. Clauset
中科院分区：
文献类型：
--
作者：
Leto Peel;A. Clauset
人或物体之间的交互本质上通常是动态的，可以表示为一系列网络，每个网络都提供短时间内交互的快照。分析此类不断发展的网络的一项重要任务是变化点检测，其中我们既确定大规模交互模式发生根本变化的时间，又量化发生的变化的大小和类型。在这里，我们首次在在线概率学习框架内形式化网络变化点检测问题，并介绍一种可以可靠解决该问题的方法。该方法将广义分层随机图模型与贝叶斯假设检验相结合，以定量确定变化点是否、何时以及如何精确地发生。我们使用具有不同类型和幅度的已知变化点的合成数据来分析我们方法的可检测性，并表明该方法比以前使用的几种替代方法更准确。该方法应用于两个高分辨率不断发展的社交网络，识别出一系列与这些网络已知的外部“冲击”相一致的变化点。
Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external ``shocks'' to these networks.