تشخیص همزمان زیرگراف های فشرده ناهنجار در شبکه های اجتماعی بزرگ

نوع مقاله : مقاله پژوهشی

نویسندگان

1 کارشناسی ارشد گروه مهندسی کامپیوتر، دانشکده فنی مهندسی، دانشگاه شاهد، تهران، ایران

2 هیات علمی دانشکده فنی مهندسی دانشگاه شاهد

چکیده

این مقاله رویکرد جدید تشخیص ناهنجاری بدون علامت براساس پردازش سیگنال های مرتبط با اطلاعات محلی ارایه می دهد که قادر به تعیین همزمان زیرگراف های فشرده ناهنجار در گراف ناشناخته نویزی شبکه های اجتماعی بزرگ است. همچنین الگوریتم جدید نمونه برداری مبتنی بر نمونه برداری فشرده جهت بازیابی ویژگی های تنک شبکه های ثابت ارایه داده که هدفش بهبود دقتِ تشخیص ناهنجاری همراه با کاهش پیچیدگیِ نمونه برداری داده ها است. نتایج آزمایشات تجربی با داده های مصنوعی و واقعی شبکه های اجتماعی ‌در مقایسه با مهم ترین روش های علمی نشان داد که رویکرد پیشنهادی علاوه بر برخورداری از دقت تشخیص همزمان چندین زیرگراف فشرده، پیچیدگی محاسباتی را از O(n^4 √(log⁡n )) به O(n^2) در شبکه n گره ای کاهش داده و به آسانی قابل کاربرد در شبکه های پویای پیچیده است.

کلیدواژه‌ها


عنوان مقاله [English]

Concurrent Detection of Compact Anomalous Subgraphs in Large Social Networks

نویسندگان [English]

  • M. Shah Hosseini 1
  • A. Mahabadi 2
1
2 Computer Engineering Department, Shahed University, Tehran, Iran. Acoustic Research Center , Shahed University, Tehran, Iran.
چکیده [English]

This paper presents a new approach to the detection of asymptomatic anomalies based on the signal processing related to local information of graph that simultaneously detects small compact anomalous subgraphs in the unknown graphs of large social networks. It also introduces a novell sampling algorithm based on compressive sensing to retrieve the sparse properties of static networks, which aims to improve the accuracy of anomaly detection while reducing the complexity of data sampling. The results of experimental experiments with artificial random and real datasets of social networks in comparison with the state-of-the-art methods showed that the proposed approach, in addition to having the accuracy of simultaneous detection of anomalous compact subgraphs, the computational complexity reduced from O(n^4 √(log⁡n )) to O(n^2) in the n node networks and is easily applicable in complex dynamic networks.

کلیدواژه‌ها [English]

  • Anomaly Detection
  • Anomalous Subgraphs
  • Signal Processing
  • Compressive Sensing
  • Graph Theory
[1]     Yu, Rose, et al., “A Survey on Social Media Anomaly Detection.” ACM SIGKDD Explorations Newsletter, vol. 18(1), pp. 1-14, 2016.##
[2]     Y. Yasami and F. Safaei, “A statistical in nite feature cascade-based approach to anomaly detection for dynamic social networks,” Computer Communications, vol. 100, pp. 52-64, 2017.##
[3]     Xiong, Fei, Yun Liu, and Junjun Cheng, “Modeling and predicting opinion formation with trust propagation in online social networks,” Communications in Nonlinear Science and Numerical Simulation, vol. 44, pp. 513-524, 2017.##
[4]     N. Rastogi and J. Hendler, “Graph Analytics for anomaly detection in homogeneous wireless networks A Simulation Approach,” arXiv preprint arXiv:1701.06823, 2017.##
[5]     M. Ahmed, A. N. Mahmood, and J. Hu, “ A survey of network anomaly detection techniques,” J. Netw. Comput. Appl., vol. 60, p. 1931, 2016.##
[6]     A. Zargar, A. Nowroozi, and R. Jalili, “XABA: A            zero-knowledge anomaly-based behavioral analysis method to detect insider threats,” Information Security and Cryptology (ISCISC), 2016 13th International Iranian Society of Cryptology Conference on. IEEE, 2016.##
[7]     D. Mutz, F. Valeur, G. Vigna, and C. Kruegel, “Anomalous system call detection, ACM Trans,” Inf. Syst. Secur., vol. 9(1), p. 6193, 2006.##
[8]     R. Chaker, Z. Al Aghbari, and I. N. Junejo, “Social network model for crowd anomaly detection and localization.” Pattern Recognition, vol. 61, pp. 266-281, 2017.##
[9]     V. Krebs, “Mapping networks of terrorist cells,” Connections, vol. 14(3), p. 4352, 2002.##
[10]  E. Bastami, A. Mahabadi, and E. Taghizadeh, “A   gravitation-based link prediction approach in social networks,” Swarm Evol Comput., vol. 44, pp.  176–186, 2019.##
[11]  B. A. Miller, et al., “Detection theory for graphs,” Lincoln Laboratory Journal, vol. 20(1), pp. 10-30, 2013.##
[12]  A. Mohiuddin, A. N. Mahmood, and J. Hu, “A survey of network anomaly detection techniques.” Journal of Network and Computer Applications. 60 (2016): 19-31.##
[13]  Miller, B. A., Beard, M. S., Wolfe, P. J., & Bliss, N. T. “A spectral framework for anomalous subgraph detection,” IEEE Transactions on Signal Processing, vol. 63(16), pp.   4191-4206, 2015.##
[14]  W. Xu, E. Mallada, and A. Tang, “Compressive sensing over graphs,” INFOCOM, Proceedings IEEE, pp. 2087-2095, 2011.##
[15]  S. Wang, J. Cao, and P. Yu, “Deep learning for spatio-temporal data mining: A survey,” IEEE Transactions on Knowledge and Data Engineering, 2020.##
[16]  Y. Wang, et al., “Data-Driven Sampling Matrix Boolean Optimization for Energy-E cient Biomedical Signal Acquisition by Compressive Sensing,” IEEE Transactions on Biomedical Circuits and Systems, 2016.##
[17]  V. J. Barranca, et al., “Ecient image processing via compressive sensing of integrate-and-fire neuronal network dynamics,” Neurocomputing, vol. 171, pp. 1313-1322, 2016.##
[18]  J. Xiaobo, et al., “An improved sparse reconstruction algorithm for speech compressive sensing using structured priors,” Multimedia and Expo (ICME), 2016 IEEE International Conference, pp. 1-6, 2016.##
[19]  Z. Liu, et al., “Path reconstruction in dynamic wireless sensor networks using compressive sensing,” IEEE/ACM Transactions on Networking, vol. 24(4), pp. 1948-1960, 2016.##
[20]  H. T. Wai, A. Scaglione, and A. Leshem, “Active sensing of social networks,” IEEE Transactions on Signal and Information Processing over Networks, vol. 2(3), pp.    406-419, 2016.##
[21]  J. Madhuka, et al., “Compressive sensing for efficient health monitoring and effective damage detection of structures,” Mechanical Systems and Signal Processing, vol. 84, pp.    414-430, 2017.##
[22]  W. Xue, et al., “Kryptein: a compressive-sensing-based encryption scheme for the internet of things,” Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks, pp. 169-180, 2017.##
[23]  N. Shrivastava, A. Majumder, and R. Rastogi, “Mining (social) network graphs to detect random link attacks,” Proc. IEEE Int. Conf. on Data Engineering. (2008): 486-495.##
[24]  C. C. Noble and D. J. Cook, “Graph-based anomaly detection,” Proce. ACM SIGKDD Int. Conf. on Knowledge discovery and data mining, pp. 631-636, 2003.##
[25]  W. Eberle and L. Holder, “Anomaly detection in data represented as graphs,” Intelligent Data Analysis, vol.11(6), pp.  663-689, 2007.##
[26]  B. Miller, N. Bliss, and P. J. Wolfe, “Subgraph detection using eigenvector L1 norms,” Proce. Int. Conf. on Neural Information Processing Systems, pp. 1633-1641, 2010.##
[27]  B. A. Miller, M. S. Beard, and N. T. Bliss, “Eigenspace analysis for threat detection in social networks,” in Proce. IEEE Int. Conf. on Information Fusion.  (2011): 1-7.##
[28]  Singh N., Miller B. A., Bliss N. T., Wolfe P. J. “Anomalous subgraph detection via sparse principal component analysis,” Proce. IEEE Statistical Signal Process, pp. 485–488, 2011.##
[29]  P. Bindu and P. S. Thilagam, “Mining social networks for anomalies: Methods and challenges,”  Netw. Comput. Appl. vol. 68, pp. 213-229, 2016.##
[30]  Y. Yasami and F. Safaei, “A statistical infinite feature cascade-based approach to anomaly detection for dynamic social networks,” Comput. Communi., 2016.##
[31]  A. Fattaholmanan, “Sparse Recovery in Peer-to-Peer Networks via Compressive Sensing,” M.Sc. Thesis Dept. Computer Engineering (CE), Sharif University of Technology, 2012.##
[32]  J. Haupt, W. U. Bajwa, M. Rabbat, and R. Nowak, “Compressed sensing for networked data,” IEEE Signal Processing Magazine, vol. 25(2), pp. 92-101, 2008.##
[33]  A. Fattaholmanan, H. R. Rabiee, P. Siyari, A. Soltani-Farani, and A. Khodadadi, “Peer-to-peer Compressive Sensing for Network Monitoring,” IEEE Commu. Letters, vol. 19(1), pp. 38-41, 2015.##
[34]  M. Mahyar, “Detection of top-k central nodes in social networks: A compressive sensing approach,” IEEE Inte. Conf. on Advances in Social Networks Analysis and Mining, pp. 902-909, 2015.##
[35]  H. Mahyar, et al., “CS-ComDet: A compressive sensing approach for inter-community detection in social networks,” Proce.  IEEE Int. Conf. on Advances in Social Networks Analysis and Mining, pp. 89-96, 2015.##
[36]  E. J. Candes, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Commun. on pure and applied mathematics, vol. 59(8), pp. 1207-1223, 2006.##
[37]  R. Tibshirani, “Regression shrinkage and selection via the lasso.” Royal Statistical Society. Series B (Methodological), pp. 267-288, 1996.##
[38]  D. Savage, et al., “Anomaly detection in online social networks,” J. Soc. Netw., vol. 39, pp. 62-70, 2014.##
[39]  D. Chakrabarti, Y. Zhan, and C. Faloutsos, “R-MAT: A Recursive Model for Graph Mining,” SDM, pp.  442-446, 2004.##
[40]  R-MAT source code, NetMine package. [Online] Available:  http://faculty.mccombs.utexas.edu/deepayan.chakrabarti/mywww/software/NetMine-Basic-03-30-2004.tgz.##
دوره 9، شماره 2 - شماره پیاپی 34
شماره پیاپی 34، فصلنامه تابستان
تیر 1400
صفحه 179-194
  • تاریخ دریافت: 22 آبان 1399
  • تاریخ بازنگری: 20 آذر 1399
  • تاریخ پذیرش: 22 دی 1399
  • تاریخ انتشار: 01 تیر 1400