File Exchange

image thumbnail

pagerankdemo

version 1.1 (6.13 KB) by

A graphical demo of a random web surfer (aka Google's PageRank)

1 Download

Updated

View License

Editor's Note: This was a File Exchange Pick of the Week

PAGERANKDEMO draws the 6-node "tiny web" in Section 2.11 of "Numerical Computing with MATLAB", by Cleve Moler, SIAM, 2004. It then simulates the computation of Google's PageRank algorithm, by randomly selecting links to traverse. If a link is traversed, the edge and the target node are displayed in red. If the "random surfer" jumps to an arbitrary page, the target node is displayed in blue. The number of hits at each node, and the page rank (in %) are displayed % on each node. Note that after a large number of steps, the PageRanks (in percentages) converge to the values given in Section 2.11 of Moler (alpha: .321, sigma: .2007, beta: .1705, delta: .1368, gamma: .1066, rho: .0643). See http://www.mathworks.com/moler for more details (the pagerank M-file, in particular).
See also David Gleich's pagerank in the File Exchange, file id 11613,
for computing pageranks of really large graphs.

Note that this method is NOT how the PageRank is actually computed. Instead the eigenvalue problem A*x=x is solved for x, where A is the Markov transition matrix, A = p*G*D + e*z', where G is the binary matrix used here. The method here is a simplistic random-hopping demonstration of the Markov process, to motivate the A*x=x formulation of the problem. In this example, A does control how the transitions are made, but the matrix A is not formed explicitly.

This demo only operates on a single graph. It is meant as a simple demo only, suitable for in-class use. To compute the PageRanks for an arbitrary graph, use pagerank.m from Moler's book, or the power method (repeat x=A*x, until convergence, where A is the Markov transition matrix of the web).

Comments and Ratings (1)

Charles

Updates

1.1

Updated comments.

Updated description; no change to code (long url caused problems when reading this page).

Updated description; no change to code.

Increased font size for better in-class use.

MATLAB Release
MATLAB 7.5 (R2007b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video