Lesson 5

A natural way of computing the resulting distribution is to multiply the so-called transition matrix by the original distribution vector. We introduce the transition matrix using our working toy graph.

Consider the adjacency matrix of the graph:

Now, let us divide each entry \(\mathbf{A}[i,j]\) by the outdegree of \(i\) and transpose the resulting matrix. \[\mathbf{T}= \begin{bmatrix}0 & 1/4 & 1/3 & 0 & 0\\ 1/3 & 0 & 0 & 1/2 & 0\\ 1/3 & 1/4 & 0 & 0 & 0\\ 0 & 1/4 & 1/3 & 0 & 1\\ 1/3 & 1/4 & 1/3 & 1/2 & 0\\\end{bmatrix}\] It is not difficult to see that \(\mathbf{T}[i,j]\) is the probability of going to \(i\) from \(j\).

The matrix \(\mathbf{T}\) is known as the stochastic matrix of the corresponding Markov chain (we will soon introduce them formally). In particular, it is column-normalized: the sum of each column is equal to \(1\). It is not difficult to see that this property can be used to show that if \(\mathbf{r}\) is the original distribution vector, then \(\mathbf{T}\mathbf{r}\) is the resulting distribution vector.

In Python, it is easy to produce the transition matrix and to multiply it by the distribution vector.

import numpy as np
import networkx as nx

edges = ['01', '02', '04', '10', '12', '13', '14', '20', '23', '24', '31', '34', '43']
graph = DiGraph([(int(e[0]), int(e[1])) for e in edges])

A = nx.stochastic_graph(graph)
T = nx.to_numpy_array(A, nodelist=sorted(graph.nodes())).T
r = [0.2, 0.1, 0.3, 0.1, 0.3]

print(*np.round(T @ r, 3))

0.125 0.117 0.092 0.425 0.242

This way of recomputing the probabilities by multiplying the transition matrix \(\mathbf{T}\) by the current probability distribution vector makes it easy to generalize our approach to the case when a random graph surfer makes \(k\) steps (rather than a single step): simply multiply the current distribution vector by the transition matrix \(k\) times!