Random regular graph
Encyclopedia
A random r-regular graph is a graph
selected from
, which denotes the probability space of all r-regular graphs
on n vertices, where 3 ≤ r < n and nr is even. It is therefore a particular kind of random graph
, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.
s, it is possible to prove that certain properties of random r-regular graphs hold almost surely
. In particular, a random r-regular graph is almost surely r-connected
. In other words, although r-regular graphs with connectivity less than r exist, the probability of selecting such a graph tends to 0 as n increases.
If
> 0 is a positive constant, and d is the least integer satisfying
then, almost surely, a random r-regular graph has diameter at most d. There is also a (more complex) lower bound on the diameter of r-regular graphs, so that almost all r-regular graphs (of the same size) have almost the same diameter.
The distribution of the number of short cycles is also known: for fixed m ≥ 3, let Y3,Y4,…,Ym be the number of cycles of lengths up to m. Then the Yi are asymptotically independent Poisson random variables with means
. If this object has no multiple edges or loops (i.e. it is a graph), then it is the required result. If not, a restart is required.
A refinement of this method was developed by Brendan McKay
and Nicholas Wormald.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
selected from
, which denotes the probability space of all r-regular graphsRegular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
on n vertices, where 3 ≤ r < n and nr is even. It is therefore a particular kind of random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.
Properties of random regular graphs
As with more general random graphRandom graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s, it is possible to prove that certain properties of random r-regular graphs hold almost surely
Almost surely
In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory...
. In particular, a random r-regular graph is almost surely r-connected
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
. In other words, although r-regular graphs with connectivity less than r exist, the probability of selecting such a graph tends to 0 as n increases.
If
> 0 is a positive constant, and d is the least integer satisfyingthen, almost surely, a random r-regular graph has diameter at most d. There is also a (more complex) lower bound on the diameter of r-regular graphs, so that almost all r-regular graphs (of the same size) have almost the same diameter.
The distribution of the number of short cycles is also known: for fixed m ≥ 3, let Y3,Y4,…,Ym be the number of cycles of lengths up to m. Then the Yi are asymptotically independent Poisson random variables with means
Algorithms for random regular graphs
It is non-trivial to implement the random selection of r-regular graphs efficiently and in an unbiased way, since most graphs are not regular. The pairing model (also configuration model) is a method which takes nr points, and partitions them into n buckets with r points in each of them. Taking a random matching of the nr points, and then contracting the r points in each bucket into a single vertex, yields an r-regular graph or multigraphMultigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
. If this object has no multiple edges or loops (i.e. it is a graph), then it is the required result. If not, a restart is required.
A refinement of this method was developed by Brendan McKay
Brendan McKay
Brendan Damien McKay is a Professor in the Research School of Computer Science at the Australian National University . He has published extensively in combinatorics....
and Nicholas Wormald.