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

Incremental and parallel algorithm for anomaly detection in dynamic graphs

作　　者：韩涛[1] 兰雨晴[1] 肖利民[1] 刘艳芳[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100083

出　　处：《北京航空航天大学学报》2018年第1期117-124,共8页Journal of Beijing University of Aeronautics and Astronautics

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]