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.

中文翻译：

---

阻力扰动距离：动态网络分析的度量

为了量化时变网络的基本演变并检测异常行为，人们需要一种时间差异的概念来捕捉两个连续时刻之间的重大组织变化。在这项工作中，我们提出了一系列距离，可以调整这些距离以量化不同尺度上图上发生的结构变化：从每个顶点的邻居形成的局部尺度，到量化簇之间连接的最大尺度，或社区。我们的方法导致了真实距离的定义，而不仅仅是相似性的概念。我们提出了快速（边数线性）随机算法，可以快速计算图形度量的近似值。第三个贡献涉及一种通过优化降低基尔霍夫指数来提高网络鲁棒性的快速算法。最后，我们对合成图和真实网络进行了多次实验，并证明我们可以检测与控制动态网络演化的隐藏变量直接相关的配置变化。