We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in article amsmath,amsfonts empty . We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x − y|−s+o(1) when |x − y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)Δ+o(1) where Δ−1 := log2(2d s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp r1 Δ+o(1) in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210-227, 2011 (Reproduction, by any means, of the entire article for non-commercial purposes is permitted without charge.)
Recently, long-range percolation has been invoked as a fruitful source of graphs with non-trivial growth properties. Our interest was stirred by the work of Benjamini and Berger @cite_13 who proposed (and studied) long-range percolation as a model of social networks. It is this context where the graph distance scaling, and volume growth, are particularly of much interest. Thanks to numerous contributions that followed @cite_13 , this scaling is now known for most values of @math and @math . Explicitly, for @math , a corollary to the main result of Benjamini, Kesten, Peres and Schramm @cite_0 asserts that almost surely. As @math , the right-hand side tends to infinity and so, at @math , we expect @math . And, indeed, the precise growth rate in this case has been established by Coppersmith, Gamarnik and Sviridenko @cite_12 , where @math '' means that the ratio of left and right-hand side is a random variable that is bounded away from zero and infinity with probability tending to one.
@cite_0 @cite_13 @cite_12
1580648572 2032332507 1968939650 2088668624
We consider long-range percolation in dimension @math , where distinct sites @math and @math are connected with probability @math . Assuming that @math is translation invariant and that @math with @math , we show that the graph distance is at least linear with the Euclidean distance. In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model. Appears in Phys. Rev. E 60, 7332-7342 (1999). Bounds for the diameter and expansion of the graphs created by long-range percolation on the cycle ℤ Nℤ are given. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 102–111, 2001 We consider the following long-range percolation model: an undirected graph with the node set 0, 1, ..., N d, has edges (x, y) selected with probability ≈ β ||x -y||s if ||x - y|| ' η1 > η2 > 1, it is at most Nη2 when s = 2d, and is at least Nη1 when d = 1, s = 2, β > 1 or when s > 2d. We also provide a simple proof that the diameter is at most log O(1) N with high probability, when d > s > 2d, established previously in [2].