How many paths of length 2 in a general random graph?

Question

Suppose you have several random graphs. Each one has $n$ nodes, connected among them with probability $p$. There are $r$ random graphs. Now, each node is connected to nodes of another random graph with probability $q$, in general different from $p$. Suppose that any node is a friend of anybody to whom he is either directly connected to by an edge, or by anyone with whom they share an endnode, i.e. anyone with whom there exists a path of length at most 2.

First question: How many friends each node has in expectation?

Second question: now suppose that half nodes in each graph are men, half women. How many expected women friends each male node has?

The answer must be a generalization of this one: Probability of friendship

Furthermore, the probability that node x is not a friend of someone in his own graph is something like

$(1-p) \sum^n_k \sum^{r(n-1)}_h p^k q^h (1-p)^{n-k} (1-q)^{(r-1)n-h} (1-p)^{k} (1-q)^{h}$

and the probability that node x is not a friend of someone in a different graph is something like

$(1-q) \sum^n_k \sum^{r(n-1)}_h p^k q^h (1-p)^{n-k} (1-q)^{(r-1)n-h} (1-p)^{k} (1-q)^{h}$

but in both cases I am missing a combinatorial factor.

Answer 1

It is easier to understand the probability that, given a node $v$, another node $w$ is not connected to it by a path of length $1$ or $2$.

For example, to answer question $2$, we can assume both nodes $v$ and $w$ are in the same $n$-vertex graph. In that case,

• There is no edge $vw$, which happens with probability $(1-p)$.
• For any node $x$ in the same $n$-vertex graph, edges $vx$ and $wx$ are not both present, which happens with probability $1-p^2$.
• For any node $x$ in another $n$-vertex graph, edges $vx$ and $wx$ are not both present, which happens with probability $1-q^2$.

Combining these, there is a probability $$(1-p)(1-p^2)^{n-2}(1-q^2)^{n(r-1)}$$ that there is not a path of length $1$ or $2$ between $v$ and $w$. So the expected number of vertices in the same $n$-vertex graph that do have such a path is $$(n-1)\left(1 - (1-p)(1-p^2)^{n-2}(1-q^2)^{n(r-1)}\right)$$ which is the number of other vertices in the same $n$-vertex graph multiplied by the probability that each one of them has such a path.

We can find the expected number of vertices connected to $v$ in other $n$-vertex graphs in a similar way.

Answer 2

I think Misha Lavrov's answer is better than mine, but my approach, though longer, does get the required results . . .

Let $m=n(r-1)$.

For a given member $y$ of your group, other than yourself, let $A$ be the event that you are connected to $y$ by a path of length at most two.

For a given member $z$ of one of the other groups, let $B$ be the event that you are connected to $z$ by a path of length at most two.

Then the expected number of vertices which are connected to you by a path of length at most two is just $$(n-1)P(A)+mP(B)$$ and if $n$ is even, and each group has ${\large{\frac{n}{2}}}$ members of each gender, then the expected number of vertices whose gender is opposite to yours, and which are connected to you by a path of length at most two is just $$\left({\small{\frac{n}{2}}}\right)\!P(A)+\left({\small{\frac{m}{2}}}\right)\!P(B)$$

It remains to compute $P(A)$ and $P(B)$.

Let $A',B'$ denote the complements of $A,B$, respectively (i.e., $A'=\text{not}\,A$, and $B'=\text{not}\,B$). \begin{align*} \text{Then}\;\;P(A') &=(1-p)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-2}{\small{\binom{n-2}{k}}}p^k(1-p)^{(n-2)-k}(1-p)^k\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^m{\small{\binom{m}{k}}}q^k(1-q)^{m-k}(1-q)^k\right)\\[8pt] &=(1-p)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-2}{\small{\binom{n-2}{k}}}p^k(1-p)^{n-2}\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^m{\small{\binom{m}{k}}}q^k(1-q)^m\right)\\[8pt] &=(1-p)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left((1-p)^{n-2}\sum_{k=0}^{n-2}{\small{\binom{n-2}{k}}}p^k\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left((1-q)^m\sum_{k=0}^m{\small{\binom{m}{k}}}q^k\right)\\[4pt] &=(1-p)\Bigl((1-p)^{n-2}(1+p)^{n-2}\Bigr)\Bigl((1-q)^m(1+q)^m\Bigr)\\[4pt] &=(1-p)(1-p^2)^{n-2}(1-q^2)^m\\[20pt] \text{and}\;\;P(B') &=(1-q)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-1}{\small{\binom{n-1}{k}}}p^k(1-p)^{(n-1)-k}(1-q)^k\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{m-n}{\small{\binom{m-n}{k}}}q^k(1-q)^{(m-n)-k}(1-q)^k\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-1}{\small{\binom{n-1}{k}}}q^k(1-q)^{(n-1)-k}(1-p)^k\right)\\[8pt] &=(1-q)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-1}{\small{\binom{n-1}{k}}}\bigl(p(1-q)\bigr)^k(1-p)^{(n-1)-k}\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left((1-q)^{m-n}\sum_{k=0}^{m-n}{\small{\binom{m-n}{k}}}q^k\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\sum_{k=0}^{n-1}{\small{\binom{n-1}{k}}}\bigl(q(1-p)\bigr)^k(1-q)^{(n-1)-k}\right)\\[8pt] &=(1-q)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\bigl(p(1-q)+(1-p)\bigr)^{n-1}\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left((1-q)^{m-n}(1-q)^{m-n}\right)\\[0pt] &\;\;\;\;\;{\LARGE{\cdot}}\left(\bigl(q(1-p)+(1-q)\bigr)^{n-1}\right)\\[4pt] &=(1-q)(1-pq)^{2n-2}(1-q^2)^{m-n}\\[0pt] \end{align*} Finally, since $P(A)=1-P(A')$, and $P(B)=1-P(B')$, we get \begin{align*} P(A) &= 1-(1-p)(1-p^2)^{n-2}(1-q^2)^m\\[4pt] P(B) &= 1-(1-q)(1-pq)^{2n-2}(1-q^2)^{m-n}\\[4pt] \end{align*} which completes the analysis.