做图数据挖掘的项目尤其是研究网络结构、社区发现、影响力传播这块绕不开几个老朋友K-core、truss number、clique还有经常被一笔带过的ECCeccentricity离心率。我最早接触这组概念是在分析社交网络里的“紧密小团体”时一开始看了很多论文发现作者们总把这些词揉在一起用于是花了不少力气把它们的关系、计算方式、适用场景全部理了一遍。今天把这份笔记整理成文送给正要入坑或已经在这条路上踩坑的同行。这篇文章不是简单搬运定义我会把每个指标从“它是干什么的”讲到“怎么高效算出来”再讲它们之间怎么配合、在真实项目里能派什么用场。适合对图论有一定基础、正在做图特征工程或社区挖掘的同学也适合想系统搞懂这几个密度概念、但被各种术语绕晕的新手。1. 为什么ECC、K-core、truss、clique总被放在一起讨论先说一个感受这四个概念本质上是同一类思想的三种颗粒度。它们都在回答一个问题——在一个图里哪些节点/边是“内部紧密”的只是看问题的粒度不一样。K-core看的是节点层面我至少需要保持多少度才能不被一层层剥离掉。Truss number看的是边层面一条边要参与多少个三角形才算稳固。Clique则是终极要求任意两点直接相连一个不多一个不少这是密度定义的极限状态。而ECC离心率可以理解为给每个节点算一个“最远距离”它和核心-边缘结构core-periphery structure研究关系非常密切。在实际项目里这组概念常常是组合使用的。比如我给一个用户网络做特征工程时会同时计算每个用户的core number核数和eccentricity离心率前者反映用户处于网络多深的“腹地”后者反映他距离网络边缘的最远位置。这两个值一组合能很清晰地把用户分成“核心圈层”“中间层”“边缘游离者”三类比单独用度degree或者PageRank直观得多。从算法演进的角度看这组概念也是一条线。最大团问题是NP-hard的现实中根本没法在大图上直接求于是人们提出k-core因为k-core可以在线性时间内算完后来又觉得只按度来削太粗糙就引入三角形约束变成k-truss而truss number本质上是对每条边做一次分解得到的“边的核数”。所以它们不是孤立的知识点而是同一问题在不同约束条件下的层层递进。理解这一点对后续选型非常重要。如果你的数据是几百万节点、上千万边的稀疏图clique根本不用想直接上K-core做粗筛再用truss二次过滤效率会高很多。这也是为什么很多论文里的pipeline都是“先core剪枝再truss细化最后枚举clique”。2. K-core与Core Number从网络剥离术说起2.1 K-core到底是什么怎么算先给定义再说人话。无向图G中如果存在一个子图H满足H中每个节点的度degree至少为k并且H是满足这个条件的最大子图那么这个H就叫做图G的k-core。一个节点属于k-core、但不属于(k1)-core它的core number就是k。说人话就是你一层一层地剥洋葱。把所有度小于k的节点全部剥掉剥完一轮发现又有新节点的度掉到k以下再剥掉直到剩下的所有节点度都不小于k剩下的这个壳未必连通就是k-core。这个过程中每个节点被剥掉时所在的那一层数就是它的core number。有个很容易混淆的点k-core不一定是连通图。它只是满足度约束的最大子图但里面可能有多个连通分量。很多新手拿k-core当社区用结果发现一个core里横着两个完全不相连的小团体然后就懵了。这在松散图里很常见建议在构建社区特征时额外做一次连通分量分析。计算core number的标准算法是经典的“桶排序Havel-Hakimi式剥离”复杂度是O(mn)在稀疏图上非常快。算法思想不复杂先统计每个节点的度把所有节点按度数分桶然后从度数最小的节点开始逐层剥离每剥掉一个节点就把它的邻居度数减1并将邻居移入新的桶中。简单说这个算法不涉及任何迭代的矩阵运算就是一遍扫描加一遍删边所以性能极好。用NetworkX的话一行代码就能搞定import networkx as nx G nx.karate_club_graph() # 经典的空手道俱乐部图 cores nx.core_number(G) print(cores)这个接口返回的是一个dict映射每个节点到它的core number。千万注意core_number输出的是每个节点属于的最大k-core的k值也就是核数如果只是想提取某个特定的k-core子图应该用nx.k_core(G, k)。2.2 Core Number在图中长什么样怎么解读我还是用空手道俱乐部图来说吧。这个图只有34个节点但结构非常有代表性两个老师分别带一拨学生中间有少量桥接边。算完core number后你会发现核心的几位学生和老师的core number是4外围学生大多是1或2边缘人物是0或1。这种分布非常有信号价值。在实际项目中我通常不直接看core number的绝对值而是看它的分布分位点。一个网络中如果有大量节点core number集中在最高档说明这个网络的结构非常“实心”谁都离不开谁反之如果大多数节点core number都只有1或者2只有极少数核心节点那这个网络就是典型的hub-spoke结构信息传播很容易被中间人卡脖子。另一个常用的做法是把core number当作“节点重要性的标签”。虽然它不像介数中心性那样精确刻画“流量咽喉”但它有一个很大的好处——计算极快且不需要全图最短路径。在大规模图上介数中心性几乎不可算core number却毫秒级出结果。所以很多推荐系统的图特征里core number承担了“结构深度”这个维度和度、聚类系数这些特征并列一起进模型。再提一个启发式经验网络鲁棒性分析中k-core分解后的最大core层数即最大的core number经常被当作网络韧性的指标。如果一个网络的最大核数是h说明就算随机去掉一批节点只要剩下的节点之间还存在一种h度以上的骨架结构网络就不会瞬间崩掉。这在基础设施网络的韧性评估、通信网络抗毁性分析里都有应用虽然分析对象不是社交网络但思路完全一致。3. ECC离心率计算节点到“世界尽头”的距离说到ECC先说一件尴尬的事在图形学、密码学里ECC有别的意思——椭圆曲线加密。但在图挖掘的上下文里ECC指的是eccentricity离心率。我第一次看到论文里的ECC差点念成加密算法后来才反应过来是图论里的老概念。咱们这篇文章里的ECC全部指离心率。3.1 离心率的定义与半径、直径的关系定义很简洁。在图G中一个节点v的离心率ecc(v)等于v到图中所有其他节点的最短路径距离中的最大值也就是ecc(v) max{d(u, v) | u ∈ V(G), u ≠ v}翻译成人话从v出发走到最远那个节点需要经过多少条边这个数值就是v的离心率。注意这个“最远”是整个图范围的最远不是局部范围的。从这里又引出两个经典概念图的半径radius是全部节点离心率的最小值图的直径diameter是全部节点离心率的最大值。直觉上半径对应的那个节点们就是图的“地理中心”直径对应的那对节点就是“最远的两个人”。写代码也很快ecc nx.eccentricity(G) print(ecc) print(radius:, nx.radius(G)) print(diameter:, nx.diameter(G))需要注意的是nx.eccentricity在非连通图上会计算失败因为孤立分量里的两个节点之间不存在路径。所以先判断连通性再算离心率是必备的流程。我在实际项目中处理一个100万节点的大图时发现里面有一堆孤立点直接算ecc就报错了必须先把主连通分量提取出来。3.2 离心率和Core Number怎么配合用很多做图挖掘的人忽略ECC原因很直接它的计算依赖全源最短路径在大图上太慢了。但换个角度想如果只在一个社区子图内部算离心率呢或者在已经用k-core筛出来的“核心圈层”内部算计算量会小很多而且更有业务含义。我经常这样构建节点特征先提取3-core以上的子图这个子图相对小而且结构紧密在这个子图上计算每个节点的eccentricity。这样一来core number告诉你“你在圈内吗、你处在多深的圈”eccentricity告诉你“你在圈内离边界多远”。两者组合成一个二维坐标非常有解释力。举个例子。一个电商平台的种子用户网络里有两个用户core number都是5说明他们的度约束层级一样深。但一个ecc是3另一个ecc是8。前者意味着他离这个核心圈的其他人都很近是真正的“圈内人”后者说明他虽然也在核心圈里但有点孤悬一侧像是核心圈和外部世界之间的桥接者。这两种用户的运营策略完全不同前者适合做圈层意见领袖后者适合做跨圈传播节点。这就是单一指标看不到的隐藏信息。再补充一点如果图规模大算全局ECC确实不现实但可以算近似ECC。常见做法是随机选一组“地标节点”landmarks只算每个节点到这组地标节点的最短路径然后取最大值作为近似离心率。这个近似的质量取决于地标的选择策略一般随机选几十个节点就能有不错的效果。实测下来在千万边级别的图上这个近似算法的误差通常能控制在可接受范围内而且运行时间从不可算变成了秒级完成。4. Truss Number与k-truss把边也拉进密度判定4.1 为什么光有K-core不够还需要TrussK-core只看度有一个致命弱点它其实无法保证“抱团”。想象一下两个完全独立的星型结构每个星型中心的度数都很高如果把它们中间加一条桥边然后做度约束的核心分解这条桥两端的节点可能因为度数不低而被保留在core里但整条桥在结构上是非常脆弱的“接缝”并不属于真正稠密的团块。换句话说k-core选出来的子图可能包含大量“虚胖”结构。k-truss就是为了解决这个问题提出的。它的定义建立在三角形上图G的k-truss是满足“每条边都至少被包含在(k-2)个三角形内”的最大子图。这里k从3开始有实际意义因为3-truss要求每条边至少在一个三角形里也就是说整个子图里不能有“孤吊”的边。理解k-truss的最好方式是把它看成边的k-core。把每条边看成一个“节点”把“共用一个三角形”看成一种连接关系那么k-truss本质上就是在边的图上做类似k-core的剥离。这种类比对新手指南特别友好我当时就是这么想通的。k-truss的意义在于它强制要求“每条边都必须有足够多的共同邻居”所以得到的子图内部没有明显的“峡谷”任意一条边都被周围足够多的三角形包围着。这在社交网络的“紧密朋友圈子”发现里比K-core的结果合理得多。两个人只互相关注但不认识共同好友在k-core里可能还在一个壳里但在k-truss里这条边因为没有三角形支撑第一时间就会被削掉。4.2 Trussness的计算与实操每条边对应的最大的那个k使得边属于k-truss称为这条边的truss number也叫trussness。计算truss number的思路和core number类似都是“剥离”思想但这里的单位从节点变成了边约束条件从“度数”变成了“三角形支持度”。学术上有不少优化算法比如用支持度索引、动态维护三角形计数等。但一般而言计算所有边的truss number在稠密图上开销不低因为三角形枚举本身就是O(m^1.5)级别的操作。在实际项目里如果只是想知道哪些边“最稳固”我一般不会去算全图的所有边的trussness而是先用core number筛出一个候选子图再在这个子图上算truss成本低很多。NetworkX也有直接的接口truss nx.k_truss(G, k4) # 提取4-truss子图 edge_trussness nx.truss_number? # 注意NetworkX当前没有全量trussness接口踩过坑提醒一下目前NetworkX的k_truss接口只支持无向简单图有自环、重边会导致三角形计算逻辑出错。如果你要用它处理真实数据第一步先做图清洗去掉自环、合并重边、确认无向。我见过有人在包含多条平行边的图上调k_truss出来的结果全是乱的排查了半天才发现是数据清洗没做干净。还有一个坑是k的取值。3-truss基本就等于提取所有在三角形里的边某些稀疏图上可能一下子滤掉一大半边这是正常的。不过要想找到高质量的紧密圈子一般从4或者5开始试然后根据子图规模反向调整阈值。实操中就对着子图节点数和边数做几次试跑才会有手感。4.3 Truss Number、Core Number到底该用哪个这个问题特别多人问。直接给结论如果只是粗筛用K-core如果要想确保结果稠密且没有“峡谷边”用K-truss如果想做社区簇的硬边界再用clique细化。时间开销上core是O(mn)truss取决于三角枚举clique是NP-hard——复杂度递增结果质量也递增。项目里常见的组合拳是大图上用core number快速划分层圈中间层用truss做二次过滤最后在极小的候选子图上枚举clique做精确校验。这个pipeline能兼顾性能和精度我在好几个数据集上验证过效果很稳。再补充一点truss number是边属性core number是节点属性两者不能直接比较大小但可以做映射关联。比如对一条边可以比较它的trussness和它两个端点的core number之间的差值。如果一条边的trussness明显低于两端节点的core number说明这条边是“借用两端节点的高核数混进核心区的弱边”在社区划分时应当考虑切开。这种桥边检测的方法比单纯看edge betweenness快很多在大规模图上尤其划算。5. Clique与Maximal Clique结构的最大公约数如果k-core是“松散的壳”k-truss是“紧密的小团队”那clique就是“铁板一块”——任意两点之间都有边。对很多应用来说最大团和极大团是社区检测的“金标准”因为团内部完全不存在任何缺失的连接是最直观的“紧密群体”。但现实很骨感判定一个图是否存在大小为k的团是NP-complete的找最大团更是出了名的难。所以在大规模图项目中clique几乎不以“全局枚举”的形式出现而是作为后验验证或者候选集内的精确搜索存在。举一个实际例子。我在做某社交平台的“兴趣小组挖掘”时先用core number筛出候选用户集合再用truss number过滤出高密度的候选子图最后在候选子图上枚举极大团maximal clique拿这些团作为“铁杆兴趣圈”。因为候选子图通常只有几百个节点枚举极大团完全在可控范围内。这一步得到的团长者数量少、召回低但精确度极高可以直接当作训练集的强标签再去做扩召回后面的事情就好办多了。NetworkX里枚举极大团比较方便cliques list(nx.find_cliques(G_sub))注意nx.find_cliques返回的是极大团maximal clique不是最大团maximum clique。极大团指“不能再添加任何节点还能保持完全连接”的团最大团指“所有团中节点数量最大”的那个团。求前者是多项式延迟polynomial delay可枚举的但数量可能指数级求后者才是NP-hard。很多新手把两者混为一谈在看论文时容易被绕进去。如果真需要在大图上做最大团的近似搜索《帕特里夏·S·B》里常常会提到贪心算法加启发式的做法。简单说就是每次选一个度数最高的节点把它作为团的一部分然后只在它的公共邻居里继续选节点重复这个过程。这个贪心方法虽然不保证找到最大团但在好多真实图上效果足够好尤其是配合core number做预处理之后性能提升非常明显。还有一个经典理论结果也是我用它做剪枝的依据一个规模为s的团的每个节点其core number至少是s-1。原因很简单团内每个节点与其余s-1个节点直接相连所以它在k-core分解中至少能坚持到第s-1层。利用这一点可以先求全体节点的core number如果一个子图里最高core number只有3那这个子图里绝对不可能有size大于4的团。直接剪枝省下大量计算。在实际操作里我还会用三角形计数作为clique的轻量级替代。因为3-clique就是三角形而很多真实的“紧密小团体”规模也就是5到10个人完全枚举虽然可行但可能与业务需求不匹配。很多社交网络的“群组”特征是三角形密度很高但不完全闭合。所以我在项目中经常这样取舍如果业务强调“绝对紧密”那就上clique如果业务能容忍95%的紧密性那用k-truss就够了性价比高很多。6. 从理论到代码一个完整的实操小项目说了这么多概念现在直接给一套能跑通的代码带大家做一个“图密度指标一键计算”的小工具。这个示例是我博客里的固定内容经过多次实战打磨针对小中型图最多几十万边可以直接抄作业。我用的是Python NetworkX数据集就用内置的空手道俱乐部图方便大家对照跑。import networkx as nx import pandas as pd from collections import defaultdict G nx.karate_club_graph() print(节点数:, G.number_of_nodes(), 边数:, G.number_of_edges()) # ---------- 1. Core Number 节点核数 ---------- core_dict nx.core_number(G) # ---------- 2. 4-core 子图 ---------- core4_subgraph nx.k_core(G, k4) print(4-core 节点数:, core4_subgraph.number_of_nodes(), 边数:, core4_subgraph.number_of_edges()) # ---------- 3. ECC 离心率在主连通分量上计算 ---------- if nx.is_connected(G): ecc_dict nx.eccentricity(G) else: # 取最大连通分量避免无穷大问题 largest_cc max(nx.connected_components(G), keylen) G_main G.subgraph(largest_cc).copy() ecc_dict nx.eccentricity(G_main) print(原图不连通取最大连通分量节点数:, G_main.number_of_nodes()) # ---------- 4. Truss 子图以4-truss为例 ---------- core_truss nx.k_truss(G, k4) print(4-truss 节点数:, core_truss.number_of_nodes(), 边数:, core_truss.number_of_edges()) # ---------- 5. 极大团枚举在truss子图上做控制规模 ---------- cliques list(nx.find_cliques(core_truss)) if core_truss.number_of_nodes() else [] max_clique max(cliques, keylen) if cliques else [] print(极大团数量:, len(cliques), 最大团大小:, len(max_clique)) # ---------- 6. 汇总成表格 ---------- rows [] for node in G.nodes(): rows.append({ node: node, degree: G.degree(node), core_number: core_dict[node], eccentricity: ecc_dict.get(node, float(nan)), in_4core: node in core4_subgraph.nodes(), in_4truss: node in core_truss.nodes(), }) df pd.DataFrame(rows) print(df.head(10))这段代码基本覆盖了前面说的全部指标。说几个注意事项第一nx.k_truss只支持简单无向图。如果你的数据是带方向的先G.to_undirected()如果有多重边先合并成单边如果有自环先删掉。第二用find_cliques时最好限制在truss子图上运行因为原图的极大团数量可能是天文数字。空手道俱乐部图上运行没问题但放开到上万节点的图枚举全部极大团就可能卡死所以在pipeline里先做候选集收窄是至关重要的习惯。第三如果项目规模超过百万级边NetworkX的核心分解会开始变得吃力虽然纯core计算是线性的但Python层的循环仍然很慢。这种时候建议换用igraph它的Graph.coreness()是用C实现的速度比NetworkX快一个数量级。import igraph as ig g ig.Graph.from_networkx(G) cores g.coreness(modeall)igraph的接口更简洁对大规模图友好很多。不过igraph计算trussness没有现成接口需要在三角形计数的基础上自己实现剥离循环工作量会稍微大一点。7. 常见问题与排查技巧实录7.1 为什么同一个节点的core number和truss number不在一个量级先说结论它俩本来就不是一个东西别放在一起比大小。core number是节点属性最大值是图最大核数truss number是边属性绑在某条边上。一个节点可以有很高的core number但它连出去的某条边可能trussness只有3这说明这个节点能靠其他边撑住核数但这条边本身是脆弱的。如果用图的节点-边关系做解释时这个差异本身就可以当特征用。7.2 图的连通性和ECC计算报错nx.eccentricity在非连通图上会抛异常或返回inf这个问题非常常见。“图不连通”是真实数据的常态我处理过的电商、社交数据几乎都有孤立节点或碎片化分量。建议先把最大连通分量提取出来算ECC其余节点的离心率当作缺失值处理而不是直接报错终止整个pipeline。7.3 k-truss结果为空或者太小k-truss要求每条边都在至少k-2个三角形里这个条件对稀疏图相当苛刻尤其是社交网络里有大量“汇报关系”式的弱连接三角形密度很低。遇到结果为空时试着从k3开始逐步降低阈值。还有一种情况是图的三角形本就很稀少比如二分图天然的三角形为0truss算法对这类图直接失效。如果在二分图场景下做社区挖掘果断放弃k-truss改用core number或者biclique相关的算法。7.4 极大团数量爆炸导致内存耗尽这是最现实的坑。枚举极大团虽然是多项式延迟但输出规模本身是指数级的。在真实图上一个节点稠密区域就可能产生几百万个极大团直接list(nx.find_cliques(G))会直接撑爆内存。解决办法是只用迭代器不转list对图做预处理core剪枝加truss过滤如果仍然太大设定最大团大小阈值或只保留最大团而不是全量枚举。7.5 core number在大图上的性能优化NetworkX的core number虽然是线性算法但Python循环开销导致它在千万级节点图上非常慢。此时我一般直接切到igraph或者用Spark GraphX的core分解实现。另有神技巧如果图可以按连通分量切分各个分量并行算完再汇总性能提升接近线性这个方法我在多机任务里验证过因此非常推荐。8. 这些指标的典型应用场景最后顺一遍各指标的落地场景帮大家选型时心里有数。网络鲁棒性与核心骨架提取用core number找“网络脊梁”评估网络抗毁性在电力网络、物流网络、信息传播网络中都有应用。社区发现与用户分层core number配合ECC做用户圈层划分识别“核心用户”“桥接用户”“边缘用户”在用户增长和精细化运营中意义重大。稠密子图挖掘从“k-core粗筛”到“k-truss细筛”再到“clique精确校验”的pipeline是最常用的三段式既能处理大规模数据又能保证结果质量。异常检测与反欺诈稠密子图尤其是truss值异常高的子图常常对应团伙欺诈比如一批账号短时间内互相关注、互相转账就会形成异常紧密的团。用truss number或者core number可以快速抓出这类团伙。推荐系统中的网络特征core number、truss number、ECC都是很好的结构化特征可以喂给机器学习模型提升推荐的个性化效果。有一点我想特别强调绝大多数情况下单一指标都不够用。我在实际项目里很少只依赖core number或者truss number因为每个指标都只能刻画结构的一个侧面。真正的稳健做法是像上面代码一样把节点度、core number、ECC、所属truss层级、是否在某个clique里等信息一起算出来做成节点级特征表再让下游模型去做判断。这个思路在不同领域都适用而且从工程角度来说这些计算都是可并行的、可控的不像PageRank和介数中心性那样在大规模图上容易失控。结尾小技巧与个人体会最后分享一个实战小技巧。做网络图分析时我几乎总是先跑一遍core number不是为了最终报告而是为了快速了解图的“结构纵深”。一张图如果core number最大才3那说明它非常松散后续所有基于“紧密子图”的算法都不用上了直接考虑连通分量级别的分析即可。反过来如果core number能到两位数这张图内部一定有非常稠密的结构值得用truss、clique去做进一步深挖。这个决策前置步骤看着不起眼实际能帮你省下大把时间。另一个习惯是所有密度类指标算完之后永远记得做一次“边验证”。选几条core number和truss number差异最大的边把两端的节点id拿出来回到原始数据里看它们的实际行为。你会发现这些边往往是模型中最容易出“意外”的地方——比如两个看似紧密的用户其实根本不互动只是共同关注了一堆公共账号。图结构特征只能说明“结构上紧密”业务含义还需要结合人工判断但把结构特征和高差异边挑出来本身就是一种很好的抽样检查方式。图数据挖掘这些指标的实操组合我至今还在不断调优。希望这篇笔记能帮你少踩几个坑也欢迎有自己的经验找机会一起交流。