Random Graph Models with NonIndependent Edges
Volume 2  Issue 1
Zohre Ranjbar Mojaveri and Andras Farago*

Author Information
Open or Close
 Department of Computer Science, The University of Texas at Dallas Richardson, USA
*Corresponding author: Andras Farago, Department of Computer Science, The University of Texas at Dallas Richardson, USA
Received: November 24, 2020; Published: November 30, 2020
DOI:
10.32474/CTCSA.2020.02.000130
Full Text
PDF
To view the Full Article Peerreviewed Article PDF
Abstract
Random graph models play an important role in describing networks with random structural features. The most classical model
with the largest number of existing results is the Erd˝osR´enyi random graph, in which the edges are chosen interdependently at
random, with the same probability. In many reallife situations, however, the independence assumption is not realistic. We consider
random graphs in which the edges are allowed to be dependent. In our model the edge dependence is quite general, we call it
probust random graph. Our main result is that for any monotone graph property, the probust random graph has at least as high
probability to have the property as an Erd˝osR´enyi random graph with edge probability p. This is very useful, as it allows the
adaptation of many results from Erd˝osR´enyi random graphs to a nonindependent setting, as lower bounds.
Random networks occur in many practical scenarios. Some examples are wireless adhoc networks, various social networks, the
web graph describing the World Wide Web, and a multitude of others. Random graph models are often used to describe and analyze
such networks. The oldest and most researched random graph model is the Erd˝osR´enyi random graph G_{n, p}. This denotes a random
graph on n nodes, such that each edge is added with probability p, and it is done independently for each edge. A large number of
deep results are available about such random graphs, see expositions in the books [14]. Below we list some examples. They are
asymptotic results, and for simplicity we ignore rounding issues (i.e., an asymptotic formula may provide a noninteger value for a
parameter which is defined as integer for finite graphs).
The size of a maximum clique in G_{n, p} is asymptotically 2log_{1/p} n .
If G_{n, p} has average degree d, then its maximum independent set has asymptotic size (2n In d) / d .
The chromatic number of n, p G is asymptotically n/log_{b}n, where b=1p
The size of a minimum dominating set in G_{n, p} is asymptotically n/log_{b}n, where b=1/1p
The length of the longest cycle in G_{n, p}, when the graph has a constant average degree d, is asymptotically n(1− de^{−d} ) .
The diameter of G_{n, p} is asymptotically log n/ log(np), when np → ∞ . (If the graph is not connected, then the diameter is defined
as the largest diameter of its connected components.)
If G_{n, p} has average degree d, then the number of nodes of degree k in the graph is asymptotically
However, the requirement that the edges are independent is often a severe restriction in modelling reallife networks. Therefore,
numerous attempts have been made to develop models with various dependencies among the edges, see a survey in [2]. Here we
consider a general form of edge dependency. We call a random graph with this type of dependency a probust random graph.
Abstract
Definition 1 (probust random graph)
Definition 2 (Monotone Graph Property)
References