Graph, random

A probabilistic model for the study of frequency characteristics of various graph parameters. A random graph is usually understood to mean a certain class of graphs $ {\mathcal G} = \{ G \} $ with a given probability distribution. An arbitrary graph $ G $ from $ {\mathcal G} $ is said to be a realization of the random graph. Any numerical characteristic (parameter) of a graph (cf. Graph, numerical characteristics of a) can be regarded as a random variable. The concept of a random graph is highly useful in modelling connection networks which are subject to certain random changes or of logical networks whose elements may assume defective states; in considering a picture of phase transformations in statistical physics; in studying various biological processes; in problems of minimization of a Boolean function, etc. In several cases the concept of a random graph makes it possible to utilize probability theory as a tool in order to obtain asymptotic solutions of enumeration problems.

In a typical construction of a random graph, all realizations are obtained by applying to a non-random graph $ G $( most often a complete graph) a certain procedure for the removal of its edges; it is usually assumed in so doing that the removals of different edges are independent events, and that the removal of an edge $ e $ occurs with probability $ q ( e) $. Such a construction of a random graph is denoted by $ {\mathcal G} _ {G} ( \{ q ( e) \} ) $. Of greatest interest is the study of the various numerical connectivity characteristics of a random graph $ {\mathcal G} _ {G} ( \{ q ( e) \} ) $, such as the number of connected components, the diameter, radius, the connectivity number, etc., which can be interpreted as characteristics of the reliability of the respective connection network or logical network. In such a case the number $ 1 - q ( e) $ characterizes the reliability of a connection $ e $, while $ q ( e) $ is the probability of its leaving the system.

Let $ G $ be a complete graph with $ n $ vertices and let $ q ( e) \equiv q $, $ 0 < q < 1 $. The random graph $ {\mathcal G} _ {G} ( \{ q ( e) \} ) $ is connected, has diameter and radius equal to 2 and contains a Hamilton cycle (cf. Graph circuit) with a probability which tends to one as $ n $ tends to infinity. If $ q ( e) $ is a function of the number of vertices $ n $, then the probability of the random graph $ {\mathcal G} _ {n} ( q) = {\mathcal G} _ {G} ( \{ q ( e) \} ) $ being connected depends on the closeness of $ 1 - q ( e) $ to $ ( \mathop{\rm ln} n)/n $. More exactly, let

$$ x _ {n} = \ n ( 1 - q ( e)) - \mathop{\rm ln} n; $$

then $ {\mathcal G} _ {n} ( q) $ tends to one as $ n \rightarrow \infty $, if $ \lim\limits _ {n \rightarrow \infty } x _ {n} = \infty $; it tends to zero if $ \lim\limits _ {n \rightarrow \infty } x _ {n} = 0 $; it tends to $ e ^ {- e ^ {-} c } $ if $ \lim\limits _ {n \rightarrow \infty } x _ {n} = c $, where $ c $ is a constant. In the last-mentioned case the number of edges of the random graph is asymptotically equal to $ ( n \mathop{\rm ln} n)/2 $.

The same random graph $ {\mathcal G} _ {n} ( q) $ can also be regarded as the graph obtained from the non-random empty graph with $ n $ vertices by randomly connecting its vertices by edges so that any pair of vertices has probability of being connected, independently of the others, equal to $ p = 1 - q $. This mode of formation of the graph $ {\mathcal G} _ {n} ( q) $ is made dynamic if one puts $ q = e ^ {- t } $, $ t > 0 $, $ t $ being assigned the meaning of time. The situation is then as follows. At the initial moment of time $ t = 0 $ one has $ n $ separate vertices. Then, as the value of $ t $ increases, there appear non-trivial connected components, representing trees or connected graphs with one cycle and a small number of vertices. Next there appears one "main" component containing a number of vertices asymptotically equal to $ n $( for large values of $ n $). The process is subsequently distinguished by growth of the main component and by decrease in the number of small components. Finally, at some moment of time, the graph becomes connected. This evolution of the random graph can be regarded as the model of the picture of phase transformations, where the main component plays the role of the liquid phase, while the part of the rarified phase is played by components with a small number of vertices.

There exist many other types of random graphs, e.g. those connected with trees (random trees), with one-place mappings of a finite set into itself (random mappings), and with subgraphs of the $ n $- dimensional unit cube (random Boolean functions).

References

[1]	E.F. Moore, C.E. Shannon, "Reliable circuits using less reliable relays, I,II" J. Franklin Inst. , 1 (1960) pp. 109–148
[2]	V.E. Stepanov, , Problems in Cybernetics. Proc. Sem. in comb. math. , Moscow (1973) pp. 164–185 (In Russian)
[3]	, Discrete mathematics and mathematical problems in cybernetics , 1 , Moscow (1974) (In Russian)
[4]	A. Sapozhenko, "The geometric structure of almost all Boolean functions" Probl. Kibernetiki , 30 (1975) pp. 227–261 (In Russian)

References

[a1]	P. Erdös, A. Renyi, "On random graphs I" Publ. Math. Debrecen , 6 (1959) pp. 290–297
[a2]	P. Erdös, A. Renyi, "On the evolution of random graphs" Publ. Math. Inst. Hung. Acad. Sci. , 5 (1960) pp. 17–61
[a3]	B. Bollobas, "Graph theory and combinatorics" , Acad. Press (1984)