Skip to main content

Triadic Closure

Module 5: Complex Networks

NoteReading
  • Compulsory: Holme and Kim (2002) for the original model (preferential attachment with triadic closure), and Newman (2003), Section 3.2, for the definitions of the clustering coefficient. For the maximum-likelihood fit of the tail exponent used below, see Eq. (3.7) of Clauset et al. (2009).

The three models of Comparing Graph Models each reproduce one feature of real networks and miss another. The summary is

Network \(L\) \(C\) \(p(k)\)
Real networks small high heavy tail
Erdős-Rényi \(\sim \log N\) ✓ low ✗ Poisson ✗
Watts-Strogatz small ✓ high ✓ narrow ✗
Barabási-Albert very small ✓ low ✗ \(k^{-3}\) ✓

One more ingredient closes the gap: triadic closure, the social rule “a friend of my friend becomes my friend”. The model that adds it to preferential attachment is due to Holme and Kim (Holme and Kim 2002).

The model

The network grows as in the Barabási-Albert model: at each step a new node arrives with \(m\) edges.

  1. The first edge attaches by preferential attachment, to node \(i\) with probability \(\Pi_i = k_i / \sum_j k_j\). Call its target \(w\).
  2. For each of the other \(m-1\) edges, with probability \(p_t\) perform a triad formation step: connect the new node to a random neighbour of \(w\), which closes a triangle \(\text{new} - w - \text{neighbour}\). Otherwise attach by preferential attachment.

The triad probability is often written \(p\); we write \(p_t\) here to keep \(p\) for the edge probability of the random graph. At \(p_t = 0\) the model is the Barabási-Albert model, and for \(m = 1\) there is no second edge, so no triangle can ever be created. NetworkX implements the model as nx.powerlaw_cluster_graph(n, m, p). Its documentation points out one detail: if every neighbour of \(w\) is already linked to the new node, the step falls back to preferential attachment.

Clustering is tunable

Figure 1 varies \(p_t\) at fixed size.

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from scipy.sparse.csgraph import shortest_path

SEED = 7


def avg_path_length(G, n_src=300, seed=0):
    """Average distance in the largest component, from at most n_src random sources."""
    H = G.subgraph(max(nx.connected_components(G), key=len))
    nodes = list(H)
    A = nx.to_scipy_sparse_array(H, nodelist=nodes, format="csr")
    # SciPy's csgraph routines require int32 CSR index buffers in this environment.
    A.indices = A.indices.astype(np.int32)
    A.indptr = A.indptr.astype(np.int32)
    n = len(nodes)
    rng = np.random.default_rng(seed)
    src = np.arange(n, dtype=np.int32) if n <= n_src else rng.choice(n, n_src, replace=False).astype(np.int32)
    return shortest_path(A, unweighted=True, indices=src).sum() / (len(src) * (n - 1))


pts = np.linspace(0, 1, 6)
C_pt, L_pt = [], []
for pt in pts:
    graphs = [nx.powerlaw_cluster_graph(2000, 3, pt, seed=SEED + r) for r in range(4)]
    C_pt.append(np.mean([nx.average_clustering(G) for G in graphs]))
    L_pt.append(np.mean([avg_path_length(G) for G in graphs]))

fig, ax = plt.subplots(figsize=(6, 3.8))
ax.plot(pts, C_pt, "o-", label="C")
ax.set_xlabel(r"triad probability $p_t$")
ax.set_ylabel("C")
ax2 = ax.twinx()
ax2.plot(pts, L_pt, "s--", color="C1", label="L")
ax2.set_ylabel("L")
ax2.set_ylim(0, 6)
fig.legend(loc="upper left", bbox_to_anchor=(0.12, 0.88))
plt.tight_layout()
plt.show()
print("p_t:", np.round(pts, 2))
print("C  :", np.round(C_pt, 3))
print("L  :", np.round(L_pt, 2))
Figure 1: Average clustering coefficient and average path length of the Holme-Kim graph (N = 2000, m = 3) as a function of the triad probability p_t, averaged over 4 graphs. The value at p_t = 0 is the Barabási-Albert graph. Clustering grows roughly linearly with p_t while the path length changes by less than 20%.
p_t: [0.  0.2 0.4 0.6 0.8 1. ]
C  : [0.019 0.121 0.231 0.339 0.457 0.594]
L  : [3.74 3.74 3.72 3.79 3.95 4.42]

The maximum clustering for \(m = 3\) is about 0.6, not 1. Only the edges after the first can close triangles, so at birth a new node with \(m\) edges has about \(m - 1\) closed pairs among its \(m(m-1)/2\) neighbour pairs, a local clustering of about \(2/m\) (0.67 for \(m = 3\)). This sets a ceiling well below 1. In other words the clustering is “finite”: it does not decay with \(N\), as the clustering figure in Scaling of Path Length and Clustering shows.

The degree distribution is still scale-free

