[freenet-dev] Wierd clustering behaviour again

[Michael Rogers]

Matthew Toseland wrote:
> Anyone feel like running some
> simulations to confirm the theory and the fix?

OK, but we need to come up with a precise model of what's happening 
before we can simulate it. There seem to be two possible causes: 
non-uniform clustering and non-uniform lifetime (maybe both).

Lifetime is relatively easy: assign each new node a lifetime drawn from 
some distribution (fixed, exponential, power law seem like plausible 
candidates).

Clustering is harder: here's an initial suggestion adapted from [1]. 
Each new node connects to m neighbours. The first neighbour is chosen at 
random. Then for each of the m-1 remaining neighbours, with probability 
p you choose a random neighbour of your existing neighbours (this 
creates clustering); with probability 1-p you choose a random node.

The value of p can be different for each node, so we can test what 
happens when clustering is correlated with lifetime (ie long-lived nodes 
form clusters and short-lived nodes are peripheral).

Cheers,
Michael

[1] http://nlsc.ustc.edu.cn/BJKim/PAPER/PRE_CLUS.PDF (the paper uses 
preferential attachment and therefore creates scale-free networks, but 
my suggestion above doesn't use preferential attachment)