2
$\begingroup$

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)

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 13, 2018 at 11:35
  • $\begingroup$ I fear most results on component size in ER graphs are for large $n$. But if $n$ is so small, then can't we enumerate all possible graphs with sampling probability, and their component size? $\endgroup$
    – Matthieu Latapy
    Commented Jan 16, 2021 at 20:06

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\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
    Commented Feb 3, 2019 at 19:36

You must log in to answer this question.

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