TOPICS
Search

Random-Connection Model


A random-connection model (RCM) is a graph-theoretic model of continuum percolation theory characterized by the existence of a stationary point process X and a non-increasing function g:R^+->[0,1] which together determine a methodology for drawing edges between various vertex points in R^d for some d.

In this case, the function g is said to be a connection function and the RCM is said to be driven by X. The model itself is denoted by (X,g).

A generalization of the ordinary nearest-neighbor bond percolation of Z^d, the random-connection model of continuum percolation should be regarded as a contrasting alternative to the Boolean and Boolean-Poisson models, two models in which the second condition above is replaced with a random variable rho. More precisely, the Boolean and Boolean-Poisson models demonstrate percolation by way of constructing d-dimensional closed balls centered at points of X and assigning random radii determined by rho; contrarily, an RCM uses notions from graph theory, viewing points from X as vertices and inserting edges between pairs x_1,x_2 in X with probability g(|x_1-x_2|), independently of all other pairs of points in X, where |·| denotes the typical Euclidean distance in R^d. Despite their differences, however, the two methods are similar in that sophisticated machinery is necessary for a mathematically precise presentation of either; the formal construction for an RCM is as follows.

Let X be a point process defined on a probability space (Omega_1,F_1,P_1). Next, define the space Omega_2 to be the product

 Omega_2=product_(K(n,z),K(m,z^'))[0,1]
(1)

where the product is taken over all unordered pairs of binary cubes and define associated to Omega_2 the usual product measure P_2 so that all the marginal probabilities are given by Lebesgue measure on [0,1]. Finally, define Omega=Omega_1×Omega_2 and equip Omega with the product measure P=P_1 square P_2. Under this construction, an RCM is a measurable mapping from Omega into N×Omega_2 defined by

 (omega_1,omega_2)|->(X(omega_1),omega_2)
(2)

where here, N denotes the set of all counting measures on the sigma-algebra B^d of Borel sets in R^d which assign finite measure to all bounded Borel sets and which assign values of at most 1 to points.

One then transitions to percolation by first noting that each point x in X is contained in a unique binary cube K(n,z(n,x)) of order n and that, for each x in X, there is a unique smallest number n_0=n_0(x) such that K(n_0,z(n_0,x)) contains no other points of X P_1-almost surely. With this in mind, consider for any two points x,y in X(omega_1) the binary cubes

 K(n_0(x),z(n_0(x),x))
(3)

and

 K(n_0(y),z(n_0(y),y)),
(4)

respectively, whereby the points x and y are connected if and only if

 omega_2({(n_0(x),z(n_0(x),x)),(n_0(y),z(n_0(y),y))})<g(|x-y|)
(5)

where omega_2({(n,z),(m,z^')}) is the notation used to denote an element omega_2 in Omega_2. Using this construction, one gets a collection of vertices in d-dimensional Euclidean space which are connected according to a the above-described random process.

Some terminology utilized in random-connection models: The edge between two points x_1 and x_2 is denoted by the unordered pair {x_1,x_2} and x_1,x_2 are called end vertices of {x_1,x_2}. Two points x,y in X are said to be connected if there exists a finite sequence

 (x=x_1,x_2,...,x_n=y)
(6)

such that the edge {x_i,x_(i+1)} is inserted for all i=1,2,...,n-1, and in the typical graph-theoretic way, one then defines a component as a set S of points which is maximal with respect to the property that any two points a,b in S are connected to one another. The occupied component of the origin is denoted W and is considered to be this model's analogue of the notion of occupied components from Boolean models. There is no analogue of that model's notion of vacant components.

Random-ConnectionModelTermExample

The above figure illustrates a realization of a random-connection model, illustrating some of the terminology related to thereto. In this figure, the component W=W({0}) has the form W={0,x,y,z}, the edges of which have the form {0,x}, {x,y}, and {y,z}.


See also

AB Percolation, Bernoulli Percolation Model, Bond Percolation, Boolean Model, Boolean-Poisson Model, Bootstrap Percolation, Cayley Tree, Cluster, Cluster Perimeter, Continuum Percolation Theory, Dependent Percolation, Discrete Percolation Theory, Disk Model, First-Passage Percolation, Germ-Grain Model, Inhomogeneous Percolation Model, Lattice Animal, Long-Range Percolation Model, Mixed Percolation Model, Oriented Percolation Model, Percolation, Percolation Theory, Percolation Threshold, Polyomino, Random-Cluster Model, Random Walk, s-Cluster, s-Run, Site Percolation

This entry contributed by Christopher Stover

Explore with Wolfram|Alpha

References

Meester, R. and Roy, R. Continuum Percolation. New York: Cambridge University Press, 2008.

Cite this as:

Stover, Christopher. "Random-Connection Model." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Random-ConnectionModel.html

Subject classifications