Authors: Nabila Zrira; Soufiana Mekouar; El Houssine Bouyakhf
Addresses: Faculty of Sciences, Mohammed V University, Rabat, Morocco ' Faculty of Sciences, Mohammed V University, Rabat, Morocco ' Faculty of Sciences, Mohammed V University, Rabat, Morocco
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.
Keywords: global outlier detection; social network graph; graph matching; Euclidean and Gower formulas; Hungarian method.
International Journal of Security and Networks, 2018 Vol.13 No.2, pp.108 - 128
Received: 27 Mar 2017
Accepted: 06 Jan 2018
Published online: 21 Jun 2018 *