c: the normalization factor to make ||R||L1 = 1 (||R||L1= |R1 + … + Rn|)

The Random Surfer Model

The Random Surfer Model

The simplified model: the standing probability distribution of a random walk on the graph of the web. simply keeps clicking successive links at random

The Modified Model

The modified model: the “random surfer” simply keeps clicking successive links at random, but periodically “gets bored” and jumps to a random page based on the distribution of E

Links that point to any page with no outgoing links

Links that point to any page with no outgoing links

Theory of random walk: a random walk on a graph is said to be rapidly-mixing if it quickly converges to a limiting distribution on the set of nodes in the graph. A random walk is rapidly-mixing on a graph if and only if the graph is an expander graph.

Expander graph: every subset of nodes S has a neighborhood (set of vertices accessible via outedges emanating from nodes in S) that is larger than some factor α times of |S|. A graph has a good expansion factor if and only if the largest eigenvalue is sufficiently larger than the second-largest eigenvalue.