Triadic closure

One measure for the presence of triadic closure is clustering coefficient, as follows:

Let ${\displaystyle G=(V,E)}$ be an undirected simple graph (i.e., a graph having no self-loops or multiple edges) with V the set of vertices and E the set of edges. Also, let ${\displaystyle N=|V|}$ and ${\displaystyle M=|E|}$ denote the number of vertices and edges in G, respectively, and let ${\displaystyle d_{i}}$ be the degree of vertex i.

We can define a triangle among the triple of vertices ${\displaystyle i}$, ${\displaystyle j}$, and ${\displaystyle k}$ to be a set with the following three edges: {(i,j), (j,k), (i,k)}.

We can also define the number of triangles that vertex ${\displaystyle i}$ is involved in as ${\displaystyle \delta (i)}$ and, as each triangle is counted three times, we can express the number of triangles in G as ${\displaystyle \delta (G)={\frac {1}{3}}\sum _{i\in V}\ \delta (i)}$.

Assuming that triadic closure holds, only two strong edges are required for a triple to form. Thus, the number of theoretical triples that should be present under the triadic closure hypothesis for a vertex ${\displaystyle i}$ is ${\displaystyle \tau (i)={\binom {d_{i}}{2}}}$, assuming ${\displaystyle d_{i}\geq 2}$. We can express ${\displaystyle \tau (G)={\frac {1}{3}}\sum _{i\in V}\ \tau (i)}$.

Now, for a vertex ${\displaystyle i}$ with ${\displaystyle d_{i}\geq 2}$, the clustering coefficient ${\displaystyle c(i)}$ of vertex ${\displaystyle i}$ is the fraction of triples for vertex ${\displaystyle i}$ that are closed, and can be measured as ${\displaystyle {\frac {\delta (i)}{\tau (i)}}}$. Thus, the clustering coefficient ${\displaystyle C(G)}$ of graph ${\displaystyle G}$ is given by ${\displaystyle C(G)={\frac {1}{N_{2}}}\sum _{i\in V,d_{i}\geq 2}c(i)}$, where ${\displaystyle N_{2}}$ is the number of nodes with degree at least 2.

Another measure for the presence of triadic closure is transitivity, defined as ${\displaystyle T(G)={\frac {3\delta (G)}{\tau (G)}}}$.