  To quantify the fundamental 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. In this
work, we propose a family of distances that can be tuned to quantify structural
changes occurring on a graph at different scales: from the local scale formed
by the neighbors of each vertex, to the largest scale that quantifies the
connections between clusters, or communities. Our approach results in the
definition of a true distance, and not merely a notion of similarity. We
propose fast (linear in the number of edges) randomized algorithms that can
quickly compute an approximation to the graph metric. The third contribution
involves a fast algorithm to increase the robustness of a network by optimally
decreasing the Kirchhoff index. Finally, we conduct several experiments on
synthetic graphs and real networks, and we demonstrate that we can detect
configurational changes that are directly related to the hidden variables
governing the evolution of dynamic networks.
