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

doi:10.13700/j.bh.1001-5965.2017.0019

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

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

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

北京航空航天大学计算机学院, 北京 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

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

摘要/Abstract

摘要： 图结构异常检测可以发现金融欺诈行为、网络入侵和可疑的社交行为。针对当前检测图异常算法的计算复杂度高、不能处理大规模动态图的缺点，研究并提出了一种增量并行式的算法以便更有效地发现和检测大规模动态图中的异常。该算法使用时间滑动窗口对图进行划分，在初始化阶段选取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

中图分类号:

TP391

韩涛, 兰雨晴, 肖利民, 刘艳芳. 一种增量并行式动态图异常检测算法[J]. 北京航空航天大学学报, 2018, 44(1): 117-124.

HAN Tao, LAN Yuqing, XIAO Limin, LIU Yanfang. Incremental and parallel algorithm for anomaly detection in dynamic graphs[J]. JOURNAL OF BEIJING UNIVERSITY OF AERONAUTICS AND A, 2018, 44(1): 117-124.

参考文献

[1] AHMED N K,NEVILLE J,KOMPELLA R.Network sampling:From static to streaming graphs[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2014,8(2):7:1-7:56.
[2] EBERLE W,HOLDER L.Anomaly detection in data represented as graphs[J].Intelligent Data Analysis,2007,11(6):663-689.
[3] EBERLE W,HOLDER L,GRAVES J.Insider threat detection using a graph-based approach[J].Journal of Applied Security Research,2011,6(1):32-81.
[4] NOBLE C C,COOK D J.Graph-based anomaly detection[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2003:631-636.
[5] AKOGLU L,MCGLHON M,FALOUSTSOS C.OddBall:Spotting anomalies in weighted graphs[C]//Proceedings of the 14th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining.Berlin:Springer-Verlag,2010,3:410-421.
[6] FEIGENBAUM J,KANNAN S,MCGREGOR A,et al.On graph problems in a semi-streaming model[J].Theoretical Computer Science,2005,348(2-3):207-216.
[7] DEMETRESCU C,FINOCCHI I,RIBICHINI A.Trading off space for passes in graph streaming problems[J].ACM Transactions on Algorithms(TALG),2009,6(1):6:1-6:17.
[8] AGGARWAL G,DATAR M,RAJAGOPALAN S,et al.On the streaming model augmented with a sorting primitive[C]//Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science(FOCS).Washington,D.C.:IEEE Computer Society,2004:540-549.
[9] SARMA A,GOLLAPUDI S,PANIGRAHY R.Estimating PageRank on graph streams[C]//Proceedings of the 27th ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems.New York:ACM Press,2008:69-78.
[10] SHIN K,ELIASSI-RAD T,FALOUTSOS C.CoreScope:Graph mining using k-core analysis-Patterns,anomalies and algorithms[C]//2016 IEEE 16th International Conference on Data Mining (ICDM).Washington,D.C.:IEEE Computer Society,2017:469-478.
[11] BRIDGES R A,COLLINS J P,FERRAGUT E M,et al.Multi-level anomaly detection on time-varying graph data[C]//2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).New York:ACM Press,2016:579-583.
[12] EBERLE W,HOLDER L.A partitioning approach to scaling anomaly detection in graph streams[C]//2014 IEEE International Conference on Big Data.Washington,D.C.:IEEE Computer Society,2014:17-24.
[13] AKOGLU L,TONG H,KOUTRA D.Graph based anomaly detection and description:A survey[J].Data Mining and Knowledge Discovery,2015,29(3):626-688.
[14] 吴烨,钟志农,熊伟,等.一种高效的属性图聚类算法[J].计算机学报,2013,36(8):1704-1713.WU Y,ZHONG Z N,XIONG W,et al.An efficient method for attributed graph clustering[J].Chinese Journal of Computers,2013,36(8):1704-1713(in Chinese).
[15] EBERLE W,HOLDER L.Incremental anomaly detection in graphs[C]//2013 IEEE 13th International Conference on Data Mining Workshops.Washington,D.C.:IEEE Computer Society,2013:521-528.
[16] EPASTO A,LATTANZI S,SOZIO M.Efficient densest subgraph computation in evolving graphs[C]//Proceedings of the 24th International Conference on World Wide Web.Geneva:International World Wide Web Conferences Steering Committee,2015:300-310.
[17] YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[C]//Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics.New York:ACM Press,2012,3:1-3:8.

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

Incremental and parallel algorithm for anomaly detection in dynamic graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	宋波, 李威, 廉国选. 基于CUDA的超声二维声场EFIT仿真[J]. 北京航空航天大学学报, 2019, 45(7): 1322-1328.
[2]	张克明, 蔡远文, 任元. 基于生成对抗网络的航天异常事件检测方法[J]. 北京航空航天大学学报, 2019, 45(7): 1329-1336.
[3]	潘海侠, 徐嘉璐, 李锦涛, 王赟豪, 王华锋. 基于CNN的多尺寸航拍图像定位方法的研究与实现[J]. 北京航空航天大学学报, 2019, 45(11): 2170-2176.
[4]	鲍军鹏, 杨科, 周静. 卫星时序数据挖掘节点级并行与优化方法[J]. 北京航空航天大学学报, 2018, 44(12): 2470-2478.
[5]	郑毓轩, 李云松, 师艳子, 曲家慧, 谢卫莹. 基于FPGA的高光谱异常目标检测RXD算法加速方案[J]. 北京航空航天大学学报, 2018, 44(12): 2556-2567.
[6]	于文波, 江洁. 低存储资源开销的多路快速星点质心提取方法[J]. 北京航空航天大学学报, 2018, 44(12): 2586-2594.
[7]	葛志闪, 鲜宁, 王津申, 李阳. 二维海面上三维电大尺寸舰船目标电磁散射仿真[J]. 北京航空航天大学学报, 2018, 44(11): 2299-2304.
[8]	宋梓旭, 李峭, 汪晶晶, 熊华钢. 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 2388-2395.
[9]	李超, 赵长海, 晏海华, 刘超, 文佳敏, 王增波. 一种在复杂环境中支持容错的高性能规约框架[J]. 北京航空航天大学学报, 2018, 44(10): 2115-2124.
[10]	冯晓萌, 吴玲达, 于荣欢. 保持颜色一致性的动态电磁环境绘制算法[J]. 北京航空航天大学学报, 2016, 42(8): 1659-1666.
[11]	周炳海, 黎明. 基于CCR带并行腔双集束型设备调度方法[J]. 北京航空航天大学学报, 2016, 42(7): 1361-1367.
[12]	周媛, 左洪福, 何军. 信息缺失的航空发动机传感器数据重构[J]. 北京航空航天大学学报, 2016, 42(5): 891-898.
[13]	马树微, 李静琳, 陈曦, 陈万春. 多级固体运载火箭分级多学科设计优化[J]. 北京航空航天大学学报, 2016, 42(3): 542-550.
[14]	黄宇, 阎超, 袁武. 适用于混合网格的改进雅可比迭代法及其应用[J]. 北京航空航天大学学报, 2016, 42(3): 551-561.
[15]	杨经纬, 马凯, 龙翔. 面向集群环境的虚拟化GPU计算平台[J]. 北京航空航天大学学报, 2016, 42(11): 2340-2348.