2
$\begingroup$

In a non weighted graph, the adjacency matrix ($A$) raised to the power $k$ will return the number of k-step paths between nodes $i$ and $j$ at the entry $a_{ij}$. Is there an equivalent for weighted graphs? I.e. to obtain the sum of the cumulative weights of all paths between node pairs?

Applying the same approach as above, but to a weighted adjacency matrix, i.e. raising to the power $k$, returns the sum of the product of the weights along each $k$ step path between node pairs. This is useful when edge weight represents some probability (e.g. Markov models), however not when edge weight represents a length (e.g. geospatial network).

Note I want to avoid path search algorithms (e.g. Dijkstra's or Yen's) if possible, as this will be applied to very large networks so efficiency is important.

Example: Given a 4-node digraph (image linked below), with the weighted adjacency matrix (infinity represents no connection between nodes):

Digraph described in the example

$$A = \begin{matrix} \infty & 2 & 3 & \infty \\ 2 & \infty & 5 & 1 \\ \infty & \infty & \infty & 7 \\ \infty & 1 & \infty & \infty \\ \end{matrix} $$

where e.g. the connection between nodes B & C is of length 5. I want to find the n-step length matrix, which for the 2 step case would be:

$$A_2 = \begin{matrix} 4 &\infty & 7 & 13 \\ \infty & 6 & 5 & 12 \\ \infty & 8 & \infty & \infty \\ 3 & \infty & 6 & 2 \\ \end{matrix} $$

Thanks in advance for any help.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $A^k_{i,j} = (n^k_{i,j}, s^k_{i,j})$ where $n^k_{i,j}$ is the number of paths of length $k$ between $i$ and $j$, and $s^k_{i,j}$ is the sum of the lengths between these paths.
$A^1_{i,j} = (1, w_{i,j})$ if $ij$ is an edge, else $A^1_{i,j}=(0,0)$
The idea of the recurrence is that a $(k+k')$-step path from $i$ to $j$ is composed of a $k$-step path from $i$ to an intermediate vertex $c$ followed by a $k'$-step path from $c$ to $j$.
Let fix $c$. Let $n_1$ (resp $n_2$) be the number of $k$-step paths from $i$ to $c$ (resp. $k'$-step paths from $c$ to $j$) and $s_1$ (resp. $s_2$) the sum of weigths on these paths. We can easily see that the number of $(k+k')$-step paths from $i$ to $j$ passing through $c$ at step $k$ is $n_1n_2$. The sum of weights is $s_1n_2 + s_2n_1$ because each path from $i$ to $c$ will appear in exactly $n_2$ paths, and conversely. To get the total number of $(k+k')$-step paths from $i$ to $j$, we just need to sum over the $c$. So the recurrence is given by :
$$A^{k+k'}_{i,j} = (n^{k+k'}_{i,j}, s^{k+k'}_{i,j}) = \sum_{c\in V}(n^k_{i,c}n^{k'}_{c,j}, n^k_{i,c}s^{k'}_{c,j}+s^k_{i,c}n^{k'}_{c,j})$$

We can adapt the definition of the matrix multiplication by replacing the multiplication by : $(n_1,s_1)\otimes(n_2,s_2) = (n_1n_2, n_1s_2 + n_2s_1)$
and addition by :
$(n_1,s_1)\oplus(n_2,s_2) = (n_1+n_2, s_1+s_2)$
With it, we have :
$$A^{k+k'}_{i,j} = \bigoplus_{c\in V} A^{k}_{i,c}\otimes A^{k'}_{c,j}$$ and so $A^kA^{k'} = A^{k+k'}$

The new matrix multiplication is associative, so matrix exponentiation by squaring still work.


This kind of redefinition of the matrix multiplication is common when dealing with shortest paths, see the min-plus matrix multiplication

$\endgroup$
12
  • $\begingroup$ But how does this answer the question? $\endgroup$
    – Alex M.
    Sep 23, 2021 at 9:39
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Sep 23, 2021 at 9:40
  • $\begingroup$ You just need to compute $A^k_{i,j}$, using exponentiation by squaring for efficiency. $\endgroup$
    – caduk
    Sep 23, 2021 at 9:49
  • 1
    $\begingroup$ Note that this requires non-edges to be represented by $(0, 0)$ instead of $(0, \infty)$. $\endgroup$ Sep 23, 2021 at 10:07
  • $\begingroup$ Yes, this is important to note, I edited. $\endgroup$
    – caduk
    Sep 23, 2021 at 11:13

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.