The Detection of Anomalous Users in Location-Based Social Networks by Using Graph Rules

Document Type : Original Article

Authors

1 MSc. Student in software engineering, Kashan branch, Islamic Azad university, Kashan, Iran

2 Assistant Prof. faculty of computer and electrical engineering, Kashan branch, Islamic Azad university, Kashan, Iran

Abstract

An analysis of social networks is necessary to detect anomalous users, due to the popularity of these networks. This paper aims to detect anomalous users in location based social networks. For this purpose, an ego graph is computed for each user, and the five variables vertex degree, edge size, edge weight, betweenness centrality and eigenvector centrality are calculated with respect to the weights of the edges in this graph. Then six relationships between two of these variables are made up, and for each of these relationships, the line equation is obtained in the coordinate system of the two variables. This equation is used to predict the value of the variables. Based on this predicted value, the user's score is determined, and anomalous users are detected. The proposed method investigates anomalies in the friendship graph, location of residence and interests of users. The results indicate that the proposed method has been able to detect anomalous users by examining the scores of star and clique structures in the graph.

Keywords

Main Subjects

References

 
Akoglu, L. Chandy, R. Faloutsos, C. Opinion fraud detection in online reviews by network effects. ICWSM 2013; 13:2–11 DOI:10.1609/icwsm.v7i1.14380
Akoglu, L. Faloutsos, C. Event detection in time series of mobile communication graphs. In: Army Science Conference. 2010. p. 77–79. Doi:  10.1145/3018661.3018669
 Akoglu, L. McGlohon, M. Faloutsos, C. Oddball: Spotting anomalies in weighted graphs. In: Advances in Knowledge Discovery and Data Mining. Springer; 2010. p. 410–421. DOI:10.1007/978-3-642-13672-6_40
Chakrabarti, D. Zhan, Y. Faloutsos, C. R-MAT: A Recursive Model for Graph Mining. In: SDM. SIAM; volume 4; 2004. p. 442–446. DOI:10.1137/1.9781611972740.43
Gupta, M. Gao, J. Aggarwal, C. Han, J. Outlier detection for temporal data. Synthesis Lectures on Data Mining and Knowledge Discovery 2014a;5(1):1–129 DOI:10.2200/S00573ED1V01Y201403DMK008
Hassanzadeh, R. & Nayak, R. (2013). A semi-supervised graph-based algorithm for detecting outliers in online-social-networks. In Proceedings of the 28th Annual ACM Symposium on Applied Computing (pp. 577-582). ACM DOI:10.1145/2480362.2480474 .
Hassanzadeh, R., Nayak, R. A rule-based hybrid method for anomaly detection in online-social-network graphs. In: Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on. IEEE; 2013a. p. 351–357. DOI:10.1109/ICTAI.2013.60
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., Faloutsos, C. It’s who you know: graph mining using recursive structural features. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2011. p. 663–671 DOI:10.1145/2020408.2020512
Kaur, R., & Singh, S. (2015, December). Detecting anomalies in online social networks using graph metrics. In 2015 annual IEEE India conference (INDICON) (pp. 1-6). IEEE. DOI:10.1109/INDICON.2015.7443800
Levandoski, J. J., Sarwat, M., Eldawy, A., & Mokbel, M. F. (2012, April). Lars: A location-aware recommender system. In Data Engineering (ICDE), 2012 IEEE 28th International Conference on (pp. 450-461). IEEE DOI:10.1109/ICDE.2012.54
Nadi,n,(2016) anomaly detection in social networks using multi-dimensional array decomposition(in Persian) DOI:10.1109/BESC.2017.8256408
Sarwat, M., Levandoski, J. J., Eldawy, A., & Mokbel, M. F. (2014). LARS*: An efficient and scalable location-aware recommender system. IEEE Transactions on Knowledge and Data Engineering, 26(6), 1384-1399. DOI: 10.1109/TKDE.2013.29
Scott, J. Social network analysis: developments, advances, and prospects. Social network analysis and mining 2011;1(1):21–26 DOI:10.1007/s13278-010-0012-6
Tong, H., Lin, C.Y. Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection. In: SDM. SIAM; 2011. p. 143–153. DOI:10.1137/1.9781611972818.13
Yang, W., Shen, G.W., Wang, W., Gong, L.Y., Yu, M., Dong, G.Z. Anomaly detection in microblogging via co-clustering. Journal of Computer Science and Technology 2015;30; 30(5):1097–1108. DOI:10.1007/s11390-015-1585-3
Send comment about this article
CAPTCHA Image

Files

Share

How to cite

Statistics