图论里有个指标名字听起来平平无奇但只要你在社交网络、推荐系统或者生物网络里动过手就一定会撞上它——聚类系数Clustering coefficient。它回答的是一个特别朴素的问题你认识的人之间互相认识的比例有多高。听着简单可我在实际项目里见过太多人算错或者算对了却用错最后拿一个跟基线毫无可比性的数字去做结论。这篇就按我自己的理解路径来拆先说清楚它在量什么再把公式里每一个分母为什么长成这样推一遍然后手写代码跑两个反直觉的小例子最后聊聊真实场景里的用法和我踩过的坑。适合刚接触图论、需要快速把这个指标用起来的人也适合已经会调networkx但一直没搞明白average_clustering和transitivity为什么结果对不上的朋友。1. 先把直觉钉死聚类系数到底在量什么1.1 从朋友的朋友到三角形计数先忘掉公式。给你一张无向图取其中一个节点 i把它的所有邻居拎出来放在一起。现在问这些邻居之间自己内部连了多少条边如果邻居们互相之间全是熟人形成一个密不透风的小圈子那节点 i 的局部聚类系数就接近 1如果 i 只是一个把两拨互不相干的人串起来的中间人那这个值就接近 0。这个密不透风的小圈子在图论里有正式名字叫三角形。三个节点两两相连就是一个三角形。节点 i 的局部聚类系数本质上就是在数以 i 为顶点之一、能凑出多少个三角形占理论上最多能凑出多少个的比例。这个视角一换很多困惑就没了。所谓聚类不是聚类算法里那个把点分组的意思它衡量的是局部稠密程度是网络在微观尺度上抱团的程度。我在跟业务方解释的时候通常这么说这个数高说明这个网络里信息在小圈子里打转传播靠熟人这个数低说明网络更像一个广播塔结构信息要靠枢纽节点往外散。为什么这个指标值得单独拎出来讲因为它是少数几个不需要跑复杂算法、不需要迭代收敛、单次遍历就能算出来的结构指标之一却又能区分出非常本质的网络形态差异。随机图的聚类系数天然接近边密度而真实社交网络往往比同规模随机图高出几十倍甚至上百倍这个落差本身就是信息。1.2 三个名字相似、结果差十倍的指标这是最容易翻车的地方。很多资料里聚类系数四个字被混用实际上至少有三种不同的东西名称常见英文计算方式特性局部聚类系数local clustering coefficient每个节点算一个值再单独看逐节点的微观指标平均聚类系数average clustering coefficient所有节点的局部值取算术平均对低度节点敏感全局聚类系数global clustering / transitivity三角形总数与连通三元组总数之比被高度节点主导先说局部值。对节点 i记它的度数为 k邻居个数记它的邻居之间实际存在的边数为 e那么C_i 2e / (k * (k - 1))分子里的 2 是因为每条边被数了两次。分母 k(k-1) 是 k 个邻居两两配对的有序数目——为什么用有序对而不是组合数因为这样分子分母的计数口径才能对上2e 也是有序计数的结果。如果你想让公式更直观可以写成等价的组合形式C_i e / C(k, 2)也就是实际边数除以可能的边数。这两个写法完全等价我个人更喜欢后者因为它一眼就能看出这是个实际/理论最大的比值。然后是平均聚类系数就是所有节点局部值的算术平均。注意这里有个细节度为 0 和 1 的节点分母是 0公式没法算。不同库的处理不一样networkx的做法是直接记 0 并且算进平均里这一点后面还会专门讲。最后是全局聚类系数也叫传递性transitivity。它不再逐节点算而是在整张图上数transitivity 3 * 三角形总数 / 连通三元组总数连通三元组指的是长度为 2 的路径也就是形如 a-b-c 且 a、c 不要求相连的结构。每个三角形里包含 3 个连通三元组所以分子乘 3 才能和分母同量纲。1.3 什么时候该用哪一个一张选择表这三个指标不是随便挑的选错了结论会直接反过来。我一般按下面的逻辑选想看节点层面的特征比如给每个用户打一个社团结实度标签喂给模型用局部聚类系数。想刻画整张图的形态且图里度分布比较均匀比如规则网格、小规模实验图平均聚类系数就够了直观好解释。图里有明显的超级枢纽节点度分布极不均匀这时候我几乎总是看全局聚类系数或者两个一起报绝不只看平均值。做小世界性判断标准做法是同时报平均聚类系数和平均最短路径长度再和同规模同边数的随机图对照。注意如果你在论文或报告里只写聚类系数为 0.31这个数字基本没有信息量必须写清楚是 local、average 还是 global以及图的规模、边数、是否去除自环多重边。2. 局部聚类系数公式里的分母比分子更容易出错2.1 从 2e/k(k-1) 手推一遍我见过太多人把这个公式背下来却不知道 2 从哪来。我们真的推一遍用 3 个节点的三角形举例节点 i 有 2 个邻居邻居之间有一条边。k 2e 1代入 2×1/(2×1) 1。正确因为三个节点两两相连这确实是个完美的小圈子。再看一个 4 个节点的例子i 有 3 个邻居 a、b、c边只有 a-b 和 a-c 两条b-c 不相连。k 3e 2C_i 4/(3×2) 2/3 ≈ 0.667。直觉验证一下3 个邻居之间理论上有 3 对可能相连ab、ac、bc实际连了 2 对比例就是 2/3对上了。再换个角度用三角形数量来表示会更方便写代码。设 T_i 为包含节点 i 的三角形个数那么 T_i 恰好等于 e也就是邻居之间的边数——因为每一对相连的邻居加上 i 本身就构成一个三角形。所以C_i 2 * T_i / (k_i * (k_i - 1))这个形式在工程上特别好用因为三角形个数是可以在一次遍历里顺带算出来的你不需要为每个节点单独做邻居两两检查。2.2 度为 0 和 1 的节点为什么必须单独讨论k 0 的孤立节点压根没有邻居k 1 的叶子节点只有一个邻居一个人凑不出任何一对。这两种情况下分母为 0公式无定义。数学上通常约定 C_i 0但这会带来一个副作用平均聚类系数会被大量叶子节点稀释。举个真实的场景。电商的用户-商品二部图投影成用户-用户图之后会出现大量度只有 1 到 2 的用户社交平台的长期沉默账号也是这样。如果你把所有这些节点按 0 计入平均得到的数字会低得离谱然后你可能会得出这个社区很松散的错误结论——而实际情况是那些活跃用户的圈子密得像铁桶。我的处理习惯是报平均聚类系数时同时报一份仅统计度 ≥ 2 节点的结果两个数字一起给。如果两者差别在 10% 以内说明叶子节点不构成主要影响如果差出好几倍那就要在结论里明确说明这个口径问题因为不同口径下这两个数可能支撑完全相反的判断。还有一个隐蔽的坑某些库在计算平均值时会自动跳过未定义节点某些库会补 0。同一个数据集换一个库平均聚类系数能从 0.4 掉到 0.08。这不是数据的问题是口径的问题。所以我在代码里从来不直接用库的average_clustering而是自己取字典求平均顺便控制要不要过滤低度节点。2.3 有向图的四种三角形与 Fagiolo 口径无向图里三角形只有一种形态有向图里就热闹了。3 个节点之间有向三角形按边的方向可以分成四类循环型a→b→c→a、中间人型a→b→c 且 a→c也就是 b 是中间人、入型、出型。很多文献会给每一类单独定义一个聚类系数再取平均作为总的。如果你的图确实有方向性含义——关注关系、转账流水、邮件往来、调用依赖——直接把方向砍掉再算无向聚类系数会丢掉关键信息。举个极端例子一个纯粹的下级向上级汇报的树状结构砍掉方向以后变成一张无向树聚类系数必然是 0但这个0其实什么也没说因为树本来就没有三角形。2.4 加权图Onnela 的几何平均与 Barrat 的算术平均边权重的引入会带来一个更麻烦的问题权重到底应该怎么进入公式常见的有两条路线结果和解释都不一样。第一条是Onnela 路线用几何平均也就是把三条边的归一化权重相乘再开三次方C_i^w 1 / (k_i(k_i-1)) * Σ_{j,h} (ŵ_ij * ŵ_ih * ŵ_jh)^(1/3)这里的 ŵ 是权重除以全图最大权重做的归一化。这个形式的物理含义很清楚一个三角形只要有一条边的权重接近 0整个乘积就接近 0也就是断了一条边的三角形不算数。它强调的是闭合强度。第二条是Barrat 路线用算术平均把节点 i 与两条边的平均权重作为三角形的权重。这个形式更关注节点的重要性一个和所有人都强连接的节点会拿到很高的值。两者在加权社交网络上的结果经常差别很大尤其是在权重分布偏斜的时候。我的经验是做链路预测或推荐用 Onnela因为它对弱边的惩罚符合直觉做中心性相关的排序用 Barrat因为它能突出枢纽节点。选之前先想清楚你要回答的问题是什么别看哪个公式顺眼就用哪个。提示networkx的nx.clustering(G, weightweight)实现的是 Onnela 那一套并且内部会把权重按最大值归一化。如果你自己已经做过归一化就没必要再依赖它这一步直接手写更可控。3. 两个图算给你看平均值和全局值到底能差多少3.1 例子一K10 挂 90 个叶子全局值远大于平均值光说会被枢纽节点主导太抽象我们算一个。构造一张图一个 10 个节点的完全图K10然后用 90 个叶子节点平均挂到这 10 个节点上每个挂 9 个。总节点数 100总边数 45 90 135。先算全局聚类系数。每个 K10 节点的度数是 9圈内 9叶子 18以它为中心能形成的连通三元组是 C(18, 2) 15310 个节点合计 1530 个三元组。三角形只有 K10 内部的 C(10, 3) 120 个闭合三元组 360 个。所以 transitivity 360 / 1530 ≈0.235。再算平均局部聚类系数。K10 节点参与的三角形数是 C(9, 2) 36所以 C_i 2×36 / (18×17) 72/306 ≈ 0.235。90 个叶子节点全是 0。平均值 (10 × 0.235) / 100 ≈0.0235。两个数字差了整整10 倍。全局值告诉你网络上确实存在一个很紧密的核心圈子平均值告诉你平均每个节点处在很松散的位置两个说法都对取决于你想问什么。3.2 例子二三角星形桥接平均值反超全局值反过来再造一个例子。一个三角形节点 t1、t2、t3一个星形中心 c10 个叶子再用一条边把 t1 和 c 连起来让图保持连通。总节点 14总边 3 10 1 11。局部值t2 和 t3 的邻居都是另外两个三角形节点互相相连C 1t1 的邻居是 t2、t3、c其中只有 t2-t3 是边C 2×1/(3×2) 1/3c 和 10 个叶子都是 0。平均值 (1 1 1/3) / 14 ≈0.167。连通三元组t2 处 1 个t3 处 1 个t1 处 C(3,2) 3 个c 处 C(11,2) 55 个叶子 0合计 60 个。三角形只有 1 个闭合三元组 3 个。transitivity 3/60 0.05。这次反过来了平均值0.167是全局值0.05的三倍多。原因是那个星形中心 c 一个人贡献了 55 个不闭合的三元组把全局值狠狠地拉了下来但它在平均值里只占 1/14 的权重。3.3 从这两个例子提炼出的判断规则把两个例子摆在一起规律就很清楚了场景特征平均值 vs 全局值典型结构存在少数超高度节点且它们本身处于稠密核心全局 平均核心-边缘结构存在少数超高度节点但它们只是广播枢纽平均 全局星形、二部图投影度分布均匀图规模不大两者接近规则图、小规模实验图我自己的习惯是永远两个都算然后比较它们的比值。这个比值本身就携带信息。比值接近 1说明聚类在所有节点上分布均匀比值远大于 1说明高的那部分是被少数低度节点的紧密小圈子撑起来的比值远小于 1说明枢纽节点数量多但彼此之间不闭合网络以广播为主要传播模式。这个经验是我在分析一批社区数据时总结出来的比单独看任何一个数字都有用。3.4 随机图基线p 值和度保持零模型绝对数值本身几乎没有意义必须有基线。最简单的基线是 Erdős–Rényi 随机图如果每个节点对以概率 p 独立连边那么任意三个节点构成三角形的概率是 p³而局部聚类系数的期望恰好等于 p因为邻居之间的边也是以概率 p 独立存在的。所以边密度是多少随机图的聚类系数就大概是多少。但 ER 基线太粗了。真实网络的度分布是重尾的你再拿一个均匀度分布的随机图去对照等于拿苹果比橘子。更靠谱的做法是用度保持零模型生成一个和原图度数序列完全相同、但边随机重连的图算它的聚类系数作为基线。这样做出来的对照才能说明多余的三角形是结构性的还是度分布带来的必然结果。networkx里可以用配置模型生成近似图先nx.configuration_model(degree_sequence)然后去掉自环和平行边再做一次双重边交换nx.double_edge_swap来采样。这个过程要做几十次取平均才能得到一个稳定的基线值。听起来麻烦但这是区分真结构和统计噪声的唯一办法。4. 代码落地networkx 的快捷路径和手写实现4.1 networkx 里那几个容易混的 API先把几个常用接口的区别说清楚这几个名字看着像行为完全不同import networkx as nx G nx.karate_club_graph() local nx.clustering(G) # dict: 节点 - 局部聚类系数 avg nx.average_clustering(G) # 所有节点局部值的算术平均低度节点记 0 glob nx.transitivity(G) # 全局聚类系数传递性 tri nx.triangles(G) # dict: 节点 - 参与的三角形个数几个必须知道的细节nx.average_clustering的默认口径是包含所有节点度小于 2 的记为 0。想要另一种口径只能自己算。nx.transitivity和nx.average_clustering在大多数真实网络上的结果不一样通常差 2 到 10 倍这是正常的不是 bug。遇到有向图时nx.clustering的处理方式在不同版本上有差异有的版本内部会转成无向图再算。我的做法是永远先显式G.to_undirected()把口径钉死不依赖库的默认行为。nx.triangles返回的是每个节点参与的三角形个数sum(tri.values())等于三角形总数的 3 倍每个三角形被它的三个顶点各数一次。这个恒等式可以用来做交叉验证。4.2 用三角形计数反推局部聚类系数既然 C_i 2 T_i / (k_i (k_i - 1))那你完全不需要为每个节点单独算局部聚类系数数一遍三角形就够了def local_from_triangles(G): tri nx.triangles(G) res {} for v in G: k G.degree(v) if k 2: res[v] 0.0 else: res[v] 2.0 * tri[v] / (k * (k - 1)) return res这么写有两个好处。第一三角形计数是局部聚类系数里最贵的那一步复用它可以把总耗时压下来。第二当你需要同时报局部值、平均值和全局值时只需数一次三角形即可代码路径统一口径也就统一了。4.3 手写一遍邻接集合交集法自己写一遍的价值在于你才真正知道库帮你做了哪些清理工作。下面是我平时用来做交叉验证的实现输入是邻接表字典套集合def clustering_manual(adj): adj: dict, 节点 - set(邻居) 返回: (局部聚类系数字典, 平均聚类系数, 全局聚类系数) tri counting_triangles(adj) local {} triples 0 for v, nbrs in adj.items(): k len(nbrs) if k 2: local[v] 0.0 else: local[v] 2.0 * tri[v] / (k * (k - 1)) triples k * (k - 1) // 2 # C(k,2) avg sum(local.values()) / len(local) total_tri sum(tri.values()) / 3.0 glob 3.0 * total_tri / triples if triples else 0.0 return local, avg, glob注意triples累加的是 C(k, 2)这就是连通三元组的总数sum(tri.values()) / 3.0得到三角形总数。这两个量对上全局聚类系数就出来了。整段代码里最贵的部分是数三角形其他都是线性扫描。4.4 大规模图上的前向剪枝与近似采样百万级节点上直接做邻居交集会炸。核心优化思路是按度排序做定向剪枝给每个节点一个秩按度数从小到大只在每条边的低秩指向高秩方向上做搜索。这样每个三角形只会被枚举一次总复杂度能压到接近 O(m^1.5)在稀疏图上表现很好。def counting_triangles(adj): rank {v: i for i, v in enumerate(sorted(adj, keylambda x: len(adj[x])))} tri {v: 0 for v in adj} for u in adj: ru rank[u] for v in adj[u]: if ru rank[v]: continue # 只走低秩 - 高秩方向 rv rank[v] for w in adj[v]: if rv rank[w] and w in adj[u]: tri[u] 1 tri[v] 1 tri[w] 1 return tri如果图还要大几十亿条边级别就得考虑近似方法了。楔形采样是比较好落地的方案随机抽一批长度为 2 的路径楔形统计其中能闭合成三角形的比例就是聚类系数的无偏估计。给 10 万到 100 万个样本就能把误差控制在 1% 以内比全量计算快好几个数量级。4.5 稀疏矩阵路线的适用边界如果图比较稠密或者你已经在用 SciPy另一条路是把邻接矩阵拿出来做乘法。三角形总数等于 trace(A³)/6用稀疏矩阵乘一次就能算出来import numpy as np from scipy import sparse A nx.to_scipy_sparse_array(G, formatcsr, dtypenp.float64) A3 A A A total_tri A3.diagonal().sum() / 6.0这条路的边界很清楚边数在中低规模大概十万以内时它很快因为底层是高度优化的数值库一旦图变大AA 会产生大量中间填充内存会直接爆掉。我在十几万节点的图上试过稀疏矩阵乘法产生的中间结果比原矩阵大了将近两个数量级最后只能换成前向剪枝。选择标准很简单节点数少于几千且密度不低用矩阵否则用邻接集合遍历。5. 真实场景里它能干什么五个落地角度5.1 社区结构与社团划分聚类系数和社区结构的关系非常直接一个划分得好的社区内部节点之间的聚类系数应该明显高于跨社区的连接。很多模块度优化算法的初始化步骤里就会用局部聚类系数来给边打分把明显属于同一个三角形里的边先合并降低后续优化的搜索空间。我做过一次社交媒体的话题社群分析用的是聚类系数 模块度双指标验证。单纯看模块度两个划分方案差别不大但一比聚类系数其中一个方案内部出现了大量跨圈连接实际是把两个不同兴趣群体硬拼在一起。这种问题只靠模块度是看不出来的。5.2 链路预测与推荐打分特征链路预测里有个经典指标叫共同邻居数也就是两个节点有多少个共同的邻居。聚类系数正是它的归一化版本——它把共同邻居数除以了理论最大值从而消掉了度数的影响。所以在特征工程里我一般会把两者都放进去共同邻居数是绝对量聚类系数是相对量模型能自己学出哪个更管用。在好友推荐场景里我发现一个实用技巧只看目标用户侧的局部聚类系数还不够要把候选人和目标用户之间的局部聚类系数取一个组合比如最小值或几何平均。因为单纯看一方容易被那种到处加人但圈子很散的账号拉高误召。用最小值之后召回的准确率在我的测试集上有明显改善。5.3 生物与化学网络的结构判别蛋白质互作网络的一个著名特征是聚类系数远高于同规模随机图这被解释为功能模块复合物、通路在结构上的体现。做这类分析时一个常用做法是把聚类系数和度做二维散点天然会看到一个高聚类低度和低聚类高度的双峰结构前者往往是功能模块内部成员后者是连接多个模块的枢纽蛋白。化学分子图里也会用类似指标来判断分子的环化程度。只是要注意分子图节点数很少通常几十个这时候聚类系数的方差很大单个分子的值不要过度解读必须成组比较。5.4 团伙识别与稠密子图异常这个用途比较有意思。在交易网络、设备关联网络里团伙往往表现为高度闭合的子图——几个人互相之间全有往来。全局聚类系数在这里的作用是做整体监控指标如果某个时间窗内的全局聚类系数突然抬升说明网络里正在自发形成密集的小圈子值得深入看。但直接拿全局值做告警会有大量误报因为正常业务高峰期核心用户的互动本来就会增多。我的做法是固定度保持零模型做基线算出一个超额聚类系数也就是实际值除以同度分布零模型的期望值。这个比值比原始值稳定得多。5.5 生成模型与图嵌入的效果校验训练一个图生成模型或者图嵌入模型之后怎么判断它学得像不像只看损失函数不够。一个常用的做法是对比真实图和生成图的一组结构统计量聚类系数分布是其中必选的一项。具体来说不要只比平均值要把逐节点的局部聚类系数按度分桶每一桶比均值这样能发现模型在哪一类节点上学得不好。我用这个方法抓到过一次问题生成模型在低度节点上的聚类系数分布明显偏离真实分布原因是训练目标里没有对二阶结构做约束。这种偏差看平均值完全发现不了因为低度节点在平均值里权重很小。6. 踩过的坑六个我实际遇到过的问题6.1 自环和多重边没清理结果全歪这是我最早踩的坑。从数据库导出的关系表里用户给自己点赞、同一对用户有多次互动都会留下自环和多重边。自环会让度数多算 1直接影响分母多重边会让networkx的度计算和集合操作产生不一致。更麻烦的是不同库对自环的处理规则不一样有的把它算作 1 度有的算作 2 度。我的固定流程是G.remove_edges_from(nx.selfloop_edges(G))然后如果是多重图用nx.Graph(G)压成简单图。这两步一定要在计算任何结构指标之前做而且要作为流水线里不可跳过的一环。6.2 拿不同规模的图直接比绝对值聚类系数和图的规模、边密度强相关。一个 100 节点的图和 100 万节点的图聚类系数放一起比绝对值毫无意义。真要比只能比归一化后的值和同规模同度分布的零模型比或者比 z-score。我见过一份报告把三个不同平台的聚类系数直接列在一起得出平台 A 社区更紧密的结论而这三个平台的数据规模差了两个数量级。这种结论是不可靠的。6.3 采样不完整带来的系统性低估从完整网络里随机采一批节点出来算聚类系数结果一定偏低。原因是采样会切断边本来存在的三角形被拆掉了。而且这个偏差不是随机的度数越低的节点受影响越大——因为它们的三角形本来就不多被切掉一个就归零了。修正的办法有几个一是用边采样而不是节点采样并且保留被采样边的两端节点二是在解释时明确说明这是下界三是用肠镜式采样先采一批种子节点再补充它们的邻居来减少边界效应。实话说如果采样率低于 20%修正效果都不太理想数量级的偏差很难完全消除。6.4 加权口径的归一化方向搞反加权聚类系数里那个归一化到底是除以最大权重还是最小权重很多人写代码时不注意就弄反了。除以最大值结果落在 [0, 1]符合系数的直觉除以最小值结果会大于 1完全没法解释。还有一个更隐蔽的坑Onnela 的公式在权重为 0 时会出现 0^(1/3) 的情况但 0^(1/3) 是 0 不是未定义所以逻辑上没问题。真正麻烦的是负权重——如果边权重表示相关性可能取负值开三次方在数学上依然成立但物理含义完全崩了。这种情况下要么先把权重平移成正数要么换用 Barrat 的算术平均版本。6.5 度分布异质时的辛普森式误判这个坑比较难发现。假设你按业务维度把节点分成两组发现 A 组整体聚类系数高于 B 组于是得出结论A 组圈子更紧。但如果 A 组里高度节点占比更高而高度节点的聚类系数天然偏低因为分母是 k(k-1) 增长很快那你看到的差异可能完全来自度分布的组成差异而不是真实的抱团程度差异。正确的做法是按度分层比较在同一度区间内比较两组的聚类系数或者直接和度保持零模型比。这一步能排掉绝大多数这类伪差异。6.6 时序图上的滑动窗口与节点进出动态网络里直接对每个时间窗独立算聚类系数会在窗口边界产生剧烈波动。原因是同一个三角形可能在窗口切换时被切开导致相邻两个窗口都算不到它。窗口越小这个效应越明显。我的处理方式是窗口之间保留 50% 的重叠同时记录每个窗口内的活跃节点数在解释趋势时把这个数一起看。如果某个窗口的聚类系数突然下降而活跃节点数没变那才是真实的结构变化如果活跃节点数也在剧烈变化那大概率是采样效应。另外节点进出会带来一个基础值漂移的问题新用户进来时往往先建立少量连接局部聚类系数为 0会拉低平均值。做趋势分析时最好固定一个核心节点集只用这批节点的局部值看趋势变化才干净。我自己的习惯是只要一张图的结构指标要对外出结论聚类系数这一项至少要报三个数平均局部值、全局值、以及和度保持零模型的比值。前面两个数字告诉你网络的形态第三个数字告诉你这个形态是不是异常的。只报一个数不管是哪个都容易被误读或者被人挑刺。至于口径我一般会在代码里把过滤规则写成显式的函数名比如avg_clustering_deg2plus让每个看代码的人一眼就知道低度节点有没有被算进去——这个问题我因为口径不一致返工过两次后来就再也不敢偷懒了。