## The Impact of Edge Correlations in Random Networks

**András Faragó**

*Department of Computer ScienceThe University of Texas at Dallas800 West Campbell RoadRichardson, 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