Université Paris-Est Université Paris-Est - Marne-la-Vallée Université Paris-Est - Créteil Val-de-Marne Centre National de la Recherche Scientifique

A graph metric for the structural analysis of dynamic networks

02/03/2017 - 11:00 - 12:00
MEYER François
Université du Colorado

To quantify the evolution of time-varying networks, and detect abnormal behavior, one needs a notion of temporal difference that captures significant organizational changes between two successive instants.

We propose a family of distances to quantify structural changes occurring on a graph at different scales. We design a randomized algorithm, which scales nearly linearly in the number of edges, to compute an approximation to this novel graph distance.

We demonstrate that temporal changes in this graph distance can be used to detect configurational changes that are directly related to the hidden variables governing the evolution of dynamic networks.

This is work in collaboration with Nathan Monnig, and Peter Wills.