I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.

I would like to know the probability a random node is in a component of size $m$.

It's sufficient for me to know what the size distribution is of components in small Erdos-Renyi networks. Is there a straight-forward calculation for this?

The best I can think of at the moment is to try to take all connected graphs of size $m\leq n$, and then determine their probability of being a component of an Erdos-Renyi network. It's not obvious to me how to deal with this since I don't know a straightforward way to enumerate all connected graphs of size $m$ (though given such a connected graph, it's straightforward to calculate it's probability of being a component of an Erdos-Renyi network)

  • $\begingroup$ Note that the probability that some given connected graph $H$ is a component of $G(n,p)$ depends only on the number of vertices and edges. So it is the counts that matter, not the graphs themselves, and that is a much easier task. $\endgroup$ – Brendan McKay Sep 13 '18 at 11:35

The distribution of component size in Erdos-Renyi networks is discussed in many places, and known analytically. A recent reference that summarizes this is in Appendix A of

Eytan Katzav, Ofer Biham, and Alexander K. Hartmann, Distribution of shortest path lengths in subcritical Erdős-Rényi networks, Phys. Rev. E 98, 012301 (2018).

I hope this helps

  • $\begingroup$ Thanks for getting back to me. I've found: "A moment-generating formula for Erdős-Rényi component sizes" projecteuclid.org/euclid.ecp/1524708114 which gives a linear system of equations I can use. The appendix you point to seems to work only as an approximation that is accurate in the large network limit below the giant component threshold. In my case I need to be able to work in quite small networks. I'm interested in, for example, being able to say for a graph of 20 nodes, what is the probability of a component of 6 nodes. Can that be found from the paper you've linked? $\endgroup$ – Joel Feb 3 at 19:36

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.