Random walk

Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.

Time complexity O(steps × degree), gograph function traverse.NewRandomWalkIterator.

How it works

A random walk starts at a vertex and moves to one of its out-neighbors at random, again and again. In an unweighted graph every neighbor has the same chance. In a weighted graph the chance follows the edge's weight, so heavier edges are taken more often. An edge with a weight of zero or less is never taken, unless none of the vertex's edges has a positive weight.

The walk returns the start first and stops after the number of vertices you ask for, or earlier at a vertex with no outgoing edges. Vertices can come up more than once. Each move costs time in proportion to the degree of the current vertex. gograph draws from crypto/rand, so a walk can't be replayed from a seed.

Use it to sample a graph too large to search, to simulate someone clicking from page to page, or to estimate how often a walk passes each vertex, which ranking methods build on.

Linked web pages

Forty pages of a product website, P1 to P40, where P stands for page: the main site (P1 to P13), the blog (P14 to P19), landing pages (P20 to P24), the help center (P25 to P28), the docs (P29 to P38) and the status pages (P39 and P40). Each edge counts the links from one page to another. Only ads and emails lead to the landing pages, and the help center, docs and status pages never link back to the main site.

A directed, weighted graph with 40 vertices and 114 edges.

A visitor starts on P1 of the main site and keeps clicking a link at random, so the pages the current page links to most are the likeliest next. Which pages do they see in 40 page views, counting P1?

On this run, the walk from P1 went through 40 vertices, 13 of them different: P1, P10, P28, P25, P37, P29, P37, P29, P31, P32, and so on to P33.

Step by step

  1. Start at P1. The walk stops after 40 vertices, or sooner at a vertex with no outgoing edges.
  2. P1 has 10 out-neighbors. Each one's chance is the weight of its edge divided by 14, the total weight.
  3. The walk picks P10, which had a 7.1% chance.
  4. P10 has 2 out-neighbors, both with edge weight 1, so each has a 1 in 2 chance.
  5. The walk picks P28, which had a 50% chance.
  6. P28 has 2 out-neighbors, both with edge weight 1, so each has a 1 in 2 chance.

73 more steps lead to the last one:

  1. Done. The walk reached its limit with 40 vertices, 13 of them different.

Use it in Go

it, err := traverse.NewRandomWalkIterator(g, "P1", 40)
if err != nil {
	return err
}
for it.HasNext() {
	fmt.Println(it.Next().Label())
}

Example graphs

More in Traversal

  • Breadth-first: Visits vertices level by level from a start vertex.
  • Depth-first: Follows one path as deep as it can, then backs up to the last vertex with a neighbor left to try, and sorts every edge it meets into four kinds.
  • Closest-first: Visits vertices in order of their distance from a start vertex, nearest first.

All algorithms