Erdős–Rényi model starting from non-complete graphs

Question

In the Erdős–Rényi model, they study graphs that are complete, i.e. to sample from $G(n,p)$ we start with the complete graph $K_n$ and leave each edge w.p. $p$ and drop the edge w.p. $1-p$. Then, they study the probable size of connected components (depending on thresholds given on $p$) etc.

Is there some known work done in a regime where the process is the same, but the initial graph is not $K_n$, but rather some other families of graphs. I am intrested in particular in families of graphs that are non homogenous in terms of the vertices' degrees, i.e. non-regular graphs and the degrees should be much smaller than $n-1$, even bounded by a constant.

Answer 1

Yes, lots of work has been done on this. Depending on if you're more of a physicist or more of a graph theorist, you might call this

• bond percolation on a graph $G$, where each edge of $G$ is taken to be "open" with probability $p \in [0,1]$ and "closed" otherwise. The most typical model is bond percolation in a $d$-dimensional lattice graph, but other cases are also studied.
• the random subgraph model, where in exactly the same way we define a random subgraph of a host graph. Some common notation for this is $G_p$ if we start with a graph $G$ and sample edges independently with probability $p$.

One paper that might interest you, if you're specifically curious about probable sizes of connected components, is The giant component in a random subgraph of a given graph by Chung, Horn, and Lu. This paper shows that under some assumptions on the host graph, there is a critical probability at which a giant component emerges in the random subgraph.

The authors do consider "graphs which are not necessarily regular, and can be relatively sparse" but you will have to decide for yourself if their conditions are flexible enough for the application you have in mind.