The diameter of a long range percolation graph

ABSTRACT

One can model a social network as a long-range percolation model on a graph {0, 1, …, N}². The edges (x, y) of this graph are selected with probability ≈ β/||x - y^s if ||x - y|| > 1, and with probability 1 if ||x - y|| = 1, for some parameters β, s > 0. That is, people are more likely to be acquainted with their neighbors than with people at large distance. This model was introduced by Benjamini and Berger [2] and it resembles a model considered by Kleinberg in [6], [7]. We are interested in how small (probabilistically) is the diameter of this graph as a function of β and s, thus relating to the famous Milgram's experiment which led to the "six degrees of separation" concept. Extending the work by Benjamini and Berger, we consider a d-dimensional version of this question on a node set {0, 1, …, N}^d and obtain upper and lower bounds on the expected diameter of this graph. Specifically, we show that the expected diameter experiences phase transitions at values s = d and s = 2d. We compare the algorithmic implication of our work to the ones of Kleinberg, [6].

REFERENCES

• 1: M. Aizenman and C. M. Newman. Discontinuity of the percolation density in one dimensional 1/|x - y|2 percolation models. Commun. Math. Phys., 107:611-647, 1986.
• 2: 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]
• 3: I. Benjamini, H. Kesten, Y. Peres, and O. Schramm. The geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12, …. In preparation, 2000.
• 4: D. Coppersmith, D. Gamarnik, and M. Sviridenko. The diameter of a long range percolation graph. Submitted, 2001.
• 5: 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]
• 6: Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, Cornell University, Ithaca, NY, 1999
• 7: J. Kleinberg. Navigation in a small world. Nature, 406, 2000.
• 8: S. Milgram. The small world problem. Psychology Today, 1(61), 1967.
• 9: C. M. Newman and L. S. Schulman. One dimensional 1/|j - i|s percolation models: the existence of a transition for s ≤ 2. Commun. Math. Phys., 180:483-504, 1986.
• 10: L. S. Schulman. Long-range percolation in one dimension. J.Phys. A, 16(17):L639-L641, 1983.
• 11: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393(440), 1998.