| Citation: | HAN Tao, LAN Yuqing, XIAO Limin, et al. Incremental and parallel algorithm for anomaly detection in dynamic graphs[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(1): 117-124. doi: 10.13700/j.bh.1001-5965.2017.0019(in Chinese)
|
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.
| [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. doi: 10.1016/j.tcs.2005.09.013
|
| [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. doi: 10.1007/s10618-014-0365-y
|
| [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.
|
| [1] | DUAN J Z，XIAO C. Parallel MRI reconstruction by using complex convolution and attention mechanism[J]. Journal of Beijing University of Aeronautics and Astronautics，2025，51（1）：85-93 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.1005. |
| [2] | LIU He, WEI Cheng, ZHANG Zexu, SUN Bo, HU Zihang. Spacecraft Anomaly Detection Based on Filtered Autoencoder Envelope Analysis[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0832 |
| [3] | XIONG Xiaozhou, YAN Haoran, WANG Chenxi, HU Lei. GQA-SM BERT model for log anomaly detection[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0805 |
| [4] | YUAN Run-jie, CHEN Rui, HAN Jian-wei, XIA Qing, WANG Xuan, CHEN Qian, LIANG Ya-nan. Mechanism of anomalies in operational amplifier induced by proton deep charge-discharge effects[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0060 |
| [5] | SHI Yangyu, XIE Chengjie, ZHENG Diwen, LU Shuhua. Multi-scale anomaly behavior detection based on Mamba-CNN[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0416 |
| [6] | XIAO Bo, GUO Fang, WANG Rong, ZENG Zhaolong. Abnormal Behavior Detection Method Based on Multi-modal Feature Fusion[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0455 |
| [7] | ZHANG Dong-ping, PAN Xin, MA Dao-bin, MI Hong-mei, LIN Li-li. Multi-channel Coupled Spatial-temporal Enhanced Abnormal Behavior Detection[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0752 |
| [8] | HU Dandan, ZHAO Jinju, NIU Guochen. Active obstacle avoidance based on improved dynamic window approach for off-axis full-trailer vehicles[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0404 |
| [9] | CHEN Y，FANG Y Z，HAN T，et al. Incremental guidance method for kinetic kill vehicles with target maneuver compensation[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（3）：831-838 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0519. |
| [10] | ZHAI You-hong, LI Chun-tao, SU Zi-kang, LI Xue-bing. Neural network incremental dynamic inversion target drone somersault maneuver control[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0690 |
| [11] | JU T，LIU S，WANG Z Q，et al. Task segmentation and parallel optimization of DNN model[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（9）：2739-2752 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0731. |
| [12] | ZHAO Minghua, HUANG Xuewen, DU Shuangli, LYU Jiahao, ZHI Rui, SHI Cheng. Spatio-temporal separated transform memory networks for video anomaly detection[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2024.0458 |
| [13] | ZHONG J，LUO C，ZHANG H，et al. Flight data anomaly detection based on correlation parameter selection[J]. Journal of Beijing University of Aeronautics and Astronautics，2024，50（5）：1738-1745 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0574. |
| [14] | DUAN Le-fan, HAO Xin-hong, CHEN Qi-le. Anti-sweep jamming method for FM fuze based on outlier reconstruction[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0199 |
| [15] | RAN Hua-ming. Airborne sensor multi-task scheduling algorithm based on slide time window[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0488 |
| [16] | MI X P，CHEN X H，LIU Q，et al. Tropospheric scattering spectrum sensing based on sliding interception and signal correlation[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（2）：464-471 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0255. |
| [17] | SHI T，ZHUANG X B，LIN Z J，et al. Satellite selection based on parallel genetic algorithm for high orbit autonomous satellite navigation[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（12）：3528-3536 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0118. |
| [18] | LI Shuai-chao, LI Ming-ze, SUN Jia-ao, LU Shu-hua. Combining LBP and parallel attention mechanism micro expression recognition[J]. Journal of Beijing University of Aeronautics and Astronautics. doi: 10.13700/j.bh.1001-5965.2023.0215 |
| [19] | LIU R，BAI J Q，QIU Y S. Research and application of parallel infill sampling method based on non-dominated sorting[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（6）：1446-1459 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2022.0831. |
| [20] | KONG B A，LU S，WANG H W. Incremental computing methods of canonical correlation analysis for compositional data streams[J]. Journal of Beijing University of Aeronautics and Astronautics，2023，49（10）：2851-2858 （in Chinese）. doi: 10.13700/j.bh.1001-5965.2021.0765. |
Figures(9) / Tables(1)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
PENG Lin-ping. Strong Stability with Respect to Part of the Variablesin Systems with Impulse Effect[J]. Journal of Beijing University of Aeronautics and Astronautics, 2001, 27(3): 365-368. (in Chinese)
DownLoad:
