Concurrent Detection of Compact Anomalous Subgraphs in Large Social Networks

Document Type : Original Article

Authors

Computer Engineering Department, Shahed University, Tehran, Iran. Acoustic Research Center , Shahed University, Tehran, Iran.

Abstract

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.

Keywords


[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.##
Volume 9, Issue 2 - Serial Number 34
Serial No. 34, Summer Quarterly
June 2021
Pages 179-194
  • Receive Date: 12 November 2020
  • Revise Date: 10 December 2020
  • Accept Date: 11 January 2021
  • Publish Date: 22 June 2021