The Resistance Perturbation Distance: A Metric on the Space of Connected Graphs of a Fixed Size
Channel: Berkeley Institute for Data Science (BIDS)
Date: 29/04/2016

BIDS Data Science Lecture Series | April 29, 2016 | 1:10-2:30 p.m. | 190 Doe Library, UC Berkeley

Speaker: Francois Meyer, Professor, Departments of Electrical Engineering and Applied Mathematics, University of Colorado, Boulder

A fundamental goal of the study of dynamic graphs is the identification of universal patterns that uniquely couple the dynamic evolution of connectivity with the specific topology of the network—in essence, the discovery of universal spatio-temporal patterns.

In order to study the complicated interplay between temporal changes in connectivity and the underlying dynamical processes taking place on the graph, we propose a new family of graph metrics. These metrics can be tuned to quantify structural changes of the graph toploogy that happen at different scales.

We present fast computational algorithms to quickly compute approximations to the metrics. Results of experiments conducted on synthetic and real data suggest that this new family of metrics can identify changes in dynamic graphs and could be used to infer changes in the hidden variables that govern the evolution of such graphs.

This is work in collaboration with Dr. Nathan Monnig.