Title: A novel approach for graph-based global outlier detection in social networks

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.

DOI: 10.1504/IJSN.2018.092473

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article