2
$\begingroup$

Given an Erdős–Rényi random graph with n nodes and edge probability p, what is the expected number of nodes in the connected component containing a randomly selected node?

In other words, if I randomly select one node in the graph, how many nodes should I expect to be in the connected component it is a member of?

$\endgroup$
  • $\begingroup$ Is p a constant, or a function of n? $\endgroup$ – Studentmath Sep 30 '14 at 11:07
  • $\begingroup$ p is some constant independent of n. Ideally I'd like to know the expected size of the connected component containing a randomly selected node as a function of p and n. $\endgroup$ – user83704 Sep 30 '14 at 11:15
  • $\begingroup$ If n is arbitrarily large, the graph is w.h.p connected and the question loses its point. When n is also a constant, it requires some thinking. Will try to. $\endgroup$ – Studentmath Sep 30 '14 at 11:54
  • $\begingroup$ yeah, I'm interested in the behavior for arbitrary finite values of n. Thanks! $\endgroup$ – user83704 Sep 30 '14 at 12:06
  • $\begingroup$ Just so you know, by symmetry, the distribution of the component containing a randomly selected node is the same as the distribution of the component containing some generic fixed vertex. $\endgroup$ – D Poole Oct 3 '14 at 12:49
2
$\begingroup$

Let $C(n,p)$ be the probability of an $n$-node Erdős–Rényi random graph with edge probability p being connected. From this question we know that:

$C(n,p) = 1$ if $n=1$ (one node graphs are trivially connected)

$C(n,p) = 1 - \sum\limits_{i=1}^{n-1} C(i,p) {n-1 \choose i-1} (1-p)^{i(n-i)}$ otherwise.

Let $P(k, p, n)$ be the probability that our node of interest is the member of an exactly $k$ node cluster in an $n$-node Erdős–Rényi random graph with edge probability $p$. $P$ can be calculated from $C$ as:

$P(k, p, n) = C(k,p) {n-1 \choose k-1} (1-p)^{k(n-k)}$

Then from $P$ we can calculate the desired expected value as:

$\sum\limits_{k=1}^{n} P(k, p, n) \times k$

$\endgroup$

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.