# Change in the average geodesic distance of a graph when flipping a single edge

Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra algorithm?

I'm currently doing this by expensively copying the graph, changing the edge, and then calculating the average geodesic distance of the new graph (using Dijkstra's algorithm) and subtracting it from the average geodesic distance of the original graph..

Is there a more clever way to to this?

notes:

(1) By flipping a edge I mean the following operation: add the edge if it's absent and remove it if it's present.

(2) Good approximations are welcomed. It's part of a Monte Carlo simulation, so I must repeat this calculation many, many times.

• An idle question: could it be true that if the average change in distance is low enough, then your graph is an expander? (This question will not help solve the original question, which is about efficiently computing the average change.) May 21 '11 at 16:30
• Tom: it could be that the graph consists of 2 parts with 2 edges between them such that you would have to go through one of these edges, but neither is pivotal - removing either would not change the average at all. May 21 '11 at 19:20

With the right data structures (see http://www.ams.org/mathscinet-getitem?mr=2145260), one can maintain a matrix of pairwise distances between vertices in a dynamic graph. Updating the entire matrix after modifying an edge takes $O(n^2\log^3n)$ (amortized). This is at least better than doing a completely new all-pairs shortest path algorithm each time you modify an edge.