Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. This model aims at giving formal support to the "six degrees of separation" between individuals experienced by Milgram (1967),and verified recently by Dodds, Muhamad, and Watts (2003). In particular, Kleinberg shows that greedy routing performs in O(log²n) expected number of steps in d-dimensional augmented meshes, with O(log²n) bits of topological awareness per node, for any constant d ≥ 1. We show that giving O(log²n) bits of topological awareness per node decreases the expected number of steps of greedy routing to O(log^1+1/dn) in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, greedy routing performs in Ω(log^1+1/dn) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log²n) bits would drastically decrease the performances of greedy routing. Moreover, our model demonstrates that the efficiency of greedy routing is sensible to the "world's dimension", in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg's model. In addition to bringing new light to Milgram's experiment, our protocol presents several desirable properties. In particular, it is totally oblivious i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. Finally, our protocol can obviously be used for the design of DHTs, in the same spirit as Symphony (2003).

REFERENCES

• 1: L. Adamic and E. Adar. How To Search a Social Network. Tech. Report HP Labs, Palo Alto, 2003.
• 2: James Aspnes , Zoë Diamadi , Gauri Shah, Fault-tolerant routing in peer-to-peer systems, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571862]
• 3: Lali Barrière , Pierre Fraigniaud , Evangelos Kranakis , Danny Krizanc, Efficient Routing in Networks with Long Range Contacts, Proceedings of the 15th International Conference on Distributed Computing, p.270-284, October 03-05, 2001
• 4: Don Coppersmith , David Gamarnik , Maxim Sviridenko, The diameter of a long-range percolation graph, Random Structures & Algorithms, v.21 n.1, p.1-13, August 2002 [doi>10.1002/rsa.10042]
• 5: P. Dodds, R. Muhamad, and D. Watts. An Experimental Study of Search in Global Social Networks. Science 301:827--829, 2003.
• 6: P. Killworth and H. Bernard. Reverse Small-World Experiment. Social Networks 1(2):159--192, 1978.
• 7: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 8: J. Kleinberg. Navigation in a Small-World. Nature 406:845, 2000.
• 9: J. Kleinberg. Small-World Phenomena and the Dynamics of Information. In 15th Neural Information Processing Systems (NIPS), 2001.
• 10: E. Lebhar and N. Schabanel. Searching for Optimal paths in long-range contact networks. In 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.
• 11: G. Manku, M. Bawa, and P. Raghavan. Symphony: distributed hashing in a small world. In 4th USENIX Symp. on Internet Technologies and Systems, pages 127--140, 2003.
• 12: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 13: Chip Martel , Van Nguyen, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011794]
• 14: S. Milgram. The Small-World Problem. Psychology Today, 60--67, 1967.
• 15: J. Travers and S. Milgram. An Experimental Study of the Small World Problem. Sociometry 32:425, 1969.
• 16: D. Watts, P. Dodds, and M. Newman. Identity and Search in Social Networks. Science 296:1302--1305, 2002.
• 17: D. Watts and S. Strogatz. Collective Dynamics of Small-World Networks. Nature 393:440--442, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
distributed hash tables, routing, small world graphs