3
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Uniformly among isomorphism classes of such graphs or uniformly among all possible choices of edges among a fixed set of $N$ vertices? $\endgroup$
    – Qiaochu Yuan
    Commented Jul 26, 2012 at 3:19

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – Zatrapilla
    Commented Aug 2, 2012 at 19:13
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Aug 2, 2012 at 23:51
  • $\begingroup$ I do have all that. Is there a go-to source for this kind of analysis, that you know of? Thanks! $\endgroup$
    – Zatrapilla
    Commented Aug 3, 2012 at 0:19
  • $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Aug 3, 2012 at 1:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .