This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ from node $i$ to node $j$, with $ i \neq j \neq k \neq l$. Also see this post.

Let $A$ be the adjacency matrix. The notation I use below is: "$\cdot$" for usual matrix multiplication, "$\odot$" for element-wise matrix product, "d$(A)$" for the matrix with the same principal diagonal as $A$ and zeros elsewhere, and $S = A \odot A^T$.

The matrix for $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ will have its $i$, $j$ entry: $a_{ij}\cdot a_{jk}\cdot a_{kj}\cdot a_{jl}\cdot a_{lj}$. I have found this to be: $$ A \cdot (d(A^2))^2 $$

However, $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ also includes the following walks which repeat undesired nodes and should be subtracted: $$ \color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \rightarrow l \rightarrow j \tag{1} $$ $$ \color{red}i \rightarrow j \rightarrow k \rightarrow j \rightarrow \color{red}i \rightarrow j \tag{2} $$ $$ i \rightarrow j \rightarrow \color{red}k \rightarrow j \rightarrow \color{red}k \rightarrow j \tag{3} $$ $$\color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \tag{4} $$

My calculations for $(1) - (4)$ are: $$ S \cdot \text{d}(A^2) \tag{1} $$ $$ \text{d}(A^2) \cdot S \tag{2} $$ $$ A \cdot \text{d}(A^2) \tag{3} $$ $$ S \tag{4} $$

Every time one of $(1) - (3)$ is subtracted, $(4)$ is subtracted as well, since it is included in all three. Since it is not desired in the end, it is added back 2 times. Overall: $$ A \cdot (d(A^2))^2 - S \cdot \text{d}(A^2) - \text{d}(A^2) \cdot S - A \cdot \text{d}(A^2) + 2S$$

However, this is wrong and gives incorrect counts, even negatives. What am I missing here?


I think I have found the problem. The approach and formulas seem to be correct. What I did not consider is that they work for directed graphs, so $(i, j) \neq (j, i)$. This means that the matrix for each term has to be added to its transpose. Each terms also counts pattern $(4)$ twice, so it needs to be added $4$ times, not $2$. At the end, the matrix is divided by two.

If we have $$ \text{sym}(M) = M + M^T $$

Then the formula I ended up with is: $$ [\text{sym}(A \cdot d(A^2)^2) - \text{sym}(S \cdot \text{d}(A^2)) - \text{sym}(\text{d}(A^2) \cdot S) - \text{sym}(A \cdot \text{d}(A^2)) + 4S] \div 2 $$ (sym can be moved to the outside)

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.