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.

Web crawl

A hundred pages on ten sites that a crawler reached by following links, P1 to P100, where P stands for page. Pages are numbered site by site: an encyclopedia (P1 to P16), news (P17 to P30), a city (P31 to P37), a university (P38 to P46), a link directory (P47 to P52), docs (P53 to P62), a forum (P63 to P74), videos (P75 to P82), a blog (P83 to P90) and a shop (P91 to P100). Each edge counts the links from one page to another. The docs, shop and city sites never link back, and no page links to the directory.

A directed, weighted graph with 100 vertices and 274 edges.

A crawler starts at P47 in the link directory and follows one link at random from each page, more often the links a page repeats. Which pages and sites does it reach in 60 page visits, counting P47?

On this run, the walk from P47 went through 60 vertices, 11 of them different: P47, P50, P47, P50, P47, P51, P24, P32, P36, P31, and so on to P32.

Step by step

  1. Start at P47. The walk stops after 60 vertices, or sooner at a vertex with no outgoing edges.
  2. P47 has 5 out-neighbors, all with edge weight 1, so each has a 1 in 5 chance.
  3. The walk picks P50, which had a 20% chance.
  4. P50 has 2 out-neighbors, both with edge weight 1, so each has a 1 in 2 chance.
  5. The walk picks P47, which had a 50% chance.
  6. P47 has 5 out-neighbors, all with edge weight 1, so each has a 1 in 5 chance.

113 more steps lead to the last one:

  1. Done. The walk reached its limit with 60 vertices, 11 of them different.

Use it in Go

it, err := traverse.NewRandomWalkIterator(g, "P47", 60)
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