Details

Autor(en) / Beteiligte

• Guanhua Yan
• Eidenbenz, Stephan

Titel

Sim-Watchdog: Leveraging Temporal Similarity for Anomaly Detection in Dynamic Graphs

Ist Teil von

• 2014 IEEE 34th International Conference on Distributed Computing Systems, 2014, p.154-165

Ort / Verlag

IEEE

Erscheinungsjahr

2014

Quelle

IEEE Electronic Library Online

Beschreibungen/Notizen

• Graphs are widely used to characterize relationships or information flows among entities in large networks or distributed systems. In this work, we propose a systematic framework that leverages temporal similarity inherent in dynamic graphs for anomaly detection. This framework relies on the Neyman-Pearson criterion to choose similarity measures with high discriminative power for online anomaly detection in dynamic graphs. We formulate the problem rigorously, and after establishing its inapproximibility result, we develop a greedy algorithm for similarity measure selection. We apply this framework to dynamic graphs generated from email communications among thousands of employees in a large research institution and demonstrate that it works effectively on a set of more than 100 candidate graph similarity measures.