Using formula to count number of cycles in undirected graph in python

Question

I came across this formula to get the number of 4-cycle in an undirected graph:

 [![formula to calculate the number of 4-cycle][1]][1]

 Ck = 1/2k Tr(Pk-1 A)

 k stands for k-cycle, and A is the adjacency matrix, Pk-1 is the path count matrix

the webpage link:

[mathWorld]http://mathworld.wolfram.com/GraphCycle.html

I am now trying to code this simple formula in python, I could use NetworkX's adjacency_matrix function to get the adjacency matrix, and I could get the matrix trace too. I am just not sure about the so-called matrix of path count Pk, I googled a while but found no direct explanation on this.Could experts suggest what this Pk matrix is and I wonder if it is possible to code it in Python?

Thanks in advance!

Answer 1

My guess would be that P_k = A^k. But as you are interested in the number of 4 cycles you can simply use the formula (3) of your link:

8c_4 = Tr(A^4) - 2m - 2 \sum_i{i\ne j} a_{ij}^{(2)}

where a_{ij}^{(2)} are the elements of A^2.

This formula should be easily implementable via numpy.