Namespaces
Variants
Actions

Difference between revisions of "Graph, random"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450001.png" /> with a given probability distribution. An arbitrary graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450002.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450003.png" /> is said to be a realization of the random graph. Any numerical characteristic (parameter) of a graph (cf. [[Graph, numerical characteristics of a|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|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.
+
<!--
 +
g0450001.png
 +
$#A+1 = 44 n = 0
 +
$#C+1 = 44 : ~/encyclopedia/old_files/data/G045/G.0405000 Graph, random
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
In a typical construction of a random graph, all realizations are obtained by applying to a non-random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450004.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450005.png" /> occurs with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450006.png" />. Such a construction of a random graph is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450007.png" />. Of greatest interest is the study of the various numerical connectivity characteristics of a random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450008.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g0450009.png" /> characterizes the reliability of a connection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500010.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500011.png" /> is the probability of its leaving the system.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500012.png" /> be a complete graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500013.png" /> vertices and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500015.png" />. The random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500016.png" /> is connected, has diameter and radius equal to 2 and contains a Hamilton cycle (cf. [[Graph circuit|Graph circuit]]) with a probability which tends to one as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500017.png" /> tends to infinity. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500018.png" /> is a function of the number of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500019.png" />, then the probability of the random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500020.png" /> being connected depends on the closeness of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500021.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500022.png" />. More exactly, let
+
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|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|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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500023.png" /></td> </tr></table>
+
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.
  
then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500024.png" /> tends to one as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500025.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500026.png" />; it tends to zero if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500027.png" />; it tends to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500028.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500029.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500030.png" /> is a constant. In the last-mentioned case the number of edges of the random graph is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500031.png" />.
+
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|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
  
The same random graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500032.png" /> can also be regarded as the graph obtained from the non-random empty graph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500033.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500034.png" />. This mode of formation of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500035.png" /> is made dynamic if one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500038.png" /> being assigned the meaning of time. The situation is then as follows. At the initial moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500039.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500040.png" /> separate vertices. Then, as the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500041.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500042.png" /> (for large values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500043.png" />). 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.
+
$$
 +
x _ {n}  = \
 +
n ( 1 - q ( e)) \mathop{\rm ln} n;
 +
$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045000/g04500044.png" />-dimensional unit cube (random Boolean functions).
+
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====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E.F. Moore,  C.E. Shannon,  "Reliable circuits using less reliable relays, I,II"  ''J. Franklin Inst.'' , '''1'''  (1960)  pp. 109–148</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.E. Stepanov,  , ''Problems in Cybernetics. Proc. Sem. in comb. math.'' , Moscow  (1973)  pp. 164–185  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A. Sapozhenko,  "The geometric structure of almost all Boolean functions"  ''Probl. Kibernetiki'' , '''30'''  (1975)  pp. 227–261  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E.F. Moore,  C.E. Shannon,  "Reliable circuits using less reliable relays, I,II"  ''J. Franklin Inst.'' , '''1'''  (1960)  pp. 109–148</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.E. Stepanov,  , ''Problems in Cybernetics. Proc. Sem. in comb. math.'' , Moscow  (1973)  pp. 164–185  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Discrete mathematics and mathematical problems in cybernetics'' , '''1''' , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A. Sapozhenko,  "The geometric structure of almost all Boolean functions"  ''Probl. Kibernetiki'' , '''30'''  (1975)  pp. 227–261  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdös,  A. Renyi,  "On random graphs I"  ''Publ. Math. Debrecen'' , '''6'''  (1959)  pp. 290–297</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  A. Renyi,  "On the evolution of random graphs"  ''Publ. Math. Inst. Hung. Acad. Sci.'' , '''5'''  (1960)  pp. 17–61</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Bollobas,  "Graph theory and combinatorics" , Acad. Press  (1984)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdös,  A. Renyi,  "On random graphs I"  ''Publ. Math. Debrecen'' , '''6'''  (1959)  pp. 290–297</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  A. Renyi,  "On the evolution of random graphs"  ''Publ. Math. Inst. Hung. Acad. Sci.'' , '''5'''  (1960)  pp. 17–61</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  B. Bollobas,  "Graph theory and combinatorics" , Acad. Press  (1984)</TD></TR></table>

Revision as of 19:42, 5 June 2020


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)

Comments

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)
How to Cite This Entry:
Graph, random. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_random&oldid=14679
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article