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 -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070306/2bc22822/attachment.pgp>
