Triangle Density and Clustering Coefficient The triangle density of a graph is the ratio of number of triangles in the graph to the number of possible triangles:

triangle density $$# of triangles $/([$ n; $3])$

Triangle density is not an appropriate metric to measure clustering for several reasons. First, it does not take into account that the graph could have several connected components, in which case the denominator might be much larger than the numerator. Second, even in the case of a connected graph any three nodes need not be present in the same cluster $($the shortest path lengths connecting them may be much larger$).$ A better metric for clustering is the clustering coefficient, denoted C$,$ which measures the ratio of triangles in the network to the number of connected triples:

C$=$# of closed triplets $/$# of closed and open triplets $=3$# of triangles $/$# of connected triples $.$

where an open triplet is three nodes connected by two edges, and a closed triplet is three nodes connected by three edges. This can be written in terms of the adjacency matrix as

C$=\_$i$,$ j$,$ k A$\_$i j A$\_$j k A$\_$k i$/\_$i k$\_$i$($k$\_$i$-1)$

where k$\_$i$=\_$j A$\_$i j is the degree of node i$.$ To understand this formula, first consider the numerator. Note that $\_$i$,$ j$,$ k A$\_$i j A$\_$j k A$\_$k i$=\_$i$[$A$^3]\_$i i$=$tr A$^3,$ that is$,$ the trace of A$^3.$ We know that $[$A$^3]\_$i i 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 A$^3$ 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 $([$ k; $2])=$k$($k$-1)/2$ connected triplets. Therefore the total number of connected triplets is the sum of this formula for all nodes: $\_$i k$\_$i$($k$\_$i$-1)/2.$ One can also define the same node$-$wise. For node i$,$ the local clustering coefficient C$\_$i is defined as

C$\_$i $=$# of triangles at node i$/$# of connected triples centered at node i

$=\_$j$,$ k A$\_$i j A$\_$j k A$\_$k i$/$k$\_$i$($k$\_$i$-1)$

Clustering Coefficient of an Almost Complete Graph $0/1$ punto $($calificado$)$ A complete graph is an undirected graph on n nodes such that every node is connected to every other node. Say you remove an edge from a complete graph on n nodes. What is the new clustering coefficient? Assume that n $>=3.$