Spectral Measures of Distortion for Change Detection in Dynamic Graphs

Luca Castelli Aleardi1, Semih Salihoglu2, Gurprit Singh3, Maks Ovsjanikov1
1LIX, Ecole Polytechnique, France, 2University of Waterloo, Canada,
3Max Planck Institute for Informatics, Saarbrücken
International Conference on Complex Networks and their Applications
(presented at Complex Networks 2018)
Snow

Abstract

We propose a novel framework for detecting, quantifying and visualizing changes between two snapshots of a dynamic network. Unlike existing approaches, which can be sensitive to minor and isolated changes, and are often based on heuristics, we show how a theoretically justified, inherently multi-scale notion of change, or distortion, can be defined and computed using spectral graph-theoretic tools. Our primary observation is that informative, robust and multi-scale measures of change can be obtained by computing a real-valued function (which we call the distortion function) on the nodes of the input graph, via the optimization of a pre-defined distortion energy in a provably optimal way. Based on extensive tests on a wide variety of networks, we demonstrate the ability of our approach to highlight the evolution of the network in an informative and multi-scale manner.

Material

Paper

Copyright Disclaimer

The Author(s). This is the author's version of the work. It is posted here by permission of the Complex Networks association for your personal use. Not for redistribution. The definitive version is available at link.springer.com.

Imprint / Data Protection