Random graph by deleting edges from graph

Question

Given all possible pairs of vertices $v,v' \in V$, an Erdos Renyi (ER) graph can be generated by assigning an edge $(v,v')$ with a probability $p$.

But, given an existing graph $G=(V,E)$ and assigning a probability by which each edge in $G$ can be deleted, would the resulting graph also be considered an ER graph? Or more generally, do we get a random graph?

I have not come across such a construction for a random graph, so any references would really go a long way.

Answer 1

If you start with complete graph, So it'll be as @伽罗瓦 said. If not: $$P_{NotComplete}(G') = P_{Complete}(G'|G_0)$$ Where you start with $G_0$ and want to achive $G'$.

Answer 2

Usually, in an ER graph it is understood that the probability that an edge is sellected is the same for all edges.

Because of this, starting from a graph and doing the random process does not lead to an ER graph. Indeed, the edges not in $G$ will have a 0 probability of appearing in the subgraph, while the rest will have a different probability.

Just think what happens if you start from $G=N_n$, the null graph. Or $G= N_n \cup K_m$ for different values of $m,n$.

I would still refer to the model as a random model, but the graphs you will get are going to be only the subgraphs of your starting models. And depending on your starting models, the probabilities of the graphs you will get will not always correspond to the probabilities of ER graphs.

Answer 3

This is called the random subgraph model. Usually, it's phrased in the complementary way: we start with a graph $G$ called the host graph, and let $G_p$ be the random graph in which we keep each edge of $G$ with probability $p$. This is equivalent to deleting an edge with probability $1-p$.

(If $G = K_n$, we recover the Erdős–Rényi random graph.)

In general, $G_p$ does not have all the same nice properties that the Erdős–Rényi random graph does. However, with some assumptions on $G$, we can often prove results about $G_p$ that generalize their corresponding results for the Erdős–Rényi random graph.

For example, this paper is about finding long paths and cycles in $G_p$ assuming that $G$ has minimum degree $k$. For some $p$, we get conclusions extending the corresponding Erdős–Rényi results (which we can think of, in this case, as considering the special case $G = K_{k+1}$).