It’s relatively easy to see that, for a network with Adjacency matrix A, the number of 3-loops is (1/6)Tr(A^3).

For 4-loops, we need (1/8)[Tr(A^4) – 2(sigma(k^2)) + sigma(k)] where k are the node degrees. So Tr(A^4) counts all possible 4-loops, including those that revisit nodes. It’s quite easy to see that the 2 adjustments take account of repeated visits to nodes/links, such as ABACA or ABCBA. For a k-node, the ABACA gives k choices for each of the 2nd and 4th nodes => k^2; the ABCBA gives k choices for the 2nd, and k-1 choices for the third nodes => k(k-1). These give a total of 2(k^2) – k. Summing these over all k and subtracting from the Tr(A^4) gives the formula above. (The 1/8 = 1/(2×4) allows for 4 starting nodes in any 4-loop as well as going clock- or anti-clockwise.

My real problem is trying to find a similar formula for 5-loops (or higher). I think the ‘adjustments’ to Tr(A^5) need to be based on combinations of a 2 and a 3 loop, including repeated nodes, like ABACDA (and several others), but I can’t seem to get the right formula. I’m testing on the following Adjacency matrix, with snippets of the code:

A = np.array([
 [0,1,1,1,1,0,0,0],
 [1,0,1,1,1,0,0,1],
 [1,1,0,1,1,0,0,1],
 [1,1,1,0,1,1,1,0],
 [1,1,1,1,0,0,0,0],
 [0,0,0,1,0,0,1,0],
 [0,0,0,1,0,1,0,0],
 [0,1,1,0,0,0,0,0]
])

Tr5 = Tr(A^5) #gives 1480
K2, K3, K4, K5 = K*K, K**3, K**4, K**5
K = np.array([4,5,5,6,4,2,2,2]) # the degrees of the nodes
S_K = np.sum(K) # gives 30 for sigma(k)
S_K_squared = np.sum(K2) # gives 130 for sigma(k^2)
S_K_cubed = np.sum(K3) # gives 618 for sigma(k^3)

I’m looking for a formula of the form (1/10)[ Tr(A^5) – adjustments] where adjustments = a(sigma(k^3)) + b(sigma(k^2)) + c(sigma(k)). I think the ‘a’ has to be a multiple of 5 to give an integer answer.

I’d be very interested in any solutions/thoughts.

Thanks, Aydin