Re: Small World

On Tue, Mar 06, 2007 at 01:01:59PM +0000, Michael Rogers wrote:
> 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.

2a) Any network with no inherent locations for nodes which can be
transformed into a type 2 network by assigning locations.

*This* is what we require. It's not too far away from type 1. The
algorithm we use will break if it isn't possible to transform the
network to a type 2 - i.e. if it is not a type 2a.
> 
> 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.

No. Small-world is a property of the graph. It exists without location
information.
> 
> > 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.

Many networks are not sufficiently close to small-world to be compatible
with our swapping algorithm. In particular, most things created by
refbots are very unlikely to be small-world. Swapping cannot create the
small-world property out of nothing; it must already be small world,
swapping makes it navigable.
> 
> Cheers,
> Michael

_______________________________________________
Tech mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/tech

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFF7ZxCA9rUluQ9pFARAp0zAJ4k3krxRmHIXit6YyxKjf7eRnfWWQCfZxAX
8RA+TEEMRzs0VUq6I2A+H50=
=WcE+
-----END PGP SIGNATURE-----