Following Probability Through a Network

Imagine Botie inspecting a network by choosing an outgoing connection at each step. A junction with several links gives several possible next positions.

Rather than following only one sampled route, we can keep a probability for each node. The transition matrix describes the next move from every current node. Combining the two gives us the distribution of possible locations after one step, so we can follow how probability moves through the network.

Start with probability concentrated at one node. Follow that node's outgoing row, then try a mixture of starting nodes and see their contributions combine at each destination.

For non-negative adjacency weights, divide each row by its outgoing total to form transition probabilities. A positive weight is a relative choice weight, not a probability until normalised.

A node with no outgoing edges has a zero row. Choose a dangling-node policy explicitly. Our exercises make such a node stay at itself; PageRank often redistributes that probability instead.

Every resulting transition row must sum to one.

When rows are current nodes and columns next nodes, multiply a row probability vector by the transition matrix. Each destination collects contributions from all sources.

Initial p = [1,0,0]
P = [[0,1,0], [0.5,0,0.5], [0,1,0]]
p after one step = [0,1,0]
p after two steps = [0.5,0,0.5]

Total probability remains one when the transition matrix is valid.

An undirected two-node walk alternates forever rather than settling from every starting point. A disconnected component cannot reach another without an added transition. These are properties of the graph and process.

Teleportation mixes a link-following transition with a chosen restart distribution. It changes the process deliberately rather than fixing an arithmetic error.

Do not assume every repeated matrix multiplication converges to one unique result.

import numpy as np
probability = np.array([0.5, 0.5])
transition = np.array([[1., 0.], [0.5, 0.5]])
contributions = probability[:, None] * transition
print(contributions.tolist())
print(contributions.sum(axis=0).tolist())

[[0.5, 0.0], [0.25, 0.25]]
[0.75, 0.25]

Random walks can describe reachability patterns, ranking, or sampling of graph neighbourhoods. They do not automatically describe the actual movement of water, disease, or information.

Compare walk results under different edge definitions, and document the dangling-node and restart rules. Otherwise two implementations can disagree while each follows its own valid process.

The workshop takes an already valid transition matrix so the movement of probability is visible.

Dividing outgoing edge weights by their row sum fails when that sum is zero. The walker could remain at the node, restart according to a chosen distribution or terminate. These are different processes.

Specify the policy before normalisation. A transition matrix for a continuing walk needs every row to sum to one. Quietly leaving a zero row makes probability mass disappear when the walk reaches that node.

A two-node walk that always switches nodes alternates forever from a concentrated start. Mixing each step with a restart distribution interrupts that strict cycle. It also changes what long-run visit frequency means.

The restart distribution can be uniform or personalised. Its choice is a modelling decision, not merely a numerical fix.

import numpy as np
P = np.array([[0.,1.],[1.,0.]])
state = np.array([1.,0.])
restart = np.array([.5,.5])
for _ in range(3):
    state = .5*(state@P) + .5*restart
    print(state.tolist())

[0.25, 0.75]
[0.625, 0.375]
[0.4375, 0.5625]

A node can receive high mass because many paths lead to it, because a small region traps the walker or because the restart favours it. Relate the score to the inspection or retrieval task before naming it importance.

Check disconnected regions, dangling nodes and sensitivity to restart. A random walk uses connectivity; it does not automatically include node features, physical flow conservation or causal influence.