Cliques & Cores 团与核算子集
算子类别：Cliques & Cores（团发现、核心分解与高凝聚结构分析）
算法数量：8 个
适用阶段：紧密群体发现、最大权重团识别、核心成员识别、网络骨架提取、核心-边缘层级分析、外围结构分析、核心临界节点识别、三角支撑结构分析
产品定位：为“网络中有哪些紧密小团体 / 谁处在核心层 / 剥离外围后剩下什么结构 / 哪些节点处于边缘或临界层 / 哪些关系具有更强三角支撑”提供团与核结构分析能力底座。
一、算子集概述
Cliques & Cores 算子集聚焦于高度内聚子结构发现与核心-边缘层级分析，主要回答以下问题：
-
团结构发现
- 网络中是否存在一组节点，任意两两之间都有直接连接？
- 有哪些不能继续扩展的极大团？
- 在考虑节点权重时，哪一个团的整体价值最高？
-
核心层级识别
- 每个节点处于网络的第几层核心？
- 指定 k 值下，网络中稳定保留下来的核心结构是什么？
- 哪些节点属于核心，哪些节点属于外围？
-
核心-边缘结构分析
- 某一层 k-shell 中包含哪些节点？
- 外围 crust 结构是什么？
- k-core 中哪些节点刚好处于临界支撑状态？
-
高阶凝聚结构分析
- 哪些边受到足够多三角形支撑？
- 网络中是否存在比 k-core 更强调局部闭合关系的稳定结构？
- 哪些子图具备更强的关系可信度与结构鲁棒性？
-
Clique、Core 与 Truss 的互补分析
- Clique 强调完全连接，适合发现小而强的紧密群体
- Core 强调最低连接约束，适合发现大规模稳定骨架
- Truss 强调三角支撑，适合发现更高阶的凝聚关系结构
二、算子能力分类
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 极大团枚举 | find_cliques | 枚举图中所有极大团 |
| 最大权重团 | max_weight_clique | 寻找节点权重和最大的团 |
| 核心层级计算 | core_number | 计算每个节点的 core number |
| K-Core 提取 | k_core | 提取指定 k 的核心子图 |
| K-Shell 提取 | k_shell | 提取指定核心层的壳层结构 |
| K-Crust 提取 | k_crust | 提取核心数不高于指定 k 的外壳结构 |
| K-Corona 提取 | k_corona | 提取 k-core 中度数恰为 k 的冠层结构 |
| K-Truss 提取 | k_truss | 提取每条边具有足够三角支撑的高凝聚子图 |
三、通用输入输出约定
-
输入
G：NetworkX Graph / DiGraph -
常见输入参数：
nodes：指定必须包含的节点，适用于find_cliquesweight：节点权重字段，适用于max_weight_cliquek：核心阶数、壳层阶数、冠层阶数或 truss 阶数core_number：可选的节点核心数结果，可用于加速部分核心类算法
-
常见输出类型：
- 团枚举类：
iterator[list[node]] - 最大权重团类：团节点列表及权重值
- 核分解类：
dict[node → core_index] - 子图提取类：
NetworkX Graph
- 团枚举类：
四、算子详细说明
1. find_cliques —— 极大团枚举
功能说明 枚举图中所有极大团。极大团指的是：在当前节点集合中，任意两个节点之间都有边相连，并且无法再加入其他节点继续保持完全连接。
产品价值
- 发现网络中最紧密的小群体
- 支持识别完全互联的强关系结构
- 适合用于强一致性、高排他性的小团体发现
典型场景
- 社交网络熟人小圈子识别
- 欺诈团伙发现
- 完全协作小组识别
- 蛋白质复合体分析
- 高度一致用户群发现
适用与特性
- 图类型：无向图
- 输出：极大团节点列表迭代器
- 注意：极大团不等于最大团，极大团可能有多个且规模不同
- 复杂度：最坏情况指数级
2. max_weight_clique —— 最大权重团
功能说明 在所有 clique 中寻找节点权重和最大的团。如果未指定权重，则节点权重通常按默认值处理，可退化为寻找规模意义上的高价值团。
产品价值
- 不只关注团的规模，也关注团的总价值
- 适合寻找“完全兼容且整体收益最高”的节点组合
- 可用于强约束下的组合优化与高价值群体发现
典型场景
- 高价值核心小组识别
- 互相兼容的团队成员选择
- 投资组合筛选
- 广告渠道组合选择
- 基因模块筛选
适用与特性
- 图类型：无向图
- 关键参数：
weight - 输出：最大权重团节点列表及对应权重
- 注意：最大权重团属于 NP-hard 问题，大规模图需谨慎使用
3. core_number —— 核心层级计算
功能说明 计算每个节点的 core number。一个节点的 core number 表示它能够参与的最大 k-core 的 k 值。
直观理解：
- core number 越大，节点越接近网络深层核心
- core number 越小，节点越偏向外围或弱连接区域
产品价值
- 识别节点处于网络核心还是边缘
- 支持核心-边缘结构分析
- 可作为网络稳定性、影响力和传播潜力分析的基础指标
典型场景
- 核心用户识别
- 核心设备识别
- 核心论文或核心作者识别
- 网络骨架分析
- 传播潜力评估
适用与特性
- 图类型：无向图 / 有向图
- 输出：
dict[node → core_index] - 复杂度：通常为
O(V + E)
4. k_core —— K-Core 核心子图提取
功能说明 提取指定 k 值下的 k-core 子图。k-core 是所有节点度数至少为 k 的最大诱导子图，通常通过递归剥离低度节点得到。
产品价值
- 提取网络中的稳定核心骨架
- 移除低连接、边缘或噪声节点
- 支持网络韧性、核心结构和主干结构分析
典型场景
- 网络主干提取
- 社交核心圈识别
- 僵尸节点过滤
- 供应链稳定结构分析
- 知识网络核心主题识别
适用与特性
- 图类型：无向图 / 有向图
- 关键参数：
k - 输出：k-core 子图
- 复杂度：通常为
O(V + E)
5. k_shell —— K-Shell 壳层结构提取
功能说明 提取指定 k 值对应的 k-shell。k-shell 通常表示 core number 等于 k 的节点组成的层级结构。
产品价值
- 将网络按核心层级进行分层
- 区分不同核心深度的节点群体
- 支持核心、准核心、外围节点的层次化分析
典型场景
- 用户层级分群
- 网络核心层次可视化
- 传播层级分析
- 组织网络层级划分
- 核心成员与准核心成员区分
适用与特性
- 图类型：无向图 / 有向图
- 关键参数：
k - 输出：k-shell 子图
- 特点：关注“正好处于某一核心层”的节点
6. k_crust —— K-Crust 外壳结构提取
功能说明 提取核心层级不高于指定 k 的外壳结构。它常用于观察网络中较外围、较低核心层级的部分。
产品价值
- 识别网络边缘结构
- 支持外围节点、弱连接节点和低稳定结构分析
- 可与 k-core 搭配，形成核心与外壳的对比分析
典型场景
- 边缘用户分析
- 低活跃节点筛选
- 外围设备识别
- 网络去噪前的边缘结构观察
- 核心-边缘对比分析
适用与特性
- 图类型：无向图 / 有向图
- 关键参数：
k - 输出：k-crust 子图
- 特点：关注核心层级较低的外围结构
7. k_corona —— K-Corona 冠层结构提取
功能说明 提取 k-core 中度数恰好为 k 的节点组成的结构。它可以理解为某一核心层中处于临界支撑状态的节点集合。
产品价值
- 识别核心结构中的临界节点
- 支持分析核心结构的稳定边界
- 可用于判断核心层是否容易被破坏
典型场景
- 网络脆弱性分析
- 核心层边界节点识别
- 传播网络临界节点发现
- 组织结构稳定性分析
- 基础设施网络风险评估
适用与特性
- 图类型：无向图 / 有向图
- 关键参数：
k - 输出：k-corona 子图
- 特点：关注 k-core 内“刚好满足 k 度约束”的节点
8. k_truss —— K-Truss 三角支撑子图
功能说明
提取 k-truss 子图。k-truss 要求子图中的每条边至少被 k - 2 个三角形支撑，因此它比 k-core 更强调边的局部三角凝聚性。
产品价值
- 发现具有强三角闭合关系的稳定群体
- 比 core 更关注边的关系质量和局部支撑
- 适合识别高可信、高内聚的关系结构
典型场景
- 强社群发现
- 欺诈团伙识别
- 互信网络分析
- 协作网络稳定群体发现
- 高凝聚关系子图提取
适用与特性
- 图类型：通常用于无向图
- 关键参数：
k - 输出：k-truss 子图
- 特点：强调三角形支撑，适合高阶内聚结构分析
五、推荐使用指南
1. 团结构发现
- 枚举所有极大团：
find_cliques - 寻找权重最高的完全连接群体：
max_weight_clique
2. 核心结构分析
- 计算每个节点的核心层级：
core_number - 提取指定 k 的核心子图：
k_core - 提取指定核心层壳层：
k_shell - 提取外围外壳结构：
k_crust - 提取核心临界冠层：
k_corona
3. 高阶凝聚结构分析
- 提取三角支撑稳定子图：
k_truss
4. 场景化选型建议
- 想找“彼此全部相连”的紧密小圈子：
find_cliques - 想找总价值最高的完全互联组合：
max_weight_clique - 想识别网络核心成员：
core_number - 想提取网络主干结构：
k_core - 想按核心层分层观察节点：
k_shell - 想分析外围结构：
k_crust - 想找核心层中的临界节点：
k_corona - 想找三角关系支撑很强的稳定群体：
k_truss
六、可直接回答的典型问题
- “网络中有哪些完全互联的小圈子？”
- “所有极大团分别包含哪些节点？”
- “在完全互相连接的前提下，哪组节点价值最高？”
- “谁是网络中最核心的成员？”
- “每个节点的核心层级是多少？”
- “剥掉外围节点后，网络还剩下什么主干？”
- “哪些节点属于某一层 k-shell？”
- “哪些节点属于网络外围结构？”
- “核心结构中哪些节点处于临界支撑状态？”
- “哪些关系受到足够多三角形支撑？”
- “这个节点是核心成员、准核心成员还是边缘节点？”
- “这个网络的核心-边缘结构是否稳定？”
七、算子清单
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | find_cliques | 枚举所有极大团 |
| 2 | max_weight_clique | 寻找最大权重团 |
| 3 | core_number | 计算节点核心层级 |
| 4 | k_core | 提取 K-Core 核心子图 |
| 5 | k_shell | 提取 K-Shell 壳层结构 |
| 6 | k_crust | 提取 K-Crust 外壳结构 |
| 7 | k_corona | 提取 K-Corona 冠层结构 |
| 8 | k_truss | 提取 K-Truss 三角支撑子图 |