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.
Microservice calls
Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.
A directed graph with 9 vertices and 15 edges.
A request enters at the gateway, and each service passes it on to one of the services it calls, picked at random. Which services does it pass through in 12 stops, counting the gateway?
On this run, the walk from Gateway went through 12 vertices, 3 of them different: Gateway, Search, Inventory, Search, Inventory, Search, Inventory, Search, Inventory, Search, and so on to Search.
Step by step
- Start at Gateway. The walk stops after 12 vertices, or sooner at a vertex with no outgoing edges.
- Gateway has 3 out-neighbors, so each has a 1 in 3 chance.
- The walk picks Search, which had a 33.3% chance.
- Search has one out-neighbor, Inventory, so the walk must go there.
- The walk moves to Inventory.
- Inventory has one out-neighbor, Search, so the walk must go there.
17 more steps lead to the last one:
- Done. The walk reached its limit with 12 vertices, 3 of them different.
Use it in Go
it, err := traverse.NewRandomWalkIterator(g, "Gateway", 12)
if err != nil {
return err
}
for it.HasNext() {
fmt.Println(it.Next().Label())
}
Example graphs
- Microservice calls, 9 vertices and 15 edges
- Import cycles, 18 vertices and 30 edges
- Linked web pages, 40 vertices and 114 edges
- Web crawl, 100 vertices and 274 edges
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.