The additional step changes who is connected to the new node but not the rich-get-richer mechanism, so the tail should stay a power law with exponent close to 3. Figure 2 compares the complementary cumulative distribution \(P(K \ge k)\) of the Barabási-Albert and the Holme-Kim graphs. For \(p(k) \sim k^{-\gamma}\) this distribution decays like \(k^{-(\gamma - 1)}\), so a slope of \(-2\) corresponds to \(\gamma = 3\). The exponent is estimated with the maximum-likelihood formula for discrete data, \(\hat\gamma \simeq 1 + n \big[\sum_{i} \ln \big(k_i / (k_{\min} - \tfrac12)\big)\big]^{-1}\), applied to the \(n\) nodes with \(k_i \ge k_{\min}\) (Clauset et al. 2009, Eq. 3.7).

def gamma_mle(deg, kmin):
    x = deg[deg >= kmin]
    return 1 + len(x) / np.sum(np.log(x / (kmin - 0.5)))


graphs = {
    "BA": nx.barabasi_albert_graph(50_000, 3, seed=1),
    "HK, p_t = 0.5": nx.powerlaw_cluster_graph(50_000, 3, 0.5, seed=1),
    "HK, p_t = 1": nx.powerlaw_cluster_graph(50_000, 3, 1.0, seed=1),
}
fig, ax = plt.subplots(figsize=(6, 4))
for name, G in graphs.items():
    deg = np.array([d for _, d in G.degree()])
    ks = np.arange(3, deg.max() + 1)
    ccdf = np.array([(deg >= k).mean() for k in ks])
    ax.loglog(ks, ccdf, ".", ms=3, label=name)
    print(f"{name:>14}: k_max = {deg.max():5d}, gamma_hat(k_min = 10) = {gamma_mle(deg, 10):.2f}, "
          f"gamma_hat(k_min = 20) = {gamma_mle(deg, 20):.2f}, C = {nx.average_clustering(G):.3f}")
deg_ba = np.array([d for _, d in graphs["BA"].degree()])
ks = np.array([10, 1000])
ax.loglog(ks, (deg_ba >= 10).mean() * (ks / 10.0) ** -2, "k--", lw=1, label=r"slope $-2$")
ax.set_xlabel("k")
ax.set_ylabel(r"$P(K \geq k)$")
ax.legend()
plt.tight_layout()
plt.show()
            BA: k_max =   506, gamma_hat(k_min = 10) = 2.86, gamma_hat(k_min = 20) = 2.91, C = 0.001
 HK, p_t = 0.5: k_max =  1622, gamma_hat(k_min = 10) = 2.81, gamma_hat(k_min = 20) = 2.81, C = 0.268
   HK, p_t = 1: k_max =  2371, gamma_hat(k_min = 10) = 2.85, gamma_hat(k_min = 20) = 2.83, C = 0.590
Figure 2: Complementary cumulative degree distribution P(K >= k) of a Barabási-Albert graph and of Holme-Kim graphs with p_t = 0.5 and 1 (N = 50000, m = 3), on logarithmic axes. The dashed line has slope -2, which corresponds to p(k) ~ k^-3.

The estimates are between 2.8 and 2.9 for all three graphs. They are below 3 because the formula is an approximation and because the finite sample and the discrete lower cutoff \(k \ge m\) bias the estimate. The plain Barabási-Albert graph gives the same value, so the triad step does not change the exponent in a detectable way. For the Barabási-Albert model, Barabasi and Albert (1999) report a simulated exponent of \(2.9 \pm 0.1\) against the analytical value 3, which is consistent with these estimates.

The completed comparison

Table 1 puts numbers in the summary table. All model graphs have \(N = 5000\) and mean degree 6. The two real networks are the ones used in Practice: Real Networks and Practice: Flights and Other Networks; they are small and, in the flights case, not connected, so \(L\) is computed on the largest component.

Table 1: Measured properties of the model graphs (N = 5000, mean degree 6, one graph each) and of two real networks. C_random = /N is the clustering of a random graph with the same N and mean degree. kmax/ measures how far the degree distribution extends beyond its mean.
import gzip

N = 5000
models = {
    "Erdős-Rényi": nx.fast_gnp_random_graph(N, 6 / (N - 1), seed=1),
    "Watts-Strogatz (p = 0.1)": nx.watts_strogatz_graph(N, 6, 0.1, seed=1),
    "Barabási-Albert (m = 3)": nx.barabasi_albert_graph(N, 3, seed=1),
    "Holme-Kim (m = 3, p_t = 0.5)": nx.powerlaw_cluster_graph(N, 3, 0.5, seed=1),
}
enron = nx.Graph(nx.read_edgelist("data/ia-enron-only/ia-enron-only.edges"))
flights = nx.Graph(nx.read_graphml("data/openflights/openflights_usa.graphml.gz"))
rows = {**models, "Enron e-mail (data)": enron, "US flights (data)": flights}

print(f"{'network':<30}{'N':>6}{'<k>':>7}{'L':>6}{'C':>8}{'C/C_random':>12}{'kmax/<k>':>10}")
for name, G in rows.items():
    G.remove_edges_from(nx.selfloop_edges(G))
    k = np.array([d for _, d in G.degree()], dtype=float)
    C = nx.average_clustering(G)
    print(f"{name:<30}{len(G):>6}{k.mean():>7.1f}{avg_path_length(G):>6.2f}{C:>8.3f}{C / (k.mean() / len(G)):>12.1f}{k.max() / k.mean():>10.1f}")
