2
$\begingroup$

I am wondering whether there exist a closed-form expression for the expected assortativity coefficient (http://arxiv.org/pdf/cond-mat/0205405.pdf) of an Erdos Ranyi random graph model $G(n,m)$, where $n$ is the number of nodes and $m$ is the density (http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).

A rough approximation might be provided by the correlation of a multinomial distribution, but it doesn't seem particularly accurate when the graph density is reasonably high. In fact, the degree of a node cannot be greater than $n-1$, whereas if we regard the degree vector of $G(n,m)$ to be distributed as $Multinomial(p_1, p_2, \ldots, p_n; m)$, where $p_i = m/n$, for $i = 1, \ldots, n$, the result is that a node might have a degree greater than $n-1$ with positive probability. This is clearly wrong! In any case, if we assume the degree vector of $G(n,m)$ to be distributed as $Multinomial(p_1, \ldots, p_n; m)$, the result is that the degree correlation (which represent the assortativity coefficient) is $\frac{1}{n-1}$.

I think that many of you would probably claim that the best choice is to use a truncated multinomial, $P(d_1, \ldots, d_n | d_1 < n-1, \ldots, d_n<n-1)$, and to derive the correlation of this multivariate expression. Nonetheless, before undertaking such a tedious work I'd like to see whether someone already know a closed-form expression for the expected assortativity coefficient.

Thank you very much for your help.

$\endgroup$

1 Answer 1

2
$\begingroup$

The expected degree correlation of (i.e., the assortativity of the node degrees) in an ER network is 0.

"In the ER model, since edges are placed at random without regard to vertex degree, it follows that r = 0 in the limit of large graph size." - http://en.wikipedia.org/wiki/Assortativity

$\endgroup$
1
  • $\begingroup$ "In the limit of large graph size" is important. The original question asked about arbitrary finite $n$ and $m$. $\endgroup$
    – Szabolcs
    Commented Jun 9, 2022 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.