A Survey on Graph-Based Anomaly Detection Methods in Social Networks

Document Type : Original Article

Authors

1 imam hossein university

2 shahed university

Abstract

The use of social networks to communicate and share information has grown dramatically in recent years. These networks are nowadays used in most areas such as education, business, health and entertainment. The large amount of valuable information on social networks has made them the main target of malicious users, such as spammers and fraudsters, for carrying out abusive and illegal activities. The abnormal and unexpected behavior of these users is identified using anomaly detection methods. Detection of anomalies is important in preventing fraud, dissemination of counterfeit information and configuration of attacks in these networks.  Anomalies are static or dynamic, with or without attributes. In this paper, various methods developed for anomaly detection in social networks have been investigated and categorized and an overview provided on anomaly detection, its applications, existing challenges and key areas for future research.       

Keywords

References

1. بسطامی، اسماعیل، جوادزاده، محمدعلی، تحلیل مرکزیت شبکه‌های اجتماعی در فضای سایبری با رویکرد مقابله با تهدیدات نرم، فصلنامه پدافند غیرعامل، شماره 23، صفحات 78-69، 1394.  ##
Z. Papacharissi, “Community, and Culture on Social Network Sites,” A Networked Self: Identity, New York, Routledge, 2010.##
“Worldwide Social Networks Users,” eMarketer, 2017.##
X. Ying, X. Wu, and D. Barbara, “Spectrum based fraud detection in social networks,” IEEE 27th International Conference of Data Engineering (ICDE), 2011.##
M. Fire, G. Katz, and Y. Elovici, “Strangers intrusion detection-detecting spammers and fake profiles in social networks based on topology anomalies,” ASE Human Journal, vol. 1, pp. 26-39, 2012.##
D. H. Chau, S. Pandit, and C. Faloutsos, “Detecting fraudulent personalities in networks of online auctioneers,” Knowledge Discovery in Databases: PKDD, 2006.##
D. Toshniwal and S.Yadav, “Adaptive Outlier Detection in Streaming Time Series,” International Conference on Asia Agriculture and Animal, 2011.##
V. Chandola, A. Banerjee, and V. Kumar, “Anomaly detection: A survey,” ACM Computing Surveys (CSUR), vol. 41, pp. 1-72, 2009.##
V. Barnett and T. Lewis, “Outliers in Statistical Data,” 3rd Edition, John Wiley & Sons, 1994.##
V. Hodge and J. Austin, “A survey of outlier detection methodologies,” Artificial Intelligence Review, vol. 22, pp. 85–126, 2004.##
V. Chandola, “Anomaly detection for symbolic sequences and time series data,” Ph.D. thesis, university of Minnesota, 2009.##
R. Hassanzadeh, R. Nayak, and D. Stebila, “ Analyzing the Effectivenees of Graph Metrics for Anomaly Detection in Online Social Networks,” Web Information Systems Engineering (WISE ), 2012.##
M. E. Newman, D. J. Watts, and S. H. Strogatz, “Random Graph Models of Social Networks,” National Academy of Sciences, vol. 99, pp. 2566-2572, 2002.##
R. Yu, X. He, and Y. Liu, “Glad: group anomaly detection in social media analysis,” ACM Transactions on Knowledge Discovery from Data (TKDD), 2015.##
Y. Chen and B. Malin, “Detection of anomalous insiders in collaborative environments via relational analysis of access logs,” 1st ACM conference on Data and application security and privacy, 2011.##
Y. Chen, S. Nyemba, and B. Malin, “Auditing medical records accesses via healthcare interaction networks,” AMIA Annual Symposium Proceeding, 2012.##
Y. Chen, S. Nyemba, W. Zhang, and B. Malin, “Specializing network analysis to detect anomalous insider actions,” Security informatics, vol. 1, pp. 1-24, 2012.##
N. Jindal, B. Liu, and E. P. Lim, “Finding unusual review patterns using unexpected rules,” 19th ACM international conference on Information and knowledge management, 2010.##
R. Kaur and S. Singh, “A survey of data mining and social network analysis based anomaly detection techniques,” Egyptian Informatics Journal, vol. 17, pp. 199-216, 2016.##
D. Savage, X. Zhang, X. Yu, P. Chou, and Q. Wan, “Anomaly detection in online social networks,” Social Networks, vol. 39, pp. 62-70, 2014.##
Z. Chen, W. Hendrix, and N. F. Samatova, “Community-based anomaly detection in evolutionary networks,” Intell. Inf. Syst., vol. 39, pp. 59-85, 2012.##
N. A. Heard, D. J. Weston, K. Platanioti, D. J. Hand, and others, “Bayesian anomaly detection methods for social networks,” The Annals of Applied Statistics, vol. 4, pp.    645–662, 2010.##
S. Pandit, D. Chau, S. Wang, and C. Faloutsos  “Netprobe, A fast and scalable system for fraud detection in online auction networks,” 16th international conference on World Wide Web, 2007.##
L. Akoglu, M. McGlohon, and C. Faloutsos, “Anomaly Detection in Large Graphs,” School of Computer Science Carnegie Mellon University, 2009.##
F. Y. Edgeworth, “On discordant observations,” Philosophical Magazine, pp. 364-375, 1887.##
N. Shrivastava, A. Majumder, and R. Rastogi, “Mining (social) network graphs to detect random link attacks,” In Data Engineering, IEEE 24th International Conference on, 2008.##
L. Akoglu, M. McGlohon, and C. Faloutsos, “Oddball: spotting anomalies in weighted graphs,” Advances in Knowledge Discovery and Data Mining, 2010.##
M. A. Doostari, R. Zeinali, H. Lashkari, and M. Ajamzamani, “Anomaly Detection in Cliques of Online Social Networks Using Fuzzy Node-Fuzzy Graph,” Journal of Basic and Applied Scientific Research, vol. 3, pp. 614-626, 2013.##
R. Hassanzadeh and R. Nayak, “A semi-supervised         graph-based algorithm for detecting outliers in online-social-networks,” 28th Annual ACM Symposium on Applied Computing, 2013.##
S. Y. Bhat and M. Abulaish, “Communities Against Deception in Online Social Networks,” Computer fraud Security, vol. 2, pp. 8-16, 2014.##
M. Abulaish and S. Y. Bhat, “A densitybased based approach to detect community evolutionary events in online social networks,” 12th Social Network Analysis and Mining, 2013.##
D. Chakrabarti, “Autopart: parameter-free graph partitioning and outlier detection,” 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2004.##
X. Xu, N. Yuruk, Z. Feng, and T. A. Schweiger, “Scan: a structural clustering algorithm for networks,” 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007.##
H. Sun, J. Huang, J. Han, H. Deng, and P. Zhao, “gskeletonclu: Density-based network clustering via structure-connected tree division or agglomeration,” 10th IEEE International on DATA Mining, 2010.##
H. Tong and C. Y. Lin, “Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection,”  11th SIAM International Conference on Data Mining, 2011.##
B. Miller, N. Bliss, and P. J. Wolfe, “Subgraph detection using eigenvector L1 norms,” 24th Annual Conference on Neural Information Processing Systems, 2010.##
B. Miller, M. S. Beard, N. T. Bliss, and Others, “Eigenspace analysis for threat detection in social networks,” 14th IEEE International Conference on Information Fusion, 2011.##
B. Miller, M. Beard, P. Wolfe, and N. Bliss, “A spectral framework for anomalous subgraph detection,” Signal Processing, IEEE Transactions, vol. 63, pp. 4191–4206, 2015.##
C. C. Noble and D. J. Cook, “Graph-based anomaly detection,” 9th ACM SIGKDD international conference on Knowledge discovery and data mining, 2003.##
L. B. Holder, D. J. Cook, S. DjokO, et al, “Substucture Discovery in the SUBDUE System,” 3rd International Conference on Knowledge Discovery and Data Mining, 1994.##
W. Eberle and L. Holder, “Anomaly detection in data represented as graphs,” Intelligent Data Analysis, vol. 11, pp. 663–689, 2007.##
M. Davis, W. Liu, P. Miller, and G. Redpath, “Detecting Anomalies in Graphs with Numeric Labels,” 20th ACM International Conference on Information and Knowledge Management, 2011.##
M. Gupta, A. Mallya, S. Roy, J. Cho, and J. Han, “Local learning for mining outlier subgraphs from network datasets,” SIAM International Conference on Data Mining, 2014.##
J. Li, H. Dani, X. Hu, and H. Liu, “Radar: Residual Analysis for Anomaly Detection in Attributed Networks,” 26th International Joint Conference on Artificial Intelligence, 2017.##
X. Hu, J. Tang, Y. Zhang, and H. Liu, “Social Spammer Detection in Microblogging,” 23th International Joint Conference on Artificial Intelligence, 2013.##
X. He, D. Cai and P. Niyogi, “Laplacian Score for Feature Selection,” 18th International Conference on Neural Information Processing Systems, 2005.##
L. Ghanoui, G. Li, V. Duong, V. Pham, and Srivasta, “Sparse machine learning methods for understanding large text corpora,” Conference on Intelligent Data Understanding, 2011.##
J. Gao, F. Liang, W. Fan, C. Wang, and Y. Sun, “On community outliers and their efficient detection in information networks,” 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010.##
T. Ji, J. Gao, and D. Yang, “A Scalable Algorithm for Detecting Community Outliers in Social Networks,” International Conference on Web-Age Information Management, 2012.##
E. Müller, P. I. Sánchez , Y. Mülle, and K. Böhm, “Ranking outlier nodes in subspaces of attributed graphs,” 29th  International Conference on Data Engineering Workshops, 2013.##
P. I. Sánchez, E. Müller, F. Laforet, and F. Keller, “Statistical Selection of Congruent Subspaces for Mining Attributed Graphs,” 13th IEEE International Conference on Data Mining, 2013.##
P. I. Sánchez, E. Müller, O. Irmler, and K. Böhm, “Local context selection for outlier ranking in graphs with multiple numeric node attributes,” 26th International Conference on Scientific and Statistical Database Management, 2014.##
W. Yang, G. W. Shen, W. Wang, L. Y. Gong, and M. Yu, “Anomaly detection in microblogging via co-clustering,” Journal of Computer Science and Technology, vol. 30, pp. 1097–1108, 2015.##
M. A. Prado-Romero and A. Gago-Alonso, “Community Feature Selection for Anomaly Detection in Attributed Graphs,” Pattern Recognition, Image Analysis, Computer Vision, and Applications, 2017.##
V. D. Blondel, J. Guillaume, R. Lambiotte, and Lef, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, 2008.##
L. Akoglu and C. Faloutsos, “Event detection in time series of mobile communication graphs,” Army Science Conference, 2010.##
D. Koutra, E. E. Papalexakis, and C. Faloutsos, “Tensorsplat: Spotting latent anomalies in time,” 16th IEEE Panhellenic Conference on Informatics, 2012.##
W. Yu, C. C. Aggarwal, S. Ma, and h. Wang, “On anomalous hotspot discovery in graph streams,” 13th IEEE International Conference on Data Mining, 2013.##
M. Gupta, J. Gao, Y. Sun, and J. Han, “Integrating community matching and outlier detection for mining evolutionary community outliers,” 18th international conference on Knowledge discovery and data mining, 2012.##
T. Ji, D. Yang, and J. Gao, “Incremental local evolutionary outlier detection for dynamic social networks,” 13th European Conference on Machine Learning and Knowledge Discovery in Databases, 2013.##
M. Mongiovi, P. Bogdanov, R. Ranca, E. E. Papalexakis, C. Faloutsos, and A. K. Singh, “Netspot: Spotting significant anomalous regions on dynamic networks,” SIAM International Conference on Data Mining, 2013.##
Z. Huang and D. D. Zeng, “A link prediction approach to anomalous email detection,” International Conference on  Systems, Man and Cybernetics, 2006.##
B. Thompson and T. Eliassi-Rad, “Discovery and analysis of patterns and anomalies in volatile time-evolving networks 1st  Workshop on Information in Networks,” 2009.##
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
E. E. Papalexakis, C. Faloutsos, and N. Sidiropoulos, “Parcube: Sparse parallelizable tensor decompositions,” Machine Learning and Knowledge Discovery in Databases, 2012.
Y. Yasami and F. Safaei, “A statistical infinite feature cascade-based approach to anomaly detection for dynamic social networks,” Computer Communications, vol. 100, pp. 52-64, 2017.
J. Van Gae, L. J. The, and Z. Ghahramani, “The infinite factorial hidden Markov model,”  23rd  Annual Conference on Neural Information Processing Systems, 2009.
P. V. Bindu and T. Santhi, “Mining Social Networks for Anomalies: Methods and Challenges,” Journal of Network and Computer Applications, vol. 68, pp. 213-229, 2016.
X. H. Dang, I. Assent, R. T. Ng, A. ZimekSchub, and Schub, “Discriminative features for identifying and interpreting outliers,” 30th IEEE International Conference on Data Engineering, 2014.

Files

History

  • Receive Date: 06 November 2018
  • Accept Date: 06 March 2019
  • Publish Date: 22 November 2019

Share

How to cite

Statistics