You get a bonus - 1 coin for daily activity. Now you have 1 coin

Random graph

Lecture



In mathematics, a random graph is a general term for the probability distribution of graphs. Random graphs can be described simply by a probability distribution or by a random process creating these graphs. The theory of random graphs is located at the junction of graph theory and probability theory. From a mathematical point of view, random graphs are needed to answer the question about the properties of typical graphs. Random graphs have found practical application in all areas where complex networks need to be modeled - a large number of random graph models are known that reflect various types of complex networks in various areas. In a mathematical context, the term random graph almost always means the Erdёos – Rényi random graph model. In other contexts, any graph model means a random graph .

Content

  • 1 Random graph models
  • 2Terminology
  • 3Properties of random graphs
  • 4Coloring random graphs
  • 5 Random trees
  • 6History
  • 7SM. also
  • 8Notes

Random graph models

A random graph is obtained from a set of n isolated vertices by sequentially randomly adding edges connecting vertices. The purpose of modeling random graphs is to determine at what stage a certain property of the graph appears. Different models of random graphs give different probability distributions on a graph. The most commonly studied is the distribution proposed by Hilbert and denoted by G ( n , p ), in which any possible edge appears independently with probability 0 < p <1. The probability of a random graph with m edges is equal to pm (1 - p ) N - m . The Erdёos – Rényi model [en] close to it, denoted by G ( n , M ), gives the same probability to all graphs that have exactly M edges. If to designate   Random graph with 0 ≤ MN , G ( n , p ) will contain {\ displaystyle   Random graph elements and any element falls out with probability   Random graph . This model can be considered as a snapshot for a certain point in time ( M ) of a random process on a graph.   Random graph that starts with n vertices with no edges, and at each step a new edge is added, chosen uniformly from the set of missing edges.

If we start from an infinite set of vertices and choose each possible edge independently with probability 0 < p <1, we get an object G , called an infinite random graph . Except for the trivial cases, when p is 0 or 1, this G almost certainly has the following properties:

If any n + m elements are given   Random graph , there is a vertex c in V that is adjacent to each vertex   Random graph and not connected to any of   Random graph .

It turns out that if the set of vertices is countable, then there exists, up to [en] of the isomorphism, a unique graph with such properties, namely, the Rado graph. Thus, any countable infinite graph is almost certainly a Rado graph, which for this reason is sometimes called simply a random graph . However, the analogous result is not valid for uncountable graphs for which there are many (non-isomorphic) graphs satisfying the above condition.

Another model that generalizes the Hilbert model of a random graph is the model of a random scalar product . A graph of a random dot product connects a real vector with each vertex. The probability of the edge uv between any vertices u and v is some function of the scalar product uv of the corresponding vectors.

Network probability matrices model random graphs through edge probabilities   Random graph so that this edge   Random graph exists in the specified time period. This model can be extended to oriented and non-oriented graphs, weighted and not weighted, to static and dynamic.

For MpN , where N is the maximum possible number of edges, the models G ( n , M ) and G ( n , p ) are most often used, almost always interchangeable.

A random regular graph forms a special case with properties that may differ from random graphs in the general case.

If we have a random graph model, any function on the graphs becomes a random variable. The task of studying this model is to determine, or at least estimate the probability of a property appearing.

Terminology

The term “almost reliably” in the context of random graphs refers to a sequence of spaces and probabilities, such that the probability of error tends to zero.

Properties of random graphs

The theory of random graphs studies typical properties of random graphs that are performed with a high degree of probability for graphs obtained for a certain distribution. For example, we can ask for given values ​​of n and p , what is the probability that G ( n , p ) is connected. When studying such questions, researchers often concentrate on the asymptotic behavior of random graphs — values ​​that different probabilities tend to as n grows. The percolation theory describes the connectedness of random graphs, especially unlimitedly large ones.

Percolation is related to the stability of a graph (also called a network). Let a random graph with n vertices and average degree be given   Random graph . Remove the random 1− p part of the edges and leave the p part. There is a critical threshold for percussion   Random graph , below which the network becomes fragmented, while above pc there are huge connectivity components.

Random graphs are widely used in the probabilistic method when trying to prove the existence of graphs with certain properties. The existence of a property on random graphs can often be a consequence, according to the Lemma of regularity of Szemerédi, the existence of this property for almost all graphs.

For random regular graphs, [en] G ( n , r -reg) is the set of r- regular graphs with r = r ( n ), such that n and m are positive integers, 3 ≤ r < n , and rn = 2 m evenly

The sequence of degrees of a graph G in Gn depends only on the number of edges in the sets

  Random graph

If the set of edges M in a random graph GM is large enough that almost all GM have a minimum degree of at least 1, then almost any GM is connected and, for even n , almost any GM contains a perfect matching. In particular, at the moment when the last isolated vertex disappears, in almost all random graphs, the graph becomes connected

Almost any process of constructing a graph with an even number of vertices when it reaches the minimum degree of 1 or a random graph when it reaches slightly more than ( n / 4) log ( n ) edges with a probability close to 1 ensures the existence of a complete match, except perhaps one vertex.

For some constant c, almost every labeled graph with n vertices and at least cn log ( n ) edges is Hamiltonian. With probability tending to 1, the addition of an edge, increasing the minimum degree of the graph to 2, makes it Hamiltonian.

Coloring random graphs

If a random graph G of order n with vertices V ( G ) = {1, ..., n } is given, the coloring can be obtained using the greedy algorithm (vertex 1 is colored with color 1, vertex 2 gets color 1 if it is not adjacent 1, otherwise it gets color 2, and so on).

Random trees

A random tree is a tree or oriented tree formed by a random process. In a large range of random graphs of order n and size M ( n ), the distribution of the number of trees of order k is asymptotically subject to the Poisson law. Types of random trees include uniform tightening trees [en], random minimal tightening trees, random binary trees [en], Cartesian trees, quickly viewed random trees, en Brownian trees, and random forests.

Story

Random graphs were first defined by Erdös and Rényi in the 1959 book On Random Graphs and independently by Gilbert in his article Random Graphs.

see also

  • Bose-Einstein condensation
  • Resonator Method [ru]
  • Complex Networks
  • Erdös – Rényi model [en]
  • Exponential random graph model
  • Graph theory
  • Network theory
  • Percolation
  • Semilinear response

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Probability theory. Mathematical Statistics and Stochastic Analysis

Terms: Probability theory. Mathematical Statistics and Stochastic Analysis