Network Science & Graph Analytics
Watts-Strogatz Clustering & Friendship Paradox Formula
Calculate Watts-Strogatz (1998) node local clustering 2*T_i / (k_i*(k_i - 1)) and prove Scott Feld’s (1991) Friendship Paradox <k_nn> = SUMPRODUCT(k, k) / SUM(k) >= AVERAGE(k).
Measure small-world cliquishness AND prove why your friends have more friends than you do!
Two foundational formulas govern social, epidemiological, and citation graphs of node degrees k_i and closed triangles T_i. First, Duncan Watts and Steven Strogatz (1998) defined Local Clustering Coefficient C_i = IF(k_i < 2, 0, (2 * T_i) / (k_i * (k_i - 1))) — the fraction of a node’s k_i*(k_i - 1)/2 neighbor pairs that are directly connected to each other — and Mean Network Clustering C_bar = AVERAGE(C_1:C_N)! Second, sociologist Scott Feld (1991) proved the Friendship Paradox: while the average person has <k> = AVERAGE(k) friends, the average FRIEND (sampling edge-endpoints proportionally to k_i) has <k_nn> = SUMPRODUCT(k, k) / SUM(k) = <k> + VAR_P(k) / <k> >= <k> friends — strictly GREATER whenever degree variance is positive!
Verify on an exact 5-node graph with edges {(1,2), (1,3), (1,4), (1,5), (2,3)}: Degrees B2:B6 = [4, 2, 2, 1, 1] and Closed Triangles C2:C6 = [1, 1, 1, 0, 0]. Local Clustering D2:D6 = [2/12, 1, 1, 0, 0] -> Mean Network Clustering C_bar = (1/6 + 2) / 5 = 13 / 30 = 0.4333; Mean Node Degree is <k> = 10 / 5 = 2.0000 friends, whereas Mean Friend’s Degree is <k_nn> = (16 + 4 + 4 + 1 + 1) / 10 = 2.6000 friends (+0.6000 = VAR_P([4,2,2,1,1]) / 2.00 = 1.20 / 2.00 — explaining why vaccinating random "nominated friends" reaches high-degree hubs automatically!)!
| Graph Metric (5 Nodes, Degrees [4, 2, 2, 1, 1], 1 Triangle) | Formula | Verified Output |
|---|---|---|
| Hub Node_1 Local Clustering (k=4, T=1) | (2 * 1) / (4 * 3) | 0.1667 |
| Watts-Strogatz Mean Clustering (C_bar) | AVERAGE(D2:D6) | 0.4333 (13 / 30) |
| Average Individual Degree (<k>) | AVERAGE(B2:B6) | 2.0000 friends |
| Average Friend’s Degree (<k_nn>) | SUMPRODUCT(B2:B6, B2:B6) / SUM(B2:B6) | 2.6000 friends (+30% Paradox!) |
Row-Level Watts-Strogatz Local Clustering Coefficient Formula
Guard degree k_i < 2 (0 neighbor pairs -> clustering 0) and impossible triangle counts 2 * T_i > k_i * (k_i - 1).
=IF(B2 < 0, "Invalid Graph Input", IF(B2 < 2, 0, IF(2 * C2 > B2 * (B2 - 1), "Impossible Triangle Count", ROUND((2 * C2) / (B2 * (B2 - 1)), 6))))Feld Friendship Paradox Mean Neighbor Degree <k_nn> Formula
Test a regular cycle graph B2:B6 = [2, 2, 2, 2, 2]: VAR_P(k) = 0, so <k_nn> = 2.0000 = <k> and the Friendship Paradox gap vanishes to 0.0000!
=IF(OR(MIN(B2:B6) < 0, SUM(B2:B6) <= 0), "Invalid Graph Input", ROUND(SUMPRODUCT(B2:B6, B2:B6) / SUM(B2:B6), 4))Try the example
Use the original values or change them to test your understanding.