Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this type of random graph been studied before (i realise the output highly depends on what graph you start with).
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ This is the setup for "site percolation" on G, and there's a substantial literature. See some of the references at en.wikipedia.org/wiki/Percolation_theory $\endgroup$– j.c.Commented Jun 25, 2014 at 21:12
-
$\begingroup$ You may wish to read this. $\endgroup$– BachCommented Jun 26, 2014 at 8:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
There are at least two instances that I can recall where such graphs have been studied. As you've remarked, in general too much depends on the base graph, so you're only going to get somewhere by restricting to reasonable choices of base graph: for instance the complete graph on $n$-vertices is an awful choice for the base since you already know everything about any "random" induced subgraph just by knowing how many vertices it contains.
With that out of the way, here are two examples -- both involve sufficient conditions for the presence of giant components a.a.s (a la Erdos-Renyi). The first case of base graph is the Cayley graph of the symmetric group $S_n$ where generators are restricted to transpositions. See the paper
E Jin and C Reidys, Random Induced Subgraphs of Cayley Graphs Induced by Transpositions, 2009.
The main result involves sufficient conditions for the presence of a giant component. Similarly, if you change the base graph to (the 1-skeleton of) a product of $n$-dimensional cubes $Q^n$, then consider the paper:
C Reidys, Large Components in Random Induced Subgraphs in random induced subgraphs of N-cubes
answered Jun 25, 2014 at 21:18
$\begingroup$
$\endgroup$
Just a note that this issue can be interesting, and is widely used in applications, even for simple random graphs, such as Erdos-Renyi. For example, consider a graph on n-nodes with probability q for edges. Then after randomly selecting edges with probability p you have a similar random graph on approximately np edges. This sounds trivial, but note that the average degree has changed from nq to npq, which can change fundamental properties about the graph, such as the existence of a giant component if for example nq>1 and npq<1. Thus, by inoculating a small fraction of the nodes one can reduce the probability of large outbreaks in contagion models near criticality.
