Assume you have an n node connected graph.

Repeat the following m times:

  • choose a random set of nodes by selecting each existing node with probability p, then add a new node to the graph and join it to each of these chosen nodes.

After this the graph will consist of m+n nodes. My question then is, what is the probability the original n node connected component will now belong to a connected component of exactly k nodes, for k in n,n+1,..,n+m.

More specifically, given n, m and p, is there a closed form expression for the probability of each of the possible values of k?

It seems the probability that none of the m nodes join on to the original n node cluster = P(k=n) = $(1-p)^{n \times m}$. Other than that though, I don't really know how to approach this problem, so any help would be much appreciated!


While I don't have a closed form for this probability. There is a way to break up this probability into parts which may be easier to deal with, especially if you have a specific range of the parameters, $n,m,p$, which you are interested in.

Another way to view this random structure is the following: In $G(m,p)$, the random graph on $m$ vertices with each potential edge present with probability $p$, each of the $m$ vertices is "infected" with probability $1-(1-p)^n$ independently of one another (and independently of the edges!). Each infected vertex infects each other vertex in its component.

What is the probability that the total number of infected vertices is $l$? This probability is equal to the probability that your connected component at the end of your process has size $k=n+l$.

As you found, the probability that there are no infected vertices is $\left( (1-p)^n \right)^m$. Let $p_l$ be the probability that the total number of infected vertices is $l$. For $l \geq 1,$

\begin{align*} p_l &= \sum_{j=1}^l \sum_{w_1, \ldots, w_j} P( w_1, w_2, \ldots, w_j \text{ are first infected with total comp. size }l) \\&= \sum_{j=1}^l {m \choose j} \left(1-(1-p)^n\right)^j \left( (1-p)^n\right)^{m-j} P(j,l,m,p), \end{align*} where $P(j,l,m,p)$ is the probability that the first $j$ vertices in $G(m,p)$ have total component size $l$. Maybe I'm too used to finding only asymptotic expressions, but I think finding a closed form for this probability will be difficult.


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.