Number of Fourcycles in Networks
I’m in the middle of moving my website from WordPress to Github Pages. I’ve exported my posts on WordPress into a .xml
file and have used this great program to transform the pages into Markdown documents. One problem that remains is translating equations from the blogs in Wordpress to those in Jekyll. So, I’m trying different things out. So, here is a test using the same post that I’ve used to test Wordpress when I started there (by the way, the reason for working on this weird mathematical problem, if I remember correctly, was the amazing AJS article by Peter Bearman, James Moody, and Katherine Stovel on the sexual network of high school students).
Number of FourCycles in a Graph
Let $ G=(V,E) $ be a graph with associated adjacency matrix $ A $. Consider a closed walk of length 4 starting at the vertex $ v_1\in V $. We have to consider four different scenarios:

for each $ v_j $ adjacent to $ v_i $, there exists a lengthfour walk $\{v_i, v_j,v_i,v_j,v_i\}$ which is obviously no 4cycle. The number of such lengthfour walks are equal to the degree of $ v_i $;

if $\{v_i,v_j\}, \{v_j,v_k\} \in E(G)$, $ i\ne j\ne k $, then $ \{v_i,v_j,v_k,v_j,v_i\} $ is a walk of length 4 but no 4cycle. The number of such walks is equal the degree of $ v_j $ minus one (the tie to $ v_i $);

if $ v_i $ has more than one neighbor, then $ \{v_i,v_j,v_i,v_k,v_i\} $ is also a walk of length 4, but not a cycle. For a vertex with more than one neighbor, the number of these walks are given as $ 2\binom{deg(v_i)}{2} $;

if $ \{v_i,v_j,v_k,v_l,v_i\} $ is a length4 closed walk visiting distinct vertices, then so is $ \{v_i,v_l,v_k,v_j,v_i\} $. Hence we are always double counting.
Let $ N=\{i: v_i \in V(G)\} $ be an index set and denote the degree of vertex $ v_i $ as $ d_G(v_i) $. If we let $ c_i $ be the number of 4cycles in which node $ i $ is involved, then
\[\begin{aligned} a_{ii}^{(4)} &= 2 c_i + d_G(v_i) + \sum_{j\in N}a_{ij}\Big(d_G(v_j)1\Big) + 2\binom{d_G(v_i)}{2} \\ &= 2 c_i + d_G(v_i) + \sum_{j\in N}a_{ij}\left(\sum_{k\in N}a_{jk} 1\right) + 2\binom{d_G(v_i)}{2} \\ &= 2 c_i + \sum_{k\in N}a_{ik}^{(2)} + 2\binom{d_G(v_i)}{2} \end{aligned}\]as $ d_G(v_i) = \sum_{j\in N}a_{ij} $. Hence,
\[\begin{aligned} c_i&= \frac{1}{2}\left(a_{ii}^{(4)}  \sum_{j\in N}a_{ij}^{(2)}  2\binom{d_{G}(v_i)}{2}\right). \end{aligned}\]Since each cycle of length 4 consists of four vertices, it follows that the number of 4cycles $ \vert\mathcal C_4\vert $ in $ G $ is
\[\begin{aligned} \vert\mathcal C_4(G)\vert &= \frac{1}{4}\left[\sum_{i\in N} \frac{1}{2}\left(a_{ii}^{(4)}  \sum_{j\in N}a_{ij}^{(2)}  2\binom{d_{G}(v_i)}{2}\right)\right] \\ &= \frac{1}{8}\left[\sum_{i\in N} a_{ii}^{(4)}  \sum_{i,j\in N}a_{ij}^{(2)}  2\sum_{i\in N}\binom{d_{G}(v_i)}{2}\right]. \end{aligned}\]Now, we notice that the first term is the trace of the matrix $ A^4 $ and that $ \sum_{i\in N} d_G(v_i) = 2\vert E(G)\vert $. Further,
\[\begin{aligned} \sum_{i,j\in N}a_{ij}^{(2)} &= \sum_{i\in N} a_{ii}^{(2)}+ 2\sum_{i\ne j \land i,j \in N}a_{ij}^{(2)} \\ &=\sum_{i\in N} d_G(v_i) + 2\sum_{i\in N}\binom{d_G(v_i)}{2}, \end{aligned}\]i.e., the sum of the elements in $ A^2 $ is equal to the diagonals plus the offdiagonals. But the sum of the diagonals is equal to the sum of the degree sequence of the graph and the sum of the offdiagonals is equal to the number of length2 paths. The number of length2 paths can be calculated, in turn, as follows: choose a vertex, say $ v_i $; if the vertex has a degree greater than one, calculate the number of ways in which any two neighbors of $ v_i $ can be chosen, each of which determines a unique length2 path for which $ v_i $ lies at the center. Summing over this number for all vertices in the graph gives the number of length2 paths, as no two different vertices can lie at the center of the same length2 path. On the other hand, if $ d_G(v_i) \le 1 $, $ \binom{d_G(v_i)}{2}=0 $.
Therefore it follows that
\[\begin{aligned} \vert\mathcal C_4(G)\vert &= \frac{1}{8}\left( \text{trace}(A^4)  2\vert E(G)\vert  4\sum_{i}\binom{d_G(v_i)}{2}\right). \end{aligned}\]Looks great!