A novel approach for graph-based global outlier detection in social networks. (2018)

• Record Type: Journal Article
• Authors: Zrira, Nabila; Mekouar, Soufiana; Bouyakhf, El Houssine
• Is Part Of: International journal of security and networks. Volume 13:Number 2(2018)
• Page Start: 108
• Page End: 128
• Publication Date: 2018
• Subjects: global outlier detection -- social network graph -- graph matching -- Euclidean and Gower formulas -- Hungarian method; Computer networks -- Security measures -- Periodicals; 005.805
• Languages: English
• ISSNs: 1747-8405

Abstract

Graph representation has high expensive power to model and detect complicated structural patterns. One important area of data mining that uses such representation is anomaly detection, particularly in the social network graph to ensure network privacy, and uncover interesting behaviour. In this work, we suggest a new approach for global outlier detection in social networks based on graph pattern matching. A node signature extraction is combined with an optimal assignment method for matching the original graph data with the graph pattern data, in order to detect two formalised anomalies: anomalous nodes and anomalous edges. First, we introduce Euclidean and Gower formulas to compute the distance between graphs. Then, we conduct graph pattern matching in cubic-time by defining a node-to-node cost in an assignment problem using the Hungarian method. Finally, the obtained experimental results demonstrate that our approach performs on both synthetic and real social network datasets.