8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – Tom Church
    Commented May 21, 2011 at 16:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 21, 2011 at 19:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

I don't, however, see an easy way to take advantage of the fact that you are not interested in the entire matrix of distances, but rather just the average distance.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .