Abstract

Dynamic graphs arise in a variety of real-world situations: from social networks, to engineered physical networks, to graphs associated with data sets (e.g. financial transactions) that vary in time. The challenges are the need to develop robust tools and metrics for comparing graphs at different times, in order to model statistical significant changes, and capture anomalies: in real-world situation a graph/network will vary stochastically in time with vertex/edge additions/deletions, and classical tools such as graph isomorphism are not robust enough to handle such changes. We use multiscale decompositions of graph and random walks at multiple scales to introduce metrics of change (in time) of a graph, that allow use to capture changes of different magnitude at different scales and locations on the graph. We apply these techniques to synthetic graphs as well as real world data sets, and discuss strengths and weaknesses of this approach.