The Impact of Edge Correlations in Random Networks
András Faragó
Department of Computer Science
The University of Texas at Dallas
800 West Campbell Road
Richardson, Texas 75080, USA
Abstract
Random graphs are frequently used models of real-life random networks. The classical Erdös–Rényi random graph model is very well explored and has numerous nontrivial properties. In particular, a good number of important graph parameters that are hard to compute in the deterministic case often become much easier in random graphs. However, a fundamental restriction in the Erdös–Rényi random graph is that the edges are required to be probabilistically independent. This is a severe restriction, which does not hold in most real-life networks.
We consider more general random graphs in which the edges may be dependent. Specifically, two models are analyzed. The first one is called a p-robust random graph. It is defined by the requirement that each edge exist with probability at least p, no matter how we condition on the presence/absence of other edges. It is significantly more general than assuming independent edges existing with probability p, as exemplified via several special cases. The second model considers the case when the edges are positively correlated, which means that the edge probability is at least p for each edge, no matter how we condition on the presence of other edges (but absence is not considered). We prove some interesting, nontrivial properties about both models.
Keywords: random graph; dependent edges; monotone graph property; edge correlation; geometric random graph
Cite this publication as:
A. Faragó, "The Impact of Edge Correlations in Random Networks," Complex Systems, 30(4), 2021 pp. 525–537.
https://doi.org/10.25088/ComplexSystems.30.4.525