network                            N    <k>     L       C  C/C_random  kmax/<k>
Erdős-Rényi                     5000    6.0  4.98   0.001         0.8       2.7
Watts-Strogatz (p = 0.1)        5000    6.0  7.90   0.445       370.6       1.5
Barabási-Albert (m = 3)         5000    6.0  4.10   0.009         7.2      27.2
Holme-Kim (m = 3, p_t = 0.5)    5000    6.0  4.11   0.271       225.9      63.9
Enron e-mail (data)              143    8.7  2.97   0.434         7.1       4.8
US flights (data)                546   10.2  3.22   0.493        26.4      15.0

Only the Holme-Kim row has all three properties of the real rows at once: short paths, an absolute clustering of the same order as the real values (0.27 against 0.43 and 0.49) and a degree distribution that extends far beyond its mean. The ratio \(C/C_{\text{random}}\) alone is misleading, because \(C_{\text{random}}\) depends on \(N\): the plain Barabási-Albert graph has a ratio of 7, like the Enron network, but its clustering of 0.009 is not high in absolute terms. Two reservations apply. First, the conclusion is that these are only three features: degree assortativity, community structure and edge dynamics are not reproduced. The real networks of this table have negative degree correlations (flights) or none (Enron), a feature that none of the four models is built to produce. Second, a clustering far above \(C_{\text{random}}\) is partly a consequence of the degree heterogeneity; the next page quantifies how much with a null model that keeps the degrees.

NoteExercise

Generate Holme-Kim graphs with \(N = 2000\) and \(m = 1, 2, 3\) for \(p_t = 1\) and compute their clustering coefficient. Explain the value for \(m = 1\). Is the clustering larger for \(m = 2\) or for \(m = 3\), and why?

for m in (1, 2, 3):
    C = np.mean([nx.average_clustering(nx.powerlaw_cluster_graph(2000, m, 1.0, seed=s)) for s in range(4)])
    print(m, round(C, 3))

For \(m = 1\) each new node has a single edge, so the graph is a tree and has no triangle at all: the clustering is zero. The measured values are 0, about 0.75 for \(m = 2\) and about 0.59 for \(m = 3\), so the clustering decreases with \(m\). For \(p_t = 1\) every edge after the first closes a triangle with the first target \(w\), so a new node of degree \(m\) is joined to \(w\) and to \(m-1\) neighbours of \(w\). Its \(m(m-1)/2\) neighbour pairs contain at least the \(m-1\) pairs \((w, x)\), so its local clustering is at least \(2/m\): 1 for \(m = 2\) and 2/3 for \(m = 3\). Larger \(m\) means more neighbour pairs that triadic closure does not close.

NoteExercise

The Barabási-Albert graph and the Holme-Kim graph with \(p_t = 1\) have almost the same exponent. Compute \(\langle k^2 \rangle / \langle k \rangle\) for both graphs of Figure 2 and use the heterogeneous mean-field threshold \(\lambda_c = \langle k \rangle/\langle k^2 \rangle\) of Epidemic Threshold to compare the predictions for SIS spreading. What does the prediction ignore?

for name, G in graphs.items():
    k = np.array([d for _, d in G.degree()], dtype=float)
    print(name, round(k.mean() / (k**2).mean(), 4))

With \(N = 50000\) the prediction is \(\langle k \rangle/\langle k^2 \rangle \approx 0.048\) for the Barabási-Albert graph, 0.030 for \(p_t = 0.5\) and 0.020 for \(p_t = 1\). The Holme-Kim graphs have a larger \(\langle k^2 \rangle\) (their largest hubs are bigger, see the \(k_{\max}\) printed above), hence a smaller predicted threshold. The mean-field formula uses only \(p(k)\). It assumes that the network is uncorrelated and locally tree-like, so it ignores the triangles that triadic closure adds: edges inside a triangle transmit the infection to nodes that may already be infected. Pastor-Satorras et al. (2015) discuss the effect of short loops on epidemic thresholds.

What’s Next?

Configuration Model shows how to separate the effect of the degree sequence from the effect of clustering.

References

Barabasi, Albert-Laszlo, and Reka Albert. 1999. “Emergence of Scaling in Random Networks.” Science 286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509.
Clauset, Aaron, Cosma Rohilla Shalizi, and M. E. J. Newman. 2009. “Power-Law Distributions in Empirical Data.” SIAM Review 51 (4): 661–703. https://doi.org/10.1137/070710111.
Holme, Petter, and Beom Jun Kim. 2002. “Growing Scale-Free Networks with Tunable Clustering.” Physical Review E 65 (2): 026107. https://arxiv.org/abs/cond-mat/0110452.
Newman, M. E. J. 2003. “The Structure and Function of Complex Networks.” SIAM Review 45 (2): 167–256. https://doi.org/10.1137/S003614450342480.
Pastor-Satorras, Romualdo, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. “Epidemic Processes in Complex Networks.” Reviews of Modern Physics 87 (3): 925–79. https://doi.org/10.1103/RevModPhys.87.925.