1
$\begingroup$

Given a distance-1 neighborhood matrix representing an undirected graph, I'm trying to calculate the distances between two nodes so I can work out the distance-2 matrix, then the distance-3 matrix, and so on...

How to find this distance?

Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "distance-k matrix"? $\endgroup$ – xskxzr May 6 '18 at 14:21
1
$\begingroup$

I assume that by distance-$2$ matrix you mean the matrix $A$ such that $A_{ij}=1$ if there is a path of length exactly $2$ between node $i$ and node $j$.

Let us call $B$ the distance-$1$ matrix, then remember that $B^2$ is such that $(B^2)_{ij}$ is the number of paths of legth $2$ between $i$ and $j$. So all you have to do is to check whether an entry of $B^2$ is $0$ or not.

$\endgroup$
  • $\begingroup$ Thanks, but given an adjacency matrix, how could I work out distance-3, distance-4, distance-5, etc? $\endgroup$ – Steve C. May 6 '18 at 11:44
  • $\begingroup$ What I wrote works for arbitrary $n$s: if you consider $B^n$, $(B^n)_{ij}$ is the number of paths of length $n$ between $i$ and $j$. $\endgroup$ – Leo163 May 6 '18 at 11:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.