[Tech] PageRank for premix routing?

[Matthew Toseland]

Hmmm but does it work? Does it prevent Sybil?

On Wed, Feb 07, 2007 at 01:30:59PM +0000, Michael Rogers wrote:
> So I followed up a few of the refs from the Kleinberg paper...
> 
> Katz came up with the idea of propagating trust/status/etc across a 
> graph in 1953. In 1976, Pinski and Narin suggested normalising each 
> node's output by dividing the output on each outgoing edge by the node's 
> outdegree. Geller pointed out in 1978 that their model was equivalent to 
> a Markov chain: the scores assigned to the nodes followed the Markov 
> chain's stationary distribution. In other words, propagating 
> trust/status/etc with normalisation at each node is equivalent to taking 
> random walks from random starting points and counting how many times you 
> end up at each node. (So either my assertion that a random walk would be 
> likely to end at a Sybil node was wrong, or trust propagation isn't 
> Sybil-resistant.)
> 
> The only difference between Geller's model and PageRank is the damping 
> factor: in PageRank you continue your random walk with probability d or 
> jump to a random node with probability 1-d. (Incidentally, when the 
> algorithm's described this way rather than in terms of a transition 
> matrix, it's easy to see how you could implement it on a web spider.)
> 
> Conclusion: we should be safe from the PageRank patent as long as we 
> don't use a damping factor - the rest of the algorithm was published 
> (and applied to social networks) 20 years before the patent.
> 
> Cheers,
> Michael
> _______________________________________________
> Tech mailing list
> Tech at freenetproject.org
> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://emu.freenetproject.org/pipermail/tech/attachments/20070207/23700eb6/attachment.pgp