Big hype on small worlds. (wasRe: Dijjerand Freenet(RE: [p2p-hackers] clustering))

[Ian Clarke]

On 21 Mar 2006, at 14:15, Serguei Osokine wrote:
>  Intuitively
> I have this feeling that the graph with this constant outdegree should
> not disintegrate into unconnected pieces no matter what's its size,
> and that phase transition should happen only if the links are truly
> random and the outdegree of some nodes can be zero (or close to it)
> as a result.

Oskar has already said this, but I will say it again just for emphasis.

The phase transition does not occur because the network has become  
disconnected, the network may well be fully connected (indeed, as you  
say, it would be very unlikely for it not to be fully connected), but  
greedy routing may not be able to find short routes between nodes.

It would certainly be useful to come up with a way to predict when  
the phase transition occurs so that one can say with certainty that  
it won't happen, but I suspect one will find (and simulations  
suggest) that if the degree is scaled with the log of the network  
size, then the network will never get anywhere close to this phase  
transition.

Ian.