[p2p-hackers] clustering

[Ian Clarke]

I think Chapters 1 and 2 of Oskar Sandberg's recent thesis may be  
extremely relevant:

   http://www.math.chalmers.se/~ossa/lic.pdf

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  
world networks.

This algorithm is used by the Dijjer (http://dijjer.org/) P2P network.

Ian.

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.