2
$\begingroup$

Suppose I have an Erdős–Rényi graph ${\cal G}(n,p)$, where $n$ is the total number of nodes and $p$ is the probability of an edge between any pair of nodes (edges are added independently). I subsample the graph by sampling $m$ nodes from the graph with probability proportional to the node degrees. Specifically, the probability of sampling node $i$ is $q_i = \frac{d_i}{\sum_{j=1}^n d_j}$, where $d_i, i=1, \ldots, n$ is the node degree for node $i$. We obtain a subgraph ${\cal G}_s$ consisting of the sampled nodes and whatever edges exist between them in the original graph. Can one say something concrete about the underlying distribution of such subgraphs, i.e., subgraphs obtained from by subsampling Erdős–Rényi graphs through the described subsampling process? I presume one may be able to write down an expression for $p_s$ (the probability that there exists an edge between a pair of nodes in the subgraph), but are the subgraphs still Erdős–Rényi? I believe the independence of edges between the nodes may be affected. If they are no longer Erdős–Rényi, then what is the underlying probabilistic model of such graphs? This seems like a natural question, but has anyone investigated similar questions before? Any pointers or references would help.

$\endgroup$
  • $\begingroup$ They will not and never were "Erdos-Reyni". Whether they are Erdős–Rényi is a more interesting question. $\endgroup$ – Misha Lavrov Oct 10 '18 at 23:28
1
$\begingroup$

The distribution of the subgraphs is different from $\mathcal G(n,p)$. One major issue is that you're much more likely to get "clone" vertices.

Consider $p=\frac12$, say. Here, for any $\epsilon>0$, with probability tending to $1$, all degrees are between $(1-\epsilon)\frac n2$ and $(1+\epsilon)\frac n2$. This means that $q_i$ stays between $(1-\epsilon)\frac1n$ and $(1+\epsilon)\frac1n$. So for any pair of vertices in the sampled graph $\mathcal G_s$, the pair of vertices they represent from the original random graph is almost equally likely (within a factor of $(1+\epsilon)^2$) to be any pair. In particular, $p_s$ is between $(1-2\epsilon)\frac12$ and $(1+2\epsilon)\frac12$.

In an $m$-vertex Erdős–Rényi graph with edge probability around $\frac12$, the probability that two vertices $v_i$ and $v_j$ have exactly the same set of adjacent vertices is around $2^{-m}$, and there are almost never any pairs with this property. In $\mathcal G_s$, this probability is at least $\frac1n$: a lower bound on the chance that the two vertices came from the same vertex of the original random graph. By the birthday paradox, if $m \gg \sqrt n$, you are going to get many such pairs.

In the case of sampling without replacement, the graph is very similar to an Erdős–Rényi graph when $p$ is large, by the same argument: we are not too much more likely to choose any vertex than any other. If we chose a random set of vertices $S$, we'd get an Erdős–Rényi graph on $S$, and our actual choice of $S$ is only slightly biased.

When $p$ is small, things look very different. For example, if $p = \frac1n$, then the average degree is $1$, but the highest degree is around $\log n$, and there are about $e^{-1}n$ vertices with degree $0$. So when sampling from this graph, we are going to pick up all or almost all of the vertices with high degrees, and none of the isolated vertices. (Of course, their degrees in $\mathcal G_s$ will be different.)

For an extreme case where this makes a huge difference, suppose we take $m = (1-e^{-1}-\epsilon)n$ for some $\epsilon>0$. Then $\mathcal G_s$ picks up almost all of the edges of the original graph, so it should be similar to a $\mathcal G(m, \frac cm)$ Erdős–Rényi graph, for $c = \frac{1}{1-e^{-1}}$. But compared to that graph, $\mathcal G_s$ has almost no isolated vertices: only $O(\epsilon n)$ of them.

I don't think there is a simple description of this random graph beyond the way you're constructing it (by taking a random graph and subsampling).

$\endgroup$
  • $\begingroup$ Thank you @Misha Lavrov. But, your argument is for sampling with replacement. What if one discards any nodes that have been sampled before so that the $m$ sampled nodes are ensured to be distinct? $\endgroup$ – Abas Oct 11 '18 at 15:16
  • $\begingroup$ @Abas I have edited my answer to consider that case. $\endgroup$ – Misha Lavrov Oct 11 '18 at 15:26
  • $\begingroup$ Many thanks @Misha Lavrov for the clarification. So it seems that it is not quite Erd\H{o}s-R\'{e}nyi even if ``similar'' in some regimes. But how similar is "very similar". For example, to ensure every node has a non-vanishing probability of being sampled, one can adjust the sampling probabilities $q_i$ by adding 1 to the node degrees. Would that make them more similar? Also would you mind clarifying how you obtain the $c/m$ probability? $\endgroup$ – Abas Oct 11 '18 at 15:46
  • $\begingroup$ (1) It would certainly make them more similar, because it would make the probabilities closer to uniform; it would be harder to find equally dramatic examples, but there would still be a bias in the degree distribution (2) The $c/m$ probability is the probability that gives about $\frac n2$ edges in an $m$-vertex graph. $\endgroup$ – Misha Lavrov Oct 11 '18 at 15:50
  • $\begingroup$ I see. One last question: Is there a way to rigorously capture deviation from the Erd\H{o}s-R\'{e}nyi model? For example, can one say something along the lines of "the probability it deviates is upper bounded" (not sure exactly how to capture deviation)? Thanks @Misha Lavrov. $\endgroup$ – Abas Oct 11 '18 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.