# The Resistance Perturbation Distance: A Metric for the Analysis of Dynamic Networks

arXiv: https://arxiv.org/abs/1605.01091 · HTML: https://mlsanity.com/paper/1605.01091/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2016.

## Built on by (most cited first, 5 of 5)

- [On a linear fused Gromov-Wasserstein distance for graph structured data](https://mlsanity.com/paper/2203.04711/) (2022)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [Measuring Similarity in Causal Graphs: A Framework for Semantic and Structural Analysis](https://mlsanity.com/paper/2503.11046/) (2025)
- [Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications](https://mlsanity.com/paper/2608.27500/) (2026)

## Abstract (arXiv)

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.