北京航空航天大学学报 ›› 2018, Vol. 44 ›› Issue (1): 117-124.doi: 10.13700/j.bh.1001-5965.2017.0019

• 论文 • 上一篇    下一篇

一种增量并行式动态图异常检测算法

韩涛, 兰雨晴, 肖利民, 刘艳芳   

  1. 北京航空航天大学 计算机学院, 北京 100083
  • 收稿日期:2017-01-16 修回日期:2017-02-06 出版日期:2018-01-20 发布日期:2017-03-23
  • 通讯作者: 兰雨晴 E-mail:lanyuqing@buaa.edu.cn
  • 作者简介:韩涛,女,博士研究生。主要研究方向:社交网络、数据挖掘、大数据;兰雨晴,男,博士,副教授,硕士生导师。主要研究方向:操作系统、大数据、数据安全;肖利民,男,博士,教授,博士生导师。主要研究方向:高性能计算机系统、大数据;刘艳芳,女,博士研究生。主要研究方向:可信计算、软件自动化测试、大数据。

Incremental and parallel algorithm for anomaly detection in dynamic graphs

HAN Tao, LAN Yuqing, XIAO Limin, LIU Yanfang   

  1. School of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2017-01-16 Revised:2017-02-06 Online:2018-01-20 Published:2017-03-23

摘要: 图结构异常检测可以发现金融欺诈行为、网络入侵和可疑的社交行为。针对当前检测图异常算法的计算复杂度高、不能处理大规模动态图的缺点,研究并提出了一种增量并行式的算法以便更有效地发现和检测大规模动态图中的异常。该算法使用时间滑动窗口对图进行划分,在初始化阶段选取N个子图,使用最小描述长度(MDL)原理并行检测正常模式和异常模式,并行迭代地检测其他子图中的正常结构和异常结构。在多个大规模图数据集上的实验结果表明,检测动态图结构异常准确率达到96%,召回率达到85%,运行时间减少了一个数量级。同时还讨论了滑动窗口大小和并行数量对算法运行时间的影响。

关键词: 异常检测, 增量, 并行, 滑动窗口, 最小描述长度(MDL)原理

Abstract: Financial fraud behavior, network intrusion and suspicious social actions can be detected by structural anomaly detection in graphs. The existing anomaly detection algorithms require high computational complexity and cannot process large-scale dynamic graphs. So an incremental and parallel algorithm is proposed to discover and detect abnormal patterns in dynamic graphs effectively and efficiently. The whole graph was partitioned into subgraphs by time sliding windows. N subgraphs in time sliding windows were processed in parallel by minimum description length (MDL) principle to discover both normal and abnormal patterns. Structural outliers can be detected gradually in parallel based on normal patterns. The results of experiments conducted in multiple large-scale graphs show that the precision rate for detecting the abnormal patterns of dynamic graph reaches 96%, recall rate reaches 85%, and running time reduces by an order of magnitude. The impact of the size of sliding windows and the number of parallel on running time of the algorithm is also discussed.

Key words: anomaly detection, incremental, parallel, sliding window, minimum description length (MDL) principle

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发