做图数据挖掘的项目，尤其是研究网络结构、社区发现、影响力传播这块，绕不开几个老朋友：K-core、truss number、clique，还有经常被一笔带过的ECC（eccentricity，离心率）。我最早接触这组概念是在分析社交网络里的“紧密小团体”时，一开始看了很多论文，发现作者们总把这些词揉在一起用，于是花了不少力气把它们的关系、计算方式、适用场景全部理了一遍。今天把这份笔记整理成文，送给正要入坑或已经在这条路上踩坑的同行。
这篇文章不是简单搬运定义，我会把每个指标从“它是干什么的”讲到“怎么高效算出来”，再讲它们之间怎么配合、在真实项目里能派什么用场。适合对图论有一定基础、正在做图特征工程或社区挖掘的同学，也适合想系统搞懂这几个密度概念、但被各种术语绕晕的新手。
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、但不属于(k+1)-core，它的core number就是k。
说人话就是：你一层一层地剥洋葱。把所有度小于k的节点全部剥掉，剥完一轮发现又有新节点的度掉到k以下，再剥掉，直到剩下的所有节点度都不小于k，剩下的这个壳（未必连通）就是k-core。这个过程中，每个节点被剥掉时所在的那一层数，就是它的core number。
有个很容易混淆的点：k-core不一定是连通图。它只是满足度约束的最大子图，但里面可能有多个连通分量。很多新手拿k-core当社区用，结果发现一个core里横着两个完全不相连的小团体，然后就懵了。这在松散图里很常见，建议在构建社区特征时额外做一次连通分量分析。
计算core number的标准算法是经典的“桶排序+Havel-Hakimi式剥离”，复杂度是O(m+n)，在稀疏图上非常快。算法思想不复杂：先统计每个节点的度，把所有节点按度数分桶，然后从度数最小的节点开始，逐层剥离，每剥掉一个节点，就把它的邻居度数减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不够，还需要Truss
K-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, k=4) # 提取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(m+n)，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, k=4) 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), key=len) 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, k=4) 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, key=len) 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(mode="all")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个三角形里，这个条件对稀疏图相当苛刻，尤其是社交网络里有大量“汇报关系”式的弱连接，三角形密度很低。遇到结果为空时，试着从k=3开始，逐步降低阈值。还有一种情况是图的三角形本就很稀少，比如二分图天然的三角形为0，truss算法对这类图直接失效。如果在二分图场景下做社区挖掘，果断放弃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拿出来，回到原始数据里看它们的实际行为。你会发现，这些边往往是模型中最容易出“意外”的地方——比如两个看似紧密的用户其实根本不互动，只是共同关注了一堆公共账号。图结构特征只能说明“结构上紧密”，业务含义还需要结合人工判断，但把结构特征和高差异边挑出来，本身就是一种很好的抽样检查方式。
图数据挖掘这些指标的实操组合，我至今还在不断调优。希望这篇笔记能帮你少踩几个坑，也欢迎有自己的经验找机会一起交流。
