The diameter of a long-range percolation graph
作者： Don Coppersmith , David Gamarnik , Maxim Sviridenko
DOI: 10.1002/RSA.10042
关键词:
摘要: We consider the following long-range percolation model: an undirected graph with node set {0, 1, ..., N}d, has edges (x, y) selected probability ≈ β/||x -y||s if ||x - y|| ' η1 > η2 it is at most Nη2 when s = 2d, and least Nη1 d 2, β 1 or 2d. also provide a simple proof that diameter log O(1) N high probability, established previously in [2].
acm.org
sci-hub.se 参考文章(10)
S. Milgram, The Small World Problem Psychology today. ,vol. 1, pp. 60- 67 ,(1967)
M. Aizenman, C. M. Newman, Discontinuity of the percolation density in one dimensional 1/| x − y | 2 percolation models Communications in Mathematical Physics. ,vol. 107, pp. 611- 647 ,(1986) , 10.1007/BF01205489
Itai Benjamini, Noam Berger, The diameter of long-range percolation clusters on finite cycles Random Structures and Algorithms. ,vol. 19, pp. 102- 111 ,(2001) , 10.1002/RSA.1022
Ronald Meester, Jeffrey E. Steif, On the continuity of the critical value for long range percolation in the exponential case Communications in Mathematical Physics. ,vol. 180, pp. 483- 504 ,(1996) , 10.1007/BF02099722
Z Q Zhang, F C Pu, B Z Li, Long-range percolation in one dimension Journal of Physics A. ,vol. 16, ,(1983) , 10.1088/0305-4470/16/3/002
Duncan J. Watts, Steven H. Strogatz, Collective dynamics of small-world networks Nature. ,vol. 393, pp. 440- 442 ,(1998) , 10.1038/30918
Jon Kleinberg, The small-world phenomenon: an algorithmic perspective symposium on the theory of computing. pp. 163- 170 ,(2000) , 10.1145/335305.335325
Itai Benjamini, Harry Kesten, Yuval Peres, Oded Schramm, Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12 ,... Annals of Mathematics. ,vol. 160, pp. 465- 491 ,(2004) , 10.1007/978-1-4419-9675-6_25
C. M. Newman, L. S. Schulman, One dimensional 1/|j - i|S percolation models: The existence of a transition for S≦2 Communications in Mathematical Physics. ,vol. 104, pp. 547- 571 ,(1986) , 10.1007/BF01211064
L S Schulman, Long range percolation in one dimension Journal of Physics A. ,vol. 16, ,(1983) , 10.1088/0305-4470/16/17/001