2
$\begingroup$

For the purposes of this question we assume undirected and connected graphs.

I am trying to learn how to efficiently find pairs of nodes in a graph that are separated by prescribed distance $d.$ One direct approach would be:

  • GraphDistance can be used to find the distance between 2 given nodes.
  • GraphDistanceMatrix on the other hand, computes the distance between all pairs of nodes. For example its element [[i,j]] is the shortest path distance between nodes i and j.
  • Position can then be used to find all occurrences for a given distance value in the distance matrix.

Below is an example:

SeedRandom[123];
n = 15;
m = 20;
gr = RandomGraph[{n, m}, VertexLabels -> "Name"]

enter image description here

distmat = GraphDistanceMatrix[gr];
(*finding all pairs at distance 2*)
pos2 = Position[UpperTriangularize@distmat, 2]

{{1, 2}, {1, 6}, {1, 13}, {2, 3}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {3, 12}, {3, 14}, {4, 7}, {4, 10}, {4, 14}, {5, 6}, {5, 8}, {5, 12}, {6,
13}, {6, 14}, {7, 8}, {7, 9}, {7, 10}, {7, 11}, {7, 15}, {8, 10}, {9, 15}, {10, 11}, {10, 14}, {14, 15}}

(*Sanity check:*)
GraphDistance[gr, #[[1]], #[[2]]] & /@ pos2

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, \ 2, 2, 2, 2, 2}

Questions:

  • For larger graphs ($n\approx 5000$ and $m\approx 10000$), my approach seems to scale poorly. My own understanding of the slowness is that, I am: computing all distances using GraphDistanceMatrix, instead of skipping all those that are $>d$ anyhow, and I am finding all occurrences of $d$ with Position instead of a smaller select of them. Knowing I am interested only in pairs with distance $d$, could one optimize the calculation of GraphDistanceMatrix?

  • Would it be altogether faster, if instead of trying to find all instances, one sampled for a smaller select $n$ of pairs with distance $d$? Or possibly, approximating the problem by finding pairs that are at most $d$ apart.

Any hints and suggestions would be highly appreciated.

Improve this question
$\endgroup$
  • $\begingroup$ Perhaps you can map AdjacencyList[] all over your graph's vertices, and then delete dupes. $\endgroup$ – J. M.'s ennui♦ Nov 19 '19 at 16:22
  • 1
    $\begingroup$ GraphDistanceMatrix[g, d] will give you the distance only up to a maximal distance d (equivalent to skipping all those that are > d as you ask in your first question) It appears that Mathematica uses Dijkstra's algorithm for this (as a possible choice); there are variants for bounded arc weights (which is your problem), where the computational complexity is linearly proportional to the edge weight. (although I'm not sure if Mathematica implements these special cases) en.wikipedia.org/wiki/… $\endgroup$ – Joshua Schrier Nov 19 '19 at 18:23
  • 1
    $\begingroup$ How large a d are you interested in? $\endgroup$ – Carl Woll Nov 19 '19 at 19:01
  • $\begingroup$ @CarlWoll For example in what I am calculating now, about half the diameter, which would be $d\approx 30.$ $\endgroup$ – user52181 Nov 20 '19 at 10:30
  • $\begingroup$ @JoshuaSchrier Unfortunately, GraphDistanceMatrix[g,d] even with d=2, is slower than computing the whole matrix GraphDistanceMatrix[g]. $\endgroup$ – user52181 Nov 20 '19 at 13:12
1
$\begingroup$

You can use VertexComponent to find all vertices precisely at a certain distance from a given vertex.

For example, in your graph, these are the vertices at distance 4 from vertex 12:

VertexComponent[gr, 12, {4}]
(* {8, 2, 6} *)

I recommend using Mathematica 12.1 for this. VertexComponent is known to sometimes return incorrect result in M12.0 and earlier.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy