聚集系数

局部聚集系数

“我的两个朋友之间是否也是朋友？”这个问题用聚集系数（clustering coefficient）来量化。

例：节点 $i$ 有 4 个邻居，邻居之间有 3 条边，则 $C_i = 2\times 3/(4\times 3) = 0.5$。等价地说，$e_i$ 就是包含节点 $i$ 的三角形个数，矩阵写法为 $e_i=(A^3)_{ii}/2$（从 $i$ 出发走 3 步回到 $i$ 的途径，每个三角形按两个方向各计一次）。全网三角形个数为 $\operatorname{tr}(A^3)/6$。

网络层面的两种定义

• 平均聚集系数：$C = \frac{1}{N}\sum_i C_i$（Watts–Strogatz 的定义）；
• 传递性（transitivity，也称全局聚集系数）：$T = \dfrac{3 \times \text{三角形个数}}{\text{连通三元组个数}}$，其中“连通三元组”指以某节点为中心、两条边构成的“开口路径”，个数为 $\sum_i k_i(k_i-1)/2$。

两者通常数值接近但并不相等：平均聚集系数中每个节点权重相同，低度节点（$C_i$ 容易很高）影响较大；传递性相当于按 $k_i(k_i-1)$ 加权，高度节点影响较大。空手道网络的 $C\approx0.57$，而 $T\approx0.26$，相差一倍以上。写论文时要说明用的是哪一种。（Barabási《Network Science》第 2 章进阶专题 2.A 专门讨论了两者的差别。）

聚集系数与度的关系

在许多真实网络中，$C(k)$（度为 $k$ 的节点的平均聚集系数）随 $k$ 增大而下降，近似 $C(k)\sim k^{-1}$：低度节点处于紧密的小团体中，枢纽则连接着许多彼此不相连的团体。这种模式被认为是层次模块化结构的信号（见社团结构与社区发现）。ER 网络中 $C(k)=p$ 与 $k$ 无关，可作对照。