A graph metric for the structural analysis of dynamic networks

Orateur: MEYER François
Localisation: Université du Colorado, États-Unis
Type: Séminaire cristolien d'analyse multifractale
Site: UPEC
Salle: FSEG 15
Date de début: 02/03/2017 - 11:00
Date de fin: 02/03/2017 - 11:00

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.