Calculate the number of triplets in a graph

Question

I try to compute the global clustering coefficient of a graph in Matlab using the adjacency matrix. I know how to find the number of closed triangles: trace(A^3), but I do not have any idea how to find open triplets in a graph efficiently. I wrote a code traversing each node and checking for open triangles, but it does not work for large datasets. Is there any option to calculate the number of all triplets (three connected nodes) in a graph?

Answer 1

With the same matrix calculations that gave you closed triangles, we can find open triplets.

The $(i,j)$ entry of $A^2$ counts the number of paths of length $2$ from $i$ to $j$. Then, computing $\mathbf 1^{\mathsf T}\!A^2 \mathbf 1$ (where $\mathbf 1$ is the all-ones vector) will add up all these values, telling you the total number of paths of length $2$ in your graph. I think Matlab can also do this with sum(A^2,'all') or sum(sum(A^2)), but I'm not a Matlab user so I can't be sure.

A set of three vertices $\{i,j,k\}$ will contribute:

• $0$ to this total if the graph has $0$ or $1$ of the edges between them, since then there are no paths of length $2$ involving $i,j,k$.
• $2$ to this total if the graph has $2$ of the edges between them, since then there are two paths (one in either direction).
• $6$ to this total if the graph has all $3$ of the edges between them, since then any permutation of $\{i,j,k\}$ is a path.

Therefore $\mathbf 1^{\mathsf T}\!A^2 \mathbf 1$ gives you $2$ times the number of open triplets plus $6$ times the number of closed triplets. You already have the closed triplets from $\operatorname{tr}(A^3)$, so this lets you solve for the open ones.

(Double-check that I'm getting the terminology right - I always forget how symmetry is counted for clustering coefficients - but the idea should be sound either way.)