Re: Small World

David Sowder (Zothar) wrote:
> Is there more than one metric for which we are trying to achieve "small
> world"?  If so, could that be confusing things for others as well?

Yup, there are two ways to define a small world:

1) The average number of hops between any two nodes is low and the
probability that two neighbours of a given node are neighbours is high.

2) Every node has a location, and the probability that any two nodes are
neighbours is proportional to 1/(r^d), where r is the distance between
the nodes and d is the number of dimensions.

Graphs that fit the second definition generally fit the first
definition, but not necessarily vice versa. Freenet uses the second
definition, with d=1.

> Can a given node and a list of potential peers be used to create a small
> world model, at least from the perspective of the given node?

Yes, this is what swapping does: given an arbitrary graph, it changes
the locations of the nodes to fit the second definition above, without
making or breaking any connections.

> Could refbot.py potentially say, add 50 peers and then remove (in an
> orderly fashion) all but 15 based on a small world location/distance
> distribution to achieve a small world model if say, all/most nodes were
> using this same algorithm?

It's possible, but I'm not sure it's necessary - the locations are
arbitrary, so rather than adding and removing connections you could just
change the locations.

Cheers,
Michael