# Sampling pairs of nodes with given distance between them

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"]


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.

• Perhaps you can map AdjacencyList[] all over your graph's vertices, and then delete dupes. Commented Nov 19, 2019 at 16:22
• 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/… Commented Nov 19, 2019 at 18:23
• How large a d are you interested in? Commented Nov 19, 2019 at 19:01
• @CarlWoll For example in what I am calculating now, about half the diameter, which would be $d\approx 30.$
– user52181
Commented Nov 20, 2019 at 10:30
• @JoshuaSchrier Unfortunately, GraphDistanceMatrix[g,d] even with d=2, is slower than computing the whole matrix GraphDistanceMatrix[g].
– user52181
Commented Nov 20, 2019 at 13:12

You can use VertexComponent to find all vertices precisely at a certain distance from a given vertex.
VertexComponent[gr, 12, {4}]

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