Tracking network distances: an overview

Graphs have emerged as one of the most powerful frameworks for encapsulating information about evolving interactions or similarities between a set of agents: in such studies, the data typically consist of a set of graphs tracking the state of a system at different times. A critical step in the data analysis process thus lies in the selection of an appropriate distance between networks: how can we devise a metric that is bost robust to small perturbations of the graph structure and sensitive to the properties that make two graphs similar?

In this review, we thus propose to provide an overview of some of the existing distances and to introduce a few alternative ones. In particular, we will try to provide ground and principles for choosing an appropriate distance over another, and highlight these properties on both a real-life microbiome application as well as synthetic examples. Finally, we extend our study to the analysis spatial dynamics, and show the performance of our method on a recipe network.