聚类系数

聚类系数（clustering coefficient）衡量一个顶点的邻居之间有多少联系已经闭合。无向简单图中，它是邻居间实际边数与可能边数之比，等价于通过该顶点的三角形数相对于可能三角形数的比例。

设 $a, b, c$ 构成一个三角形，另有悬挂顶点 $d$ 只与 $a$ 相连。 $a$ 有三个邻居 $b, c, d$ ，三对可能邻居边中只有 $b c$ 存在，所以局部聚类系数为 $1 / 3$ 。 $b, c$ 各自两个邻居互相相连，局部系数均为一。

顶点a的三个邻居bcd中，bc为实边，bd和cd为虚线表示缺边 — 分母数三对邻居，不把 a 自己的三条邻边也算进邻居内部边。

局部闭合与两种全图汇总

对有限无向简单图，记顶点 $v$ 的度为 $k_{v}$ ，邻居诱导子图中的边数为 $T_{v}$ ，也就是包含 $v$ 的三角形数。定义 $C_{v} = \frac{T_{v}}{(\binom{k_{v}}{2})} = \frac{2 T_{v}}{k_{v} (k_{v} - 1)} (k_{v} \geq 2) .$ 对 $k_{v} < 2$ 本文约定 $C_{v} = 0$ 。每对邻居最多有一条边，所以 $0 \leq C_{v} \leq 1$ ；度至少二时，等于一恰表示邻居构成完全图。^[1]

对非空图，平均局部聚类为 $\overline{C} = | V |^{- 1} \sum_{v} C_{v}$ ，这里包含低度顶点的零值。另一指标是全局传递性 $C_{t r} = \frac{3 T}{\sum_{v} (\binom{k_{v}}{2})},$ 其中 $T$ 为全图三角形数，分母为有指定中心的两边链数量；分母为零时本文记零。一个三角形在其三个顶点各贡献一个闭合的两边链，所以分子是 $3 T$ ，不是 $T$ 。

分母为正时，两种汇总的关系可完整推出：由于 $(\binom{k_{v}}{2}) C_{v} = T_{v}$ （低度时两边都为零），且 $\sum_{v} T_{v} = 3 T$ ，有 $C_{t r} = \frac{\sum_{v} (\binom{k_{v}}{2}) C_{v}}{\sum_{v} (\binom{k_{v}}{2})} .$ 因此传递性是按潜在邻居对数加权的局部平均，通常不等于每个顶点权重相同的 $\overline{C}$ 。

主例局部值为 $1 / 3, 1, 1, 0$ ，所以平均为 $7 / 12$ 。分母两边链数为 $3 + 1 + 1 + 0 = 5$ ，一个三角形给出传递性 $3 / 5$ 。若汇总时只纳入度至少二的顶点，平均又会变为 $7 / 9$ ；分母约定必须同时报告。

增加一条边的变式

给主例加上边 $b d$ ，新三角形为 $a b d$ 。此时 $a, b$ 度均为三，各在两个三角形中，局部值为 $2 / 3$ ； $c, d$ 度均为二，各在一个三角形中，局部值为一。平均变为 $5 / 6$ ，传递性为 $6 / (3 + 3 + 1 + 1) = 3 / 4$ 。这可以通过逐个列邻居对复核。

加边也可能使某个局部系数下降：在孤立三角形的一个顶点上接一片新叶子，该顶点从 $C = 1$ 变成主例的 $1 / 3$ ，因为新增邻居对尚未闭合。度数增加与聚类增加不是同一件事。任意星图中心无论有多少叶子，邻居间都没有边，局部值始终为零。

本篇不将自环、平行边、有向边或边权代入同一分母。加权聚类存在不同定义，有的使用三条边权的几何平均，有的以强度作归一化；它们回答的问题不同。非负简单图的局部闭合也不自动证明真实群体关系由三角互相促进，观测和生成机制仍需分别分析。

参考资料

↑ NetworkX 官方文档：clustering，无权局部定义、低度顶点约定及加权/有向推广的区别。访问日期：2026-10-25。

[1] NetworkX 官方文档：clustering，无权局部定义、低度顶点约定及加权/有向推广的区别。访问日期：2026-10-25。

[1]