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

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.

• I would approach this problem by considering the adjacency matrix of the graph. Depending on how you count the paths of length 2, you may need to exclude the cases where the path ends where it begins. These are just going back and forth on the same edge, and depending on your definition a "walk" like this might not be a valid path. – hardmath May 5 '18 at 18:08

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.

• Thanks Misha. What I want to understand is: choose a vertex $x$. Let his friends be those with whom he is connected by a path of length at most 2. The questions is how many friends does he have? And how many of them belong to another random graph? – fox May 10 '18 at 17:31
• I am also quite confused about the $1-p^2$. Why are we looking at the probability that NONE of the two edges are present? As long as just one edge is not there the original nodes $v$ and $w$ are not connected. – fox May 10 '18 at 17:33
• $1 - p^2$ is saying not both of the edges are present. It allows for one. – Misha Lavrov May 10 '18 at 20:02
• The answer to the question of how many friends is, in expectation, the number of vertices multiplied by the probability that they're friends. (If you're looking for the distribution, that's a harder question.) – Misha Lavrov May 10 '18 at 20:02

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.

• Wow that is great! And just now I understood Misha's answer. Thanks so much to you both! – fox May 11 '18 at 12:24
• As a way to verify, think that $q=0$. Then the number of friends of different gender is $n/2[1-(1-p)(1-p^2)^{n-2} ]$. Seems reasonable. But from your answer in the previous post I get $n/2[ 1- (1-p)^{n-1} (1+p)^{n-2} ]$. Are these expressions equivalent? – fox May 11 '18 at 15:35
• Yes, they're equivalent, since $$(1-p)(1-p^2)^{n-2}=(1-p)\bigl((1+p)(1-p)\bigr)^{n-2}=(1-p)^{n-1}(1+p)^{n-2}$$ – quasi May 11 '18 at 16:30
• Suppose $p=1$ for exposition. I had this intuition that I will have the same number of friends belonging to each graph even when $q$ is very small (I do not need $q=1$). The reason is that each extra link connects me to all the friends of that person. I thought this happens roughly at $1/n$ (in fact a smaller threshold). What I am saying is that $P(B)=1$ in expectation for some $q<1/n$, as I have found using computations using the above formulas, but I am unsure how to prove it. – fox May 14 '18 at 11:38
• To explore the issue, let $p=1,\;q=1/n$, and let $r=2$ ($2$ groups). Then the probability that you are friends with everyone is exactly $$1-\left(1-\frac{1}{n}\right)^{2n-1}$$ which approaches $$1-e^{-2}\approx .8646647168$$ as $n$ approaches infinity. – quasi May 14 '18 at 20:36