Adaptive analysis of graphical structural metric for anomaly detection in social networks

Subject Areas : Multimedia Processing, Communications Systems, Intelligent Systems

Mojtaba Aajami ¹ , Naser Asgari ²

1 - دانشکده مهندسی برق و کامپیوتر -دانشگاه آزاد اسلامی واحد زنجان - زنجان - ایران
2 - Faculty of Electrical and Computer Engineering, Islamic Azad University of Zanjan, Zanjan Iran

Received: 2020-12-22 Accepted : 2021-04-20 Published : 2021-03-21

Keywords: Clique, Anomaly, Social networks,

Abstract :

Introduction: Social networks are exposed to a variety of security problems due to their wide use and popularity. Therefore, identifying unusual activities in social networks is of paramount importance as it helps to obtain significant information about the behavior of unusual users and identify them.  One of the important aspects of social network analysis is to check the presence of anomalies. Anomalies in the field of social networks imply irregular and often illegal behavior. A host of methods have been proposed to detect different kinds of anomalies in social networks. According to the employed approach, these methods can be classified into three categories, namely, clustering-based, based on network structure-based, and signal processing-based. In this paper, we extend the graph structure-based approach by introducing and analyzing important graph metrics to detect abnormal activities. Theoretical and experimental evaluation using several large data sets demonstrate that the relationship between the interface node and the number of edges helps to correctly detect and rank the maximum number of anomalies.Method: The proposed method is a combination of graphical and statistical theory. First, various metrics and graph structures are calculated, and then statistical methods are used to identify and analyze unusual structures (stars and clusters).Results: Statistical and visual analysis shows that the area covered by the curve is maximum for the interface (B) compared to the number of edges (E). The results show that the proxy is a scale that can correctly detect many abnormalities. It can also be said that the relationship between the (B) and the (E) helps to predict most anomalies.Discussion: In this research, a structure-based method was presented by using graph criteria to predict abnormalities. The curve fitting method based on the graph structure was extended to detect anomalies using the combination of new graph criteria. It was observed that the relationship between the interface and the edges helped to predict a large number of anomalies that were either misclassified or missed by the Oddball method and the ABC relationship to E. The abnormality scores assigned to the nodes help predict the degree of anomalies and rank the nodes according to their irrational behavior. 

References:

[1] https://zephoria.com/top-15-valuable-facebook-statistics/

[2] D. Savage, X. Zhang, X. Yu, P. Chou, and Q. Wang, "Anomaly detection in online social networks," J. Soc. Netw, vol. 39, pp. 62-70, Octobr 2014.

[3] P. Bindu and P. S. Thilagam, "Mining social networks for anomalies: Methods and challenges," J. Netw.Comput.Appl, vol. 68, pp. 213-229, June 2016.

 [9] L. Akoglu, M. McGlohon, and C. Faloutsos, "Oddball: Spotting anomalies in weighted graphs," in Proce. Int. Conf. on Knowledge Discovery and Data Mining, pp. 410-421, June 2010.

 [4] Li H , Bhowmick SS , Sun A . Blog cascade affinity: analysis and prediction. In: Proceedings of the 18th ACM conference on information and knowledge management; 2009. p. 1117–26 .

[5] Li H , Bhowmick SS , Sun A , Cui J . Affinity-driven blog cascade analysis and prediction. Data Min Knowl Discov 2014;28(2):442–74 .

[6] Agarwal N , Liu H , Tang L , Yu PS . Identifying the influential bloggers in a community. In: Proceedings of the 2008 international conference on web search and data mining; 2008. p. 207–18 .

[7] Cai K , Bao S , Yang Z , Tang J , Ma R , Zhang L , et al. OOLAM: an opinion oriented link analysis model for influence persona discovery. In: Proceedings of the fourth ACM international conference on web search and data mining; 2011. p. 645–54 .

[8] M. Newman, Networks: an introduction: Oxford university press, 2010.

[11] L. Akoglu, M. McGlohon, and C. Faloutsos, "Oddball: Spotting anomalies in weighted graphs," in Proce. Int. Conf. on Knowledge Discovery and Data Mining, pp. 410-421, June 2010.

 [13] R. Hassanzadeh, R. Nayak, and D. Stebila, "Analyzing the effectiveness of graph metrics for anomaly detection in online social networks," in Int. Conf. on Web Inf. Syst. Eng., 2012, pp. 624-630.

 [9] Vanetti M , Binaghi E , Carminati B , Carullo M , Ferrari E . Content-based filtering in on-line social networks. In: Privacy and security issues data mining and machine learning; 2011. p. 127–40 .

[10] Viswanath B , Bashir MA , Crovella M , Guha S , Gummadi KP , Krishnamurthy B . Towards detecting anomalous user behavior in online social networks. In: Proceedings of the 23rd USENIX security symposium (USENIX security); 2014. p. 223–38 .

[12] Rezaei A , Kasirun ZM , Rohani VA , Khodadadi T . Anomaly detection in online social networks using structure-based technique. In: 8th international conference for internet technology and secured transactions (ICITST); 2013. p. 619–22 .

[14] Henderson K , Gallagher B , Li L , Akoglu L , Eliassi-Rad T , Tong H . 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; 2011. p. 663–71 .

[15] Ying X , Wu X , BarbaráD . Spectrum based fraud detection in social networks. In: Proceedings - international conference on data engineering; 2011. p. 912–23 .

[16] Miller B , Beard M , Wolfe P , Bliss N . A spectral framework for anomalous subgraph detection. IEEE Trans Signal Process 2014;63(16):4191–206 .

[17] Rattigan MJ , Jensen D . The case for anomalous link discovery. ACM SIGKDD Explorations Newsletter 2004;7(2):41–7 .

[18] Zheleva E , Getoor L , Golbeck J , Kuter U . Using friendship ties and family circles for link prediction. In: Advances in social network mining and analysis; 2010. p. 97–113 .

[19] Yang W , Shen G-W , Wang W , Gong L-Y , Yu M , Dong G-Z . Anomaly detection in microblogging via co-clustering. J Comput Sci Technol 2015;30(5):1097–108 .

[20] Aghdam SM , Navimipour NJ . Opinion leaders selection in the social networks based on trust relationships propagation. Karbala Int J Mod Sci 2016;2(2):88–97 .

 [21] Trifunovic S , Legendre F , Anastasiades C .Social trustin opportunistic networks.In: INFOCOM IEEE conference on computercommunications work- shops; 2010. p. 1–6 .

[22] Singh S , Sidhu J . An approach for determining trustworthiness of individuals in a web-based social network. Arab J Sci Eng 2016;41(2):461–77 .

[23] Breunig MM , Kriegel H-P , Ng RT , Sander J . LOF: identifying density-based local outliers. ACM Sigmod Rec 20 0 0;29(2):93–104 .

[24] Eberle W , Holder L . Anomaly detection in data represented as graphs. Intell Data Anal 2007;11(6):663–89 .