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.