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

ABSTRACT

We study variants of Kleinberg's small-world model where we start with a k-dimensional grid and add a random directed edge from each node. The probability u's random edge is to v is proportional to d(u,v)^-r where d(u,v) is the lattice distance and r is a parameter of the model.For a k-dimensional grid, we show that these graphs have poly-log expected diameter when k < r < 2k, but have polynomial expected diameter when r > 2k. This shows an interesting phase-transition between small-world and "large-world" graphs.We also present a general framework to construct classes of small-world graphs with Θ(log n) expected diameter, which includes several existing settings such as Kleinberg's grid-based and tree-based settings [15].We also generalize the idea of 'adding links with probability α the inverse distance' to design small-world graphs. We use semi-metric and metric functions to abstract distance to create a class of random graphs where almost all pairs of nodes are connected by a path of length O (log n), and using only local information we can find paths of poly-log length.

REFERENCES

• 1: 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]
• 2: 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
• 3: Itai Benjamini , Noam Berger, The diameter of long-range percolation clusters on finite cycles, Random Structures & Algorithms, v.19 n.2, p.102-111, September 2001 [doi>10.1002/rsa.1022]
• 4: M. Biskup, "Graph Diameter in Long-range percolation", submitted to Electron. Comm. Probab.
• 5: B. Bollobas, "The Diameter of Random Graphs", IEEE Trans. Inform. Theory 36 (1990), no. 2, 285--8.
• 6: B. Bollobás , F. R. K. Chung, The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, v.1 n.3, p.328-333, Aug. 1988 [doi>10.1137/0401033]
• 7: Fan Chung , Linyuan Lu, The diameter of sparse random graphs, Advances in Applied Mathematics, v.26 n.4, p.257-279, May 2001 [doi>10.1006/aama.2001.0720]
• 8: 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]
• 9: P. Dodds, R. Muhamad, and D. Watts, "An experimental study of search in global social networks", Science, 301:827--9, 2003.
• 10: P. Erdos and A. Renyi, "On random graphs", Publicationes Mathematicas 6, 290--7 (1959).
• 11: Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, 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.1011793]
• 12: Jie Gao , Li Zhang, Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs, 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.1011795]
• 13: Richard M. Karp, Probabilistic recurrence relations, Journal of the ACM (JACM), v.41 n.6, p.1136-1150, Nov. 1994 [doi>10.1145/195613.195632]
• 14: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 15: J. Kleinberg, "Small-World Phenomena and the Dynamics of Information", in Advances in Neural Information Processing Systems (NIPS) 14, 2001.
• 16: 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]
• 17: M. Kochen, Ed., The Small-World (Ablex, Norwood, 1989)
• 18: 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]
• 19: C. Martel and V. Nguyen, "The complexity of message delivery in Kleinberg's Small-world Model", Tech-Report CSE-2003--23, CS-UCDavis, 2003.
• 20: 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]
• 21: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 22: S. Milgram, "The small world problem" Psychology Today 1,61 (1967).
• 23: V. Nguyen and C. Martel, "Analysis and Models for Small-World Graphs", Tech-Report CS-UCDavis, 2004. www.cs.ucdavis.edu/~martel/main/smallworld.tech.pdf
• 24: D. Watts and S. Strogatz, "Collective Dynamics of small-world networks" Nature 393,p. 440--2 (1998).
• 25: H. Zhang, A. Goel and R. Gividan, "Using the Small-World Model to Improve Freenet Performance", IEEE INFOCOM'02, vol. 21(1), pp. 1228--37.