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.

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?

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

• 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