To understand this formula, first consider the numerator. Note that i,j,kAijAjkAki=i[A3]ii=trA3, that is, the trace of A3. We know that [A3]ii is equal to the number of walks of length 3 from node i to itself, which will be two if it is part of a closed triplet (there are two paths around the triplet) and zero otherwise. So the sum of the diagonal elements of A3 is exactly twice the number of closed triplets (and six times the number of triangles, as each node in the triangle is counted once). As for the denominator, let us examine how the degree of a node informs the number of connected triplets. If a node has degree zero, then it can't be part of a triplet, and the same is true for degree one. For a node of degree two, it must be part of one triplet (which may be closed or open). For degree three, the node is part of three triplets. We conclude that for a node of degree k, the node is part of (k2)=k(k1)/2 connected triplets. Therefore the total number of connected triplets is the sum of this formula for all nodes: iki(ki1)/2. One can also define the same node-wise. For node i, the local clustering coefficient Ci is defined as Ci=#ofconnectedtriplescenteredatnodei#oftrianglesatnodei=ki(ki1)jkAjjAjAk Ci=#ofconnectedtriplescenteredatnodei#oftrianglesatnodei=ki(ki1)j,kAijAjkAki Clustering Coefficient of an Almost Complete Graph ofl point (graded) A complete graph is an undirected graph on n nodes such that every "node is connected to every other node. Say remove an edge from a complete graph on n nodes. What is the new clustering coefficient? Assume that n3