Matrices for graph traversal

import numpy as np

n = 5

# Make a sparsely populated random matrix
A = np.zeros((n, n))

from random import randrange, uniform
for i in range(n*n//2):
    i, j = randrange(n), randrange(n)
    w = round(uniform(0, 1), 1)
    A[i, j] = w
    
A

array([[ 0. ,  0. ,  0. ,  0.5,  0.9],
       [ 0. ,  0. ,  0.8,  0. ,  0.2],
       [ 0.3,  0. ,  0.3,  0. ,  0.4],
       [ 0. ,  0. ,  0.3,  0. ,  0. ],
       [ 0. ,  0. ,  0. ,  0. ,  0. ]])

For a reason that will become clear in a minute, we need the columns of \(A\) to be normalized to sum to 1:

A_cols = np.sum(A, axis=0)
A_cols[A_cols == 0] = 1
A = A/A_cols

print(A)
print(np.sum(A, axis=0))

[[ 0.          0.          0.          1.          0.6       ]
 [ 0.          0.          0.57142857  0.          0.13333333]
 [ 1.          0.          0.21428571  0.          0.26666667]
 [ 0.          0.          0.21428571  0.          0.        ]
 [ 0.          0.          0.          0.          0.        ]]
[ 1.  0.  1.  1.  1.]

This short piece of code exports the matrix in a format that's readable to the dot graph drawing tool.

def to_dot(A, vec=None):
    lines = ['digraph mygraph { size="2,2";']
    for i in range(n):
        for j in range(n):
            if A[i, j]:
                lines.append("%d -> %d [label=\"%0.1f\"];" % (j, i, A[i, j]))
    if vec is not None:
        for i, vec_i in enumerate(vec):
            assert 0<=vec_i<=1
            lines.append(
                '%d [style="filled", fillcolor="#ff%02xff"];'
                % (i, int(255*(1-vec_i))))
    lines.append("}")
    return "\n".join(lines)

See?

print(to_dot(A))

digraph mygraph { size="2,2";
3 -> 0 [label="1.0"];
4 -> 0 [label="0.6"];
2 -> 1 [label="0.6"];
4 -> 1 [label="0.1"];
0 -> 2 [label="1.0"];
2 -> 2 [label="0.2"];
4 -> 2 [label="0.3"];
2 -> 3 [label="0.2"];
}

%load_ext gvmagic

The gvmagic extension is already loaded. To reload it, use:
  %reload_ext gvmagic

%dotstr to_dot(A)

Another thing we can do is plot distributions on the graph:

d = np.zeros((n,))
d[4] = 1
%dotstr to_dot(A, d)

Now, how would we model the spread of this distribution across the graph?

d = np.dot(A, d)
print(np.sum(d))
%dotstr to_dot(A, d)

1.0