Community-based anomaly detection in evolutionary networks
Community-based anomaly detection in evolutionary networks
复制标题
DOI：
10.1007/s10844-011-0183-2
复制
发表时间：
2012-08-01
影响因子：
3.4
通讯作者：
Samatova, Nagiza F.
中科院分区：
文献类型：
--
作者：
Chen, Zhengzhang;Hendrix, William;Samatova, Nagiza F.
动态系统的网络，包括社交网络、万维网、气候网络和生物网络，可以高度聚集。在这种动态网络中检测集群或社区是一个新兴的研究领域，然而，在检测基于社区的异常方面所做的工作较少。虽然已经有一些以前的工作，在基于图形的数据检测异常，这些异常检测方法都没有考虑到进化网络的一个重要属性，他们的社区结构。在这项工作中，我们提出了一种方法来发现社区为基础的异常，其特征在于重叠社区的进化网络。我们开发了一个无参数和可扩展的算法，使用建议的代表性为基础的技术来检测所有六种可能类型的基于社区的异常：增长，萎缩，合并，分裂，出生，消失的社区。我们详细的基本理论，以保证算法的正确性。我们通过与合成网络上的非代表性算法进行比较来测量基于社区的异常检测算法的性能，并且我们在合成数据集上的实验表明，我们的算法在基线算法上实现了11-46的运行时加速。我们还将我们的算法应用于两个现实世界的进化网络，食品网和安然电子邮件。在这两种情况下，都发现了重大的、信息丰富的社区异常动态。
Networks of dynamic systems, including social networks, the World Wide Web, climate networks, and biological networks, can be highly clustered. Detecting clusters, or communities, in such dynamic networks is an emerging area of research; however, less work has been done in terms of detecting community-based anomalies. While there has been some previous work on detecting anomalies in graph-based data, none of these anomaly detection approaches have considered an important property of evolutionary networks-their community structure. In this work, we present an approach to uncover community-based anomalies in evolutionary networks characterized by overlapping communities. We develop a parameter-free and scalable algorithm using a proposed representative-based technique to detect all six possible types of community-based anomalies: grown, shrunken, merged, split, born, and vanished communities. We detail the underlying theory required to guarantee the correctness of the algorithm. We measure the performance of the community-based anomaly detection algorithm by comparison to a non-representative-based algorithm on synthetic networks, and our experiments on synthetic datasets show that our algorithm achieves a runtime speedup of 11-46 over the baseline algorithm. We have also applied our algorithm to two real-world evolutionary networks, Food Web and Enron Email. Significant and informative community-based anomaly dynamics have been detected in both cases.