langreiter.com plain, simple: 2004-04-18-deePR

LANGREITER.COM plain, simple

START

INDEX

2004-04-18-deePR

CREATED BY chris • LAST EDITED BY chris 7521 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).