ian at locut.us
Wed Mar 8 01:02:45 UTC 2006
I think Chapters 1 and 2 of Oskar Sandberg's recent thesis may be
It outlines an algorithm to choose which nodes in a network should
have edges between them such that "greedy" routing (routing to the
peer closest to what you are looking for) has small world O( log^2
(N) ) path lengths.
The algorithm is very simple, and pleasingly "natural". Basically
you use greedy routing to find a path to your intended destination
node, then you add a link from each node along this path to the
destination. The number of outbound edges from each node can't
obviously increase indefinitely, so they are deleted according to a
least recently used scheme to make room for new edges.
This is based on Freenet's approach to edge selection. The paper
describes both experimental results that confirm that this algorithm
does lead to a small world topology, and also delves into the
mathematics behind why this might be the case.
It is interesting not just because of the simplicity of the
algorithm, but because it is extremely amenable to the construction
and maintainence of decentralized P2P networks, and because it could
tell us something about why human relationships tend to form small
This algorithm is used by the Dijjer (http://dijjer.org/) P2P network.
On 7 Mar 2006, at 02:46, Jeff Rose wrote:
> Anyone out there doing work in clustering? I'd be interested in
> hearing what people are up to, or if you have pointers to good
> papers that would be great too. At this point I'm interested in
> any angle, geographic distance based, semantic distance based,
> hierarchical, non-hierarchical etc... My goal is to work towards a
> very amorphous clustering scheme that allows any kind of object to
> be located close to relatives in the network as long as they share
> a common distance function.
More information about the P2p-hackers