Let $\mathcal{G}$ be a simple (no self-edges) undirected graph with $N$ vertices, and denote $\mathbf{A}$ its adjacency matrix: $A_{ij}=1$ if there exists an edge between vertex $i$ and vertex $j$.

$\left[\mathbf{A}^k\right]_{ab}$ will represents the number of walks of length $k$ between vertices $a$ and $b$, in other words, the number of ways to go from $a$ to $b$ in $k$ steps.

## Question

Is there a simple way to count the number of walks of length $k$ starting from $a$ that passes via vertex $b$? (the step where it reaches $b$ is irrelevant).

A related question would be, given a random walk starting at $a$ what is the probability that it passes through $b$ at least once in $k$ steps?

I am afraid that these are hard questions to answer if we do not add details about $\mathcal{G}$. If this is the case, I would already find it interesting to know the answer of these questions in the case of $r-$regular graphs: All vertices possess $r$ edges.