A common measure of local network structure in empirical networks is the transitivity (also called the global clustering coefficient), which is defined as the fraction of “potential triangles” which are actually realized as actual triangles in the network. High transitivity in graphs like social networks is suggestive of the idea that your friends tend to be friends with each other.
We think of a “potential triangle” (also called a “wedge”) as “a triangle with one edge missing.” A “wedge node based at \(i\)” is a set of three nodes \(i\), \(j\), and \(k\) such that there is an edge between \(i\) and \(j\), an edge between \(i\) and \(k\), but no edge between \(j\) and \(k\).
We can also talk about triangles based at node \(i\); there are three choices of such a base node for any given triangle. The formula for transitivity that we’ll use to measure the prevalence of triangles in this course is
\[ \begin{aligned} T = \frac{3\times\text{total number of triangles in graph}}{\text{total number of wedges}} = c \frac{\mathrm{trace} \; \mathbf{A}^3}{\sum_{i} k_i (k_i - 1)} \end{aligned} \]
for some undetermined constant \(c\).
- Please state formulas for the total number of all wedges and the total number of triangles in a network. At least one of these formulas may be one you’ve already seen.
- Determine the value of \(c\) such that the formula above for \(T\) is indeed equal to 1 in a network in which all wedges are realized as triangles.
- Explain why we multiply by 3 in the numerator of the formula for \(T\).