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

LANGREITER.COM plain, simple

START

Sonntag, 18. April 2004

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

slauti 7312 days AGO
wo hoitsdn jetzt Du von dem Foveon Chip?

chris 7311 days AGO
Ja prinzipiell & überhaupt faszinierend, die (Sigma-)Buidln in den diversen Galleries schaun grösstenteils gut bis super aus. Aber vom Digicam-Stand-der-Dinge abseits von Foveon hab' ich überhaupt keine Ahnung, vielleicht sind die CCDs traditioneller Bauart heutzutage eh schon auf ähnlichem Niveau ...

earl 7311 days AGO
not only does k rock, but you do, too!

slauti 7311 days AGO
was ich noch nicht ganz schnall, ist das Entwicklungspotential und auf das kommt es in the longer run bei den chips, glaub ich an. wieviel saft ist da noch drin. Carver Mead war ja mal so ein hero von mir, Auch ein Grund, dass ich es schon länger verfolge, aber diese HW-Fuzzis sind ja wohl eher geheimnisvoll ....
is a bissl wie mit Otto- und Wankelmotor: viel Optimierung in einem konventionellen Konzept ergibt auch performance, irgendwie.

Please log in (you may want to register first) to post comments!