Expectation of the power of random graph's adjacency matrix

Question

I am trying to find the power of the random graph's adjacency matrix.

Consider the $2N$ number of nodes, where $N \geq 2$ is a fixed natural number.

WLOG, let nodes with index $1$ to $N$ belong to Group 1, and nodes with index $N + 1$ to $2N$ belong to Group 2.

Then, for a node pair within the same group, a pair of nodes form an edge with the probability of $p$ (i.e., $P(\{v_{i},v_{j}\} \in \mathcal{E}) = p$ if $v_{i}$ and $v_{j}$ belong to the same group.)

Else, for a node pair in the different groups, a pair of nodes form an edge with the probability of $1-p$ (i.e., $P(\{v_{i},v_{j}\} \in \mathcal{E}) = 1-p$ if $v_{i}$ and $v_{j}$ belong to the different groups.)

We do not allow the self-loop.

You may think this is a variant of the Erods-Renyi random graph, where there are two disjoint node groups. Note that this is an undirected graph.

Let $A$ be an adjacency matrix of this random graph.

My question is: What is the closed-form solution to the expectation of 4-power and 3-power of $A$? That is: $\mathbb{E}_{A}[A^{3}]$ and $\mathbb{E}_{A}[A^{4}]$.

In other words, what would be the expected number of length-3 and length-4 paths between node $v_{i}$ and $v_{j}$ (this would differ whether $v_{i}$ and $v_{j}$ belong to the same group or not)?

Thank you.

Answer 1

A simple way to solve such problem is to consider all possible paths. Note that for some pairs of paths, events of their existence are dependent, but we don't need to take it into account due to linearity of expectation. So the total expected number of $(u, v)$-paths in random graph $G$ is $$\sum_{Q \in \mathcal P_\ell^{u, v}} \prod_{e \in E(Q)}P\{\,e \in E(G)\,\},$$ where $\mathcal P_\ell^{u, v}$ is the set of all $(u, v)$-path of length $\ell$ in complete graph $H \cong K_{|G|}$ with $V(H) = V(G)$.

Let's consider all cases for $\ell = 3$:

• Vertices $u$ and $v$ belong to different groups. There are $4$ types of paths:

  • Every edge connects vertices of different groups. There are $n - 1$ ways to choose the second vertex, and $n - 1$ ways for the third one. The expected number of such paths is $$(1 - p)(n - 1)(1 - p)(n - 1)(1 - p) = (n - 1)^2(1 - p)^3.$$
  • Only the first edge connects vertices of different groups. There are $(n - 1)(n - 2)$ ways to choose the second and the third vertices. The expected number of such paths is $$(1 - p)(n - 1)p(n - 2)p = (n - 1)(n - 2)(1 - p)p^2.$$
  • Only the third edge connected vertices of different groups. This type of the same as previous in sense of the expected number of paths.
  • Only the second edge connects vertices of different groups. There are $n - 1$ ways to choose the second vertex and the same number for the third one. The expected number of such paths is $$p(n - 1)(1 - p)(n - 1)p = (n - 1)^2(1 - p)p^2.$$

  So the total expected number of $(u, v)$-paths of length $3$ is $$(n-1)^2(1 - p)^3 + 2(n - 1)(n - 2)(1 - p)p^2 + (n - 1)^2(1 - p)p^2 = (n - 1)(1 - p)((n - 1)(1 - 2p + 4p^2) - 2p^2).$$

• Vertices $u$ and $v$ belong to the same group, but $u \ne v$. Again there are $4$ types of paths:

  • Every edge connects vertices of the same group. There are $(n - 2)(n - 3)$ ways to select the second and the third vertices. The expected number of such paths is $$p(n - 2)p(n - 3)p = (n - 2)(n - 3)p^3.$$
  • Only the first edge connects vertices of the same group. There are $(n - 2)$ ways to select the second vertex and $n$ ways to select the third one. The expected number of such paths is $$p(n - 2)(1 - p)n(1 - p) = n(n - 2)(1 - p)^2p.$$
  • Only the third edge connects vertices of the same group. This type of the same as previous in sense of the expected number of paths.
  • Only the second edge connects vertices of the same group. There are $n(n - 1)$ ways to choose the second and the third vertices. The expected number of such paths is $$(1 - p)np(n - 1)(1 - p) = n(n - 1)(1 - p)^2p.$$

  So the total expected number of $(u, v)$-paths of length $3$ is $$(n - 2)(n - 3)p^3 + 2n(n - 2)(1 - p)^2p + n(n - 1)(1 - p)^2p.$$

• $u = v$. This case is essentially the same as the previous one, but the number of ways to choose a vertex in the same group is greater by $1$. The total expected number of $(u, v)$-paths of length $3$ is $$(n - 1)(n - 2)p^3 + 3n(n - 1)(1 - p)^2p.$$

For $\ell = 4$ you have more paths types to consider, but it is still doable manually. On the other hand we need to consider only number of edges between vertices from different groups and number of vertices in each group. It gives us a summation like: $$\sum_{x = 0}^{\lfloor\ell / 2\rfloor} (1 - p)^{2x}p^{\ell - 2x}\sum_{y = x}^{(\ell - x)[x > 0]}\binom{y - 1}{x - 1}\binom{\ell - y}{x}\frac{n!}{(n - y)!}\frac{(n - 1)!}{(n - \ell + y)!}$$ for the case $u = v$ and similar sums for other cases. Here $x$ is the number of "visits" to the other group, $y$ is the number of vertices in other group and $\binom{y - 1}{x - 1}\binom{\ell - y}{x}$ is the number of ways to choose $2x$ places for edges between vertices from different groups among $\ell$ edges, so that $y - x$ edges belong to the other group and $\ell - y - x$ edges belong to the original group.