Lesson 2

To better understand the behavior of a random web surfer, we start by considering random walks on graphs.

Problem. For the toy graph shown below, consider the following random walk. Start by selecting (uniformly) a random node \(s\). Then, select (uniformly) a random edge going out of \(s\) and follow it. Find the probability that one ends up in the node \(3\).

The code below computes an approximation of the corresponding probability by modeling the experiment many times.

from networkx import DiGraph
from random import choice

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])

histogram = [0] * graph.number_of_nodes()
for _ in range(10 ** 5):
    s = choice(list(graph.nodes()))
    v = choice(list(graph[s]))
    histogram[v] += 1

print(histogram[3] / sum(histogram))

0.31826