next up previous contents
Next: Stating the problem Up: Theoretical considerations Previous: Conclusion   Contents


Small world phenomenon estimated with a fractal argument

Limewire, a popular Gnutella client, estimates the network size each day with a Gnutella Crawler[23]. In the early days of Gnutella, there were 500000 nodes. Now, Gnutella feels competition of other popular file sharing networks like eMule and Kazaa; network size dropped down to about 100000 (March 2004).

An interesting problem arises: how many users are reachable by one user in the Gnutella network? How should one set the count-down timer in each packet to reach all nodes? The problem is equivalent to the following one: how many people are between any two people or between you and the President of the United Nations, as an example? This is sometimes referred as the small world problem, a common experience of many of us: we meet a new friend and we discover he/she knows someone we know as well. Milgram's experiment showed empirically that any two people in the United States are distant six edges from each other.

To solve the problem, we attempt a volumetric argument. Some fractal arguments are given in [26], although they go by far more in depth. However, we start our argument with an analogic machine to compute the solution. Results are consistent with Mandelbrot's fractal theory [24,25].



Subsections
next up previous contents
Next: Stating the problem Up: Theoretical considerations Previous: Conclusion   Contents
Tiziano Mengotti 2004-03-27