# The degrees in a random subgraph

Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.

Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ vertices, $d_k$ of which have degree $k$ (i.e., they are connected by an edge to $k$ other vertices).

Now suppose that you (uniformly) randomly pick $M$ vertices of $G$ to form a new graph $U$, $M < N$. Join two vertices of $U$ by an edge if there is an edge in $G$ between these two vertices. Hence $U$ is a random subgraph of $G$.

Now let $p_k$ be the number of vertices in $U$ that have degree $k$.

If $M$, $N$, and $d_k$ are fixed, what is the expectation of $p_k$?

-
Uniformly among isomorphism classes of such graphs or uniformly among all possible choices of edges among a fixed set of $N$ vertices? –  Qiaochu Yuan Jul 26 '12 at 3:19

It doesn't matter that $G$ was chosen randomly. The choice of $G$ might matter if you asked for something more complicated about the distribution than the expected value.

The probability that a vertex $v$ is included is $M/N$.

Let the degree of $v$ be $h \ge k$ in $G$. The chance that precisely $k$ of its neighbors are included in $U$, conditioned on the inclusion of $v$, is

$$\frac{{h \choose k}{N-h-1 \choose M-k-1}}{N-1 \choose M-1}.$$

So, the expected number of vertices of degree $k$ in $U$ is

$$\sum_{h \ge k} d_h \frac{M}{N}\frac{{h \choose k}{N-h-1 \choose M-k-1}}{N-1 \choose M-1}.$$

-
That works very well, thank you! I tried to use it to go in the opposite direction (deduce the degree distribution of the original graph $G$ given the degree distribution of the sample $U$), but I get horrible results. Do you have a suggestion for that problem? Thanks again! –  Zatrapilla Aug 2 '12 at 19:13
Choosing a random subset of the vertices will lose information. Do you have lots of samples, and huge graphs? Then you might be able to recover some information. –  Douglas Zare Aug 2 '12 at 23:51
I do have all that. Is there a go-to source for this kind of analysis, that you know of? Thanks! –  Zatrapilla Aug 3 '12 at 0:19
I don't know of a particular reference. I would try to do something like a maximum likelihood estimation. You might want to try stats.stackexchange.com. –  Douglas Zare Aug 3 '12 at 1:17