The Resistance Perturbation Distance: A Metric on the Space of Connected Graphs of a Fixed Size

Data Science Lecture Series


April 29, 2016
1:00pm to 2:30pm
190 Doe Library
Get Directions

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 topology 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.


Francois Meyer

Professor, Departments of Electrical Engineering and Applied Mathematics, University of Colorado, Boulder

Francois Meyer graduated with Honors from Ecole Nationale Superieure d'Informatique et de Mathematiques Appliquees, Grenoble, in 1987, with a MS in applied mathematics. He received a PhD degree in electrical engineering from INRIA, France, in 1993. Meyer worked on the thermonuclear fusion program of the French Nuclear Energy Agency during his military service.
Meyer is currently a professor with the Departments of Electrical Engineering and Applied Mathematics at the University of Colorado, Boulder. He was previously an assistant professor at Yale University (1997–1999), a visiting professor at the Institute Henri Poincare (Paris), a senior fellow at the Institute of Pure and Applied Mathematics at (UCLA, 2004), a visiting research scholar at Princeton University (2007), and a visiting scholar at the Institute for Computational and Experimental Research in Mathematics at Brown University (2014).

Francois Meyer's research group works on the development of statistical and computational methods to represent, filter, and analyze data in order to detect interesting patterns and make inferences from large and noisy datasets.