Reading List for Graph Walk

Graph walks are the first topic we will dive into. Graphs are an abstract way to represent many data sources:

In the programming homework you are going to be working with a CAR-Hypertext graph like this:

Every CAR page is a node, and every paragraph represents an edge between all CAR pages it links to.

Graph walk algorithms are based on an thought experiment: Say a random surfer would pick a node at random, and would hop from node to node along edges for all eternity. Which node would it visit most often?

Graph walk algorithms can be used to rank nodes, by placing the node that is visited most often first, the second-most visited second, etc. This is the rough idea behind the PageRank algorithm, which made the Google search engine famous in the late 90’ies.

The purpose of this reading assignment is for you to become familiar with different graph walk algorithms and their variation, their underlying theory and applications.

Mandatory reading

(everyone has to read this)

Additional papers

(mandatory if you choose this as your expertise topic)

Introductory Reading

(if you are completely lost, start here!)

Further reading beyond this assignment

(if you want to know more, or read these if the other papers were to easy)