把一篇关于图数据挖掘的博文最合适的开场不是教科书式的定义而是真正遇到过的问题。我之前在做一个资金网络的分析项目时几百万个账号之间几百条转账关系全局聚类系数算出来很漂亮可实际要找的团伙一个都圈不出来。折腾了一圈最后是靠着 ECC、K-core、core number、truss number、clique 这一组图数据挖掘里的密集子结构指标把搜索范围一层一层缩小才算是真正把抱团这件事从数据里挖了出来。这篇文章就把这套组合拳完整讲一遍。不管你是做社交网络分析、反欺诈应急响应还是研究蛋白质相互作用网络只要面对怎么从一张大图里找出真正紧密的小团体这个问题下面的内容都可以直接拿去用。我会从最微观的边聚类系数ECC讲起逐步过渡到 K-core、core number、truss number最后聊到最严格的 clique并且配上一套可复现的 Python 实践流程。1. 先搞清楚紧密到底指什么从边聚类系数ECC切入1.1 一条边有多铁ECC的朴素定义ECC 的全称是 Edge Clustering Coefficient中文常叫边聚类系数。很多人一开始会把聚类系数默认成节点聚类系数也就是我朋友之间互相也是朋友的比例。但在图数据挖掘的密集子图任务里我们更需要的是判断一条边扎不扎实比如节点 u 和 v 之间这条边是不是被一堆公共邻居牢牢包围。一条边的 ECC 定义很直白[ ECC(u,v) \frac{|N(u) \cap N(v)|}{\min(d(u)-1, d(v)-1)} ]其中 N(u) 是 u 的邻居集合d(u) 是 u 的度数。分子是 u 和 v 的共同邻居数在简单无向图里这个数恰好等于包含边 (u,v) 的三角形个数分母表示最多可能有多少个共同邻居取两个端点各自扣掉彼此之后的邻居数最小值。举个例子u 和 v 有 20 个共同好友但 u 总共加了 500 个好友v 有 600 个好友那么这个 ECC 大约是[ \frac{20}{\min(499,599)} \approx 0.04 ]20 个共同好友听起来挺多但放到整个社交关系的尺度下一看这条边附近其实非常稀疏。反过来如果 u 和 v 一共只有 5 个朋友其中 4 个是共同的那么 ECC 4/4 1.0这说明这条边已经嵌入在一个局部高度闭合的小圈子里。ECC 的本质是把共同邻居这种绝对值归一化变成相对密度。1.2 为什么从边出发而不是从节点出发我在最初做这个项目时也问过自己直接用节点聚类系数不行吗后来发现关键区别在于节点指标回答的是这个人在自己的社交圈里混得开不开而边指标回答的是这两个人之间这层关系周围有没有足够的冗余连接。反欺诈场景里一条资金转账关系如果纯粹是正常交易那它周围往往没有什么三角形但如果这条边同时被许多其他交易关系支撑形成你转我、我转他、他再转回来的三角闭环这条边就非常可疑。这种三角闭环的性质天然是边属性不是节点属性。ECC 把关注点从顶点拉到边上正好匹配这类结构。另外后续要讲的 k-truss 分解本质上也是围绕边的三角形支持度展开的。ECC 里的分子——共同邻居数/三角形数——正是 truss 分解最核心的输入。1.3 手写一个ECC计算函数这里先用 Python 快速实现一个能跑的版本。注意在正式海量数据里建议用更省内存的数据结构后面我会专门讲坑。def edge_clustering_coefficient(G): 输入 networkx 无向图返回 dict: (u,v) - ecc ecc {} for u, v in G.edges(): common len(set(G[u]).intersection(G[v])) denom min(len(G[u]) - 1, len(G[v]) - 1) ecc[(u, v)] common / denom if denom 0 else 0.0 return ecc输出是每条边一个 0~1 的分数。如果只关心绝对三角支撑不关心归一化那直接取len(set(G[u]).intersection(G[v]))就是这条边的 support这个值会直接用于 truss 分解。在这个小函数里真正耗时的是每次都把邻居集合做交集。如果图比较大可以先把图转成邻接表矩阵再批量算或者用位图压缩邻居集合。这个优化我们放到第 6 章详聊。2. K-core与core number粗筛稠密区的第一层滤网2.1 k-核分解的剥皮思想K-core 的目的是找回一个子图其中每个节点都至少和该子图里 k 个其他节点相连。这个子图不一定稠密甚至可能没有三角形但它是相对核心的区域。计算过程像是剥洋葱先删掉当前图里所有度数小于 k 的节点删完后有些节点的度数会进一步掉到 k 以下继续删直到剩下的所有节点度数都不小于 k。这样留下的每一个连通部分都是一个 k-core。每个节点的 core number 定义为它能留住的 k 的最大值。比如一个节点最多能留在 4-core 里但留不进 5-core那它的 core number 就是 4。这个值越高说明节点在图中的核心程度越深。2.2 为什么core number适合做图数据挖掘的第一刀我在实际处理上亿条边时不会上来就枚举 clique而是先算一轮 core number。原因很现实K-core 分解可以做到 O(VE) 的线性复杂度是这几个指标里唯一能轻松撑起超大规模图的。Core number 具有单调性可以用桶排序配合链表增量更新在 Python 里跑百万节点也不会太吃力。Core number 能快速切开长尾噪音比如只跟一个节点相连的叶子账号这些账号天然只会留在 1-core 或 2-core 里对业务分析没什么价值。当然 k-core 的缺点也明显它只看度数不看三角形。一颗星形结构里中心节点度数极高整条星臂上的节点都可能满足很大的 k但这张图没有任何三角形根本谈不上抱团。所以 k-core 只能做粗筛不能做最终结论。2.3 一个k-core分解的实现桶排序版本下面是一个基于桶排序的经典实现逻辑不难关键是理解为什么删除一个节点会影响它的邻居。def core_number(G): from collections import deque degrees dict(G.degree()) nodes list(degrees.keys()) max_deg max(degrees.values()) if nodes else 0 # 桶bin[d] 存放当前度数等于 d 的节点集合 bins [set() for _ in range(max_deg 1)] pos {} for n in nodes: d degrees[n] bins[d].add(n) pos[n] d cor {} for k in range(max_deg 1): while bins[k]: v bins[k].pop() cor[v] k for u in G.neighbors(v): if u in cor: continue old_deg degrees[u] if old_deg k: continue bins[old_deg].discard(u) new_deg old_deg - 1 degrees[u] new_deg bins[new_deg].add(u) pos[u] new_deg return cor这段代码的核心思想每次从当前最小度数 k 的桶里取一个节点把它删除然后所有邻居的度数减一减到正好等于 k 时也会被装进同一个桶继续处理。最终每个节点的 core number 就是它被弹出时对应的 k。实际工程中如果图有 500 万节点直接使用 networkx 内置的core_number会更省心但当你需要在大图上自己定制逻辑比如结合边权、方向过滤时这个手写版更容易改。3. Truss number三角形构成的骨架比K-core更贴近抱团3.1 从边聚类系数到k-truss把三角形作为硬指标K-core 只知道节点度数够不够但一个真正紧密的社群内部应该有大量三角形。Truss 就是顺着这个思路提出的。定义一个 k-truss 是一个连通子图其中每条边都被至少 (k-2) 个三角形包含。注意这个 (k-2) 就是我在第 1 章算的 edge support共同邻居数。k-truss 的k比边的最小 support 多 2只是为了让最小索引从 3 开始。一条边的 truss number 定义为包含该边的最大 k-truss 的 k 值。如果一条边只参与一个三角形那它最多留在 3-truss 里truss number 就是 3如果一条边参与了 5 个三角形且这些三角形互相嵌套支撑它可能留在 7-truss 甚至更高阶的子里。这个直觉非常接近抱团你俩之间的这层关系有多少共同的利益点来支撑共同利益点越多这层关系越值得怀疑。3.2 truss分解的实现要点Truss 分解的思路与 k-core 完全对称只是把节点的度换成边的三角形支持度。计算每条边的初始 support也就是共同邻居数。把边按 support 值放入不同的桶。从 support 最小的边 (u,v) 开始删除这条边。删除时所有同时和 u、v 构成三角形的边也就是连接 u 与某共同邻居 w、或 v 与 w 的边support 减一。一条边被删除时它的 truss number 就是当前的 support 2。更新桶继续取下一条最小 support 的边。直接放一个朴素 Python 实现方便理解def truss_number(G): import heapq support {} for u, v in G.edges(): support[(u, v)] min_truss support.get((u,v), 0) len(set(G[u]).intersection(G[v])) # 为了效率实际要用桶这里用最小堆演示逻辑 heap [(s, u, v) for (u, v), s in support.items()] heapq.heapify(heap) truss {} while heap: s, u, v heapq.heappop(heap) if (u, v) not in support: continue truss[(u, v)] s 2 del support[(u, v)] # 找到同时与 u、v 相邻的节点 w common set(G[u]) set(G[v]) for w in common: for x, y in [(u, w), (v, w)]: if (x, y) in support: support[(x, y)] - 1 heapq.heappush(heap, (support[(x, y)], x, y)) return truss这个堆版本正确性没问题但复杂度偏高。严格的最优实现需要维护每一条边的 id 位置、双链表桶结构整体复杂度可以做到 (O(m^{1.5}))。在中小规模图上用上面的堆版本也可以跑只是当边数到百万以上后会明显变慢。工程上还有一个更快的路径先做三角形枚举给每条边打上 support 标签再类似 k-core 地按边支持度剪枝。大部分找稠密子图的库比如 NetworkX 的nx.k_truss底层逻辑就是先算支持度再做 k-core 变体。3.3 ECC、core number、truss number 对照这三个指标放在一起的时候很多同学容易记混。我整理了一个简表指标作用对象判据复杂度对紧密度的捕捉典型应用ECC边共同邻居/最大可能共同邻居(O(m \cdot d))归一化的局部密度边过滤、社区边界识别core number节点子图中度 ≥ k(O(VE))仅看度数粗糙大规模图快速粗筛truss number边子图中每条边的最小三角形支持 ≥ k-2(O(m^{1.5}))依赖三角形较准确稠密子图定位、团伙检测clique size节点集合任意两节点直接相连NP-hard最严格精确但昂贵小规模精确枚举、验证这个表基本上反映了图数据挖掘里做紧凑度度量的层次ECC 是局部视角core number 是全局线性视角truss number 开始引入结构约束clique 则是终极验证。4. Clique最严格的稠密结构以及枚举膨胀的代价4.1 团为什么是金标准Clique团的定义最简单粗暴一个顶点集合其中任意两个节点之间都有一条边。这是完全图的概念不存在比它更密的子图。在反欺诈、生物网络、推荐系统场景里找到真正的团往往意味着找到了一个完全闭环的小团队比如 5 个账号两两互相转账。这样的结构几乎不可能是自然行为嫌疑极大。但 clique 也有个致命问题找最大团是 NP-hard。哪怕只是枚举所有极大团Bron–Kerbosch 算法在最坏情况下也会指数爆炸。在一个有 100 万节点的社交网络里直接跑最大团枚举基本等于任务没开始就把计算资源烧光了。4.2 最大团/极大团枚举工程上怎么抄近路工程上最常见的组合是先用 K-core 和 truss 做大面积裁剪再在候选子集上精确枚举。原理很简单如果一个节点集合要形成一个大小为 s 的 clique那么这个 clique 里的每个节点在这个子图里的度数至少是 s-1每条边至少要出现在 s-2 个三角形里。反过来我们可以先得到 (s-1)-core再从中筛出至少位于 (s-2)-truss 区域中的边。这样原始图里绝大多数边都会被过滤掉。假设你想找 size ≥ 5 的团那可以先取所有 core number ≥ 4 的节点再取这些节点诱导子图中 truss number ≥ 4 的边成分。这么一轮下来百万节点图往往只剩几千个候选节点。在这个子图上再调用cliques list(nx.find_cliques(candidate_subgraph)) # 然后过滤掉 len 5 的nx.find_cliques使用的是带 pivot 优化的 Bron–Kerbosch 算法在剪枝后的子图上效率可以接受。我自己写过一个粗略对比10 万节点的随机图直接跑find_cliques内存很快打满但先做 core≥4 再做 truss≥4候选边数量少了两三个数量级最后枚举几乎所有极大团只需要几秒。4.3 如果只是找近似抱团的粗糙集合怎么办在绝大多数业务场景里你并不需要任意两点都相连这么苛刻的条件。真实世界的群体内部总会有那么一两条缺失边比如某人跟某个核心成员不熟、没加好友、没有转账。这时候强行枚举团会把很多有意义的候选子图丢掉。我的经验是把 truss number 大于某个阈值的连通子图直接当作准团使用。比如每条边至少被 4 个三角形支撑truss number ≥ 6的区域通常已经很能满足紧密团体的直觉。这类结构的数量远比 clique 少却比 clique 更抗噪。5. 把这些指标串成一个流水线拿反欺诈团伙识别当例子5.1 先构一个交易网络图假设现在有某支付平台的一批转账记录。先把数据抽象成无向图节点是账号边是转账关系。注意这里要先做预处理去掉自环和重复边。按业务规则过滤掉单笔小额、疑似无关支付的边。只保留至少存在一条双向转账或三角闭环的账号集合这一步说白了就是提前把不可能构成团伙的单链关系踢出去。这样处理后一个原始 50 万节点、120 万边的交易网络很可能缩到 3 万节点、6 万边。不要小看这一步它能让后续所有指标计算快一个数量级。5.2 三步流水线ECC过滤弱边 → K-core裁剪 → Truss/clique定点我最终沉淀下来的流程分为三步每一步都对应不同的阶段目标。第一步用 ECC 或 support 过滤弱边。针对剩下的 6 万条边计算每一条边的三角形 support。把 support0 的边过滤掉因为一条连三角形都没有的边无论它连接的两个节点多重要都不可能落在密集团伙内部。这一步之后图可能只剩 1.2 万条边并且这些边都至少被一个三角形包围。第二步对过滤后的图做 K-core 分解。计算每个节点的 core number取一个阈值比如只保留 core number ≥ 4 的子图。为什么取 4因为这意味着子图里每个节点至少和另外 4 个节点保持联系一个 5 人全连通团的最小节点度就是 4。这个阈值当然要根据业务微调但至少能帮你把规模压到千级别。第三步在候选子图上跑 truss 分解或 clique 枚举。如果只是想快速看结果那跑 truss number ≥ 5 的子图就够了如果业务要求精确核实就在第二步的候选子图上跑极大团枚举并过滤出 size ≥ 5 的团。这时的计算量已经小到可以在笔记本上完成。用我实际遇到的一组典型数据来说50 万节点经过第一步剩 3 万节点经过第二步剩 4000 节点最后 truss≥5 的结构只有 30 个连通分量极大团枚举输出 12 个 size≥5 的团。人工逐一审查这些候选效率非常高。5.3 验证别只看指标要看业务率图指标永远只是可疑程度的代理变量不要拿来直接当定性证据。我在每次输出结果后都会做一层业务验证团伙内部节点之间的转账是否存在资金闭环比如 A 转 BB 转 CC 转 A。这些节点是否在注册时间、设备指纹、IP 段上有聚集性是否存在一对多、多对多的刷单式交易规律如果图指标输出的是紧密结构但业务特征完全对不上那说明可能只是营销活动产生的互关簇而不是欺诈团伙。这套思路在图数据挖掘项目里非常重要结构是线索业务是裁判。6. 踩过的坑和可以直接抄作业的几条经验6.1 大图上别用递归、别用Python裸集合做上亿边Python 的小图和中等图都还好但一旦边数超过千万级你还拿set去反复求交集内存和 CPU 都会爆炸。我踩过最大的一个坑是直接用nx.k_truss处理百万级别图结果程序跑了一晚上还在支撑度更新那一步。解决思路有两个方向。一是换数据表示用 CSR/CSC 稀疏矩阵存图三角形枚举走矩阵乘法的思路能利用到底层 BLAS 优化。二是在超大规模场景直接用成熟的分布式图计算框架比如 GraphX 或拼装好的 C 图分析库不要跟 Python 硬刚。Python 版本更适合做原型验证、算法理解和中小规模数据清洗。6.2 无向图改有向图、权重的处理方式Truss 和 clique 的定义都建立在无向、无权图上。如果你拿到的是有向转账网络比如针对某个账号的一级流出关系那么需要先把方向投影成无向边。这里有个坑投影后边的权重怎么处理我一般不用边的权重去加权 truss而是先从权重的分布里找一个分位数阈值把边二值化。比如只保留转账金额在某分位数以上的边再把它变成无向边参与三角形计算。原因是三角形关系本身就是一种强结构信号如果叠加权重反而会让少数大额边主导结果掩盖团伙化的多项小额循环特征。6.3 ECC数值精度和共同邻居爆炸问题ECC 的分母是min(deg(u)-1, deg(v)-1)。在高密度图中如果这条边的两端都连着上千个节点分母很容易达到几百甚至上千但分子可能很小导致 ECC 非常接近 0。这种低数值并不是说边不重要只是被归一化稀释了。因此在干实际项目时我很少直接拿 ECC 阈值做硬过滤更多是看support这个整数指标。ECC 更适合做不同边之间的横向对标比如给每一条边算一个相对紧密指数然后用排序而不是绝对阈值来选边。另一个精度问题是如果图中有重边、自环或者多个连通部件计算共同邻居时要把这些情况明确过滤否则会出现 support 算多或算少的问题。在模板里跑通之前最好先用一个小型手算图验证一遍核心函数。这套方法的边界我也说清楚它适合关系型的静态或无向图适合挖掘紧密团体如果网络是动态演化的或者强调的是路径长度、影响力扩散那应该去关注另外一套指标比如 PageRank 和图神经网络。K-core、truss、clique 解决的核心永远只有一个——找到那些不容易散掉的小圈子。按照我上面这条流水线你至少能省下 80% 的无效计算时间并且每一步都有明确的中间产物可以检验。