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.

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?

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

• 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 continues from the most recently found vertex.
• Closest-first: Visits vertices in order of their distance from a start vertex, nearest first.

All algorithms