Skip to content



Multiscale Methods for the Analysis of Dynamic Graphs

Maggioni, M (Duke)
Friday 25 June 2010, 09:45-10:30

Seminar Room 1, Newton Institute


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.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