I am considering the random graphs generated by the Erdős-Rényi model for this question. Random Graphs as Models of Networks by Newman is a reference on this topic. A random graph $\Gamma_{n,p}$ has $n$ vertices and there is $p$ probability that there is an edge between any pair of vertices. It is already known that the average degree of a vertex of a random graph, $z$, is $(n-1) p$. The probability distribution of the degree $k$ of a vertex is,

$$ p_k = {n \choose k} p^k (1-p)^{n-1} \simeq \frac{z^k e^{-z}}{k!} $$ which is the Poisson distribution.

My questions:

  1. For two random graphs, $\Gamma_{n_1,p_1}$ and $\Gamma_{n_2,p_2}$, let's take a vertex pair, $(v_{1_i}, v_{2_j})$, where, $v_{1_i} \in V(\Gamma_{n_1,p_1})$, $v_{2_j} \in V(\Gamma_{n_2,p_2})$, $i = 1, 2, \ldots, |V(\Gamma_{n_1,p_1})|$, $j = 1, 2, \ldots, |V(\Gamma_{n_2,p_2})|$ and $deg(v_{1_i}) = deg(v_{2_j})$. How many such pairs are possible?

  2. What is the probability distribution of the number of such pairs if $deg(v_{1_i}) = deg(v_{2_j}) = k$?

My effort so far:

As $\Gamma_{n_1,p_1}$ and $\Gamma_{n_2,p_2}$ are independently generated, the Poisson distributions will be mutually independent. In that case, the probability distribution of the number of such pairs if $deg(v_{1_i}) = deg(v_{2_j}) = k$, $p_{1,2,k}$, is

$$p_{1,2,k} = {n_1 \choose k} p^k_1 (1-p_1)^{n_1-1} \times {n_2 \choose k} p^k_2 (1-p_2)^{n_2-1}$$

Am I getting it right?

  • 1
    $\begingroup$ There is a difference between the $number$ of such pairs and the probability that a specific pair $(v_{1i}, v_{2j})$ is such that deg$(v_{1i})=$deg$(v_{2j})$. The former is more difficult to deal with. With that independence between the random graphs, you do have that the $probability$ that deg$(v_{1i})=k_1$ and deg$(v_{2j})=k_2$ is $${n_1 \choose k_1} p_1^{k_1} (1-p_1)^{n_1-k_1} \, {n_2 \choose k_2} p_2^{k_2} (1-p_2)^{n_2 - k_2}, $$ for any $k_1, k_2 \geq 0$. $\endgroup$ – D Poole Jul 6 '15 at 11:52
  • $\begingroup$ @DPoole, could you please explain why you have the exponent of $(1-p)$ be $(n - k)$? I thought it should be $(n-1)$. $\endgroup$ – Omar Shehab Jul 6 '15 at 14:01
  • 1
    $\begingroup$ I mean $n_1-1-k_1$ and $n_2-1-k_2$ in those exponents. For a vertex to have degree $k_1$ in the first random graph, we must have that this vertex has exactly $k_1$ neighbors out of the possible $n_1 - 1$ other vertices. So we choose the $k_1$ neighbors (${n_1 \choose k_1}$ factor), we flip these edges on ($p_1^{k_1}$ factor) and flip all the other edges off ($(1-p_1)^{n_1 - 1 - k_1}$ factor). $\endgroup$ – D Poole Jul 6 '15 at 15:22
  • $\begingroup$ @DPoole, in that case shouldn't your expression be: $${n_1 \choose k_1} p_1^{k_1} (1-p_1)^{(n_1-k_1 -1)} \, {n_2 \choose k_2} p_2^{k_2} (1-p_2)^{(n_2 - k_2-1)},$$? $\endgroup$ – Omar Shehab Jul 6 '15 at 15:51
  • 1
    $\begingroup$ Yes, I do mean that. $\endgroup$ – D Poole Jul 7 '15 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.