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

LANGREITER.COM plain, simple

START

INDEX

2004-04-18

CREATED BY chris • LAST EDITED BY chris 7305 days AGO

Steve Kirsch interviews his former employee Matt Wells, now of Gigablast: "I'm hoping to build Gigablast up to 5 billion pages this year. My income level should allow me to do that if I invest everything in hardware and bandwidth. It will still be a modest number of machines, too, not a whole lot more than the eight I have now."

"Hey, it was the thing to do at the time."

2004-04-18-kirschBlast

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

2004-04-18-deePR

Bill de hÓra: "The syntax has been around for over half a decade - it's not catching on and I remain convinced that nothing hurts RDF adoption more than RDF/XML." [ Ø ESA • ]

2004-04-18-rdfXml

Andy Makely: "[...] Foveon pixels are working harder for you." — Offensichtlich.

2004-04-18-foveon