MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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
up vote 3 down vote accepted

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}.$$

share|cite|improve this answer
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 – Douglas Zare Aug 3 '12 at 1:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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