LANGREITER.COM plain, simple

 2004-04-18-deePR
CREATED BY chris • LAST EDITED BY chris 7395 days AGO
Amy N. Langville and Carl D. Meyer: Deeper Inside PageRank

I played a bit with PageRank at the beginning of last week, triggered by Peter Bengtsson's Python implementation. In its pure form, the algorithm is amazingly simple (compacted from Peter's version):

`def pageRank( web, p = 0.85, i = 100 ):    n = len( web )    W = array( web, Float )    V = sum( transpose( W ) ) 			    D = (1-p)/n + p * W / V[:,NewAxis]     S = ones( ( 1, n ), Float )	       	    for i in range( i ):        S = dot( S, D )    return S[0] / sum( S[0] )`
The K version is even simpler and should scale much better (as the link structure isn't represented as n-by-n matrix but as a nested list of outlinks). Testing it with graphs of interesting dimensions is left as an exercise for the reader (or next weekend), though:

`O:(,1;,2;,1;,1;1 3)p:0.85; q:1-p; i:100; n:#O V:p*1%#:'O; I:.[n#,!0;,O;,;!n]S:i{q+/'x[I]*V[I]}/n#1; S%+/S`
V is the inverse count of outlinks per node multiplied with the damping factor p (i.e. the "link value"), I:.[n#,!0;,O;,;!n] transforms outlinks to inlinks, S:i{q+/'x[I]*V[I]}/n#1 does all the work, the rest is set-up. In case you haven't noticed, K rocks (and Python with numarray and matplotlib is fairly nice too).

www.langreiter.com/py/pagerank-2c.py
www.langreiter.com/k/pagerank.k

SEARCH

Nearby in the temporal dimension:
Nobody.
... and 37 of the anonymous kind.
Click on for a moderate dose of lcom-talk. This will probably not work in Lynx and other browser exotica.

RECENT EDITS (MORE)

&c.