Problem
Let $G = (V,E)$ be a simple graph, $A$ its adjacency matrix and let $c(u,v) = |N(u) \cap N(v)|$ be the number of common neighbours of any pair of nodes $u,v \in V$, i.e. $$c(u,v) = \big|\big\{ w \in V : \{u,w\},\{v,w\} \in E \big\}\big| \, .$$ How can the matrix of common neighbours, $C = \big(c(u,v)_{u,v \in V}\big)$, be expressed in terms of the adjacency matrix $A$?
Motivation
I'm a big fan of Linear Algebra and I a firm believer that many unobvious insights can be achieved by algebraic manipulations of the corresponding matrix representations.
Some examples
Here is a small collection of how important graph-theoretic properties can be expressed in terms of the adjacency matrix:
- The number walks of length $k$ from $u$ to $v$ is given by $p_k(u,v) = (A^k)_{uv}$.
- The number of shared triangles between two nodes can either be expressed as the number of walks of length $2$ that are also neighbours, $\Delta(G) = A^2 \odot A$, with $\odot$ denoting the pointwise multiplication.
- The degree vector of a graph can either be expressed as
- the sum of each row/column, $\deg(G) = A\mathbf{1}$,
- the diagonal of the squared adjacency matrix, $\deg(G) = \operatorname{diag}(A^2)$,
i.e. the number of $2$-walks from each node to itself.
- Similarly, the number of triangles at each node (which I'd like to call triangle degree) is the number of $3$-walks from each node to itself, $\deg_{\Delta}(G) = \operatorname{diag}(A^3)$.
Answer is $A^TA$, see comments above.