跳到主要内容

Cliques & Cores 团与核算子集

算子类别：Cliques & Cores（团与核）
描述：用于发现网络中“高度内聚的紧密群体”与“稳定的核心结构”，刻画网络的深层结构强度与凝聚程度，是社区分析、核心成员识别、鲁棒性分析的重要工具。

一、算子集概述​

Cliques & Cores 算子集主要解决两类结构性问题：

1️⃣ 团（Clique）相关问题​

  • 是否存在一组节点，任意两两之间都有直接连接？
  • 哪些是“不能再扩展”的最大团？
  • 在考虑权重的情况下，哪一个团的“价值”最高？

👉 Clique 强调 完全连接（fully connected），结构非常严格，适合发现高度排他、强一致性的小群体。

2️⃣ 核（Core / K-core）相关问题​

  • 如果不断剥离“连接太少”的节点，最后剩下的稳定结构是什么？
  • 哪些节点位于网络的“核心层”，哪些只是外围？
  • 网络最深能剥到第几层（最大 K 值）？

👉 Core 强调 稳定性与层次性，比 clique 更宽松，适合分析大规模网络的骨架与韧性。

二、算子列表​

算子核心能力
find_cliques枚举所有极大团（Maximal Cliques）
max_weight_clique寻找权重和最大的团
k_core提取指定 K 的核心子图
core_number计算每个节点的核心层级

三、通用输入输出约定​

3.1 输入（Input）​

  • G：NetworkX 图
    • Clique 算法要求 无向图
    • Core 算法支持 有向 / 无向 / 多重图
  • nodes（可选）：指定必须包含的节点（仅 find_cliques）
  • weight（可选）：节点权重字段（max_weight_clique）
  • k（可选）：核心阶数（k_core）

3.2 输出（Output）​

  • 团算法：
    • find_cliques → iterator[list[node]]
    • max_weight_clique → clique 节点列表 + 权重
  • 核算法：
    • core_number → dict[node → core_index]
    • k_core → 子图（NetworkX graph）

四、算子详细说明​

4.1 find_cliques —— 极大团枚举​

功能说明​

枚举图中所有 极大团（Maximal Cliques）：

一个团如果不能再加入任何节点而保持完全连接，则称为“极大团”。

⚠️ 注意：

  • 极大团 ≠ 最大团
  • 极大团可能有很多，规模差异也很大

参数要点​

  • nodes（可选）：
    • 仅返回“包含这些节点”的极大团
    • 若 nodes 本身不是 clique，会直接报错（保证语义正确）

原理与复杂度​

  • 穷举搜索所有完全子图
  • 时间复杂度：最坏情况指数级
    O(3^(V/3))

适用场景​

  • 社交网络中的“熟人小圈子”
  • 欺诈/黑产中的“完全互联小团伙”
  • 蛋白质复合体、完全协作小组发现

4.2 max_weight_clique —— 最大权重团​

功能说明​

在所有 clique 中，寻找 节点权重和最大的团。

与 find_cliques 不同，它关注的是：

  • 不一定规模最大
  • 而是 “总价值最高”

参数要点​

  • weight：
    • 指定节点权重属性
    • 若为 None，则所有节点权重默认为 1（退化为“最大规模 clique”）

原理与复杂度​

  • NP-hard 问题
  • 时间复杂度：指数级（与图规模密切相关）

适用场景​

  • 高价值“内圈”识别（影响力、收益、权重）
  • 选人/选组合：要求彼此完全兼容，且总价值最大
  • 投资组合、广告渠道、基因模块筛选

4.3 core_number —— 核心层级计算​

功能说明​

为每个节点计算 Core Number（核数）：

一个节点的 core number =
它能参与的 最大 k-core 的 k 值。

直观理解：

  • core number 越大
  • 节点越“身处网络深层核心”

原理与复杂度​

  • 基于度递减的线性剥离算法
  • 时间复杂度：O(V + E)

适用场景​

  • 核心成员 / 核心设备 / 核心论文识别
  • 网络影响力与传播潜力评估
  • 网络层次结构分析（core–periphery）

4.4 k_core —— K-Core 子图提取​

功能说明​

提取一个 k-core 子图：

k-core =
所有节点度数 ≥ k 的最大诱导子图
（递归剔除度 < k 的节点，直到稳定）

参数要点​

  • k：
    • 不指定 → 返回主核（最大 k-core）
  • core_number（可选）：
    • 传入已计算好的 core number，可显著加速

原理与复杂度​

  • 递归剥离低度节点
  • 时间复杂度：O(V + E)

适用场景​

  • 网络骨架提取
  • 去噪（移除边缘/僵尸节点）
  • 稳定结构与韧性分析

五、Clique vs Core：怎么选？​

维度CliqueCore
连接要求完全连接至少 k 个邻居
严格程度非常严格相对宽松
规模通常较小可很大
复杂度指数级线性
典型用途小而强的“铁团”大规模核心骨架

经验法则：

  • 👉 想找 “彼此全都认识” 的小圈子 → Clique
  • 👉 想找 “越剥越稳”的核心结构 → Core

六、选型指南（快速）​

  • 列出所有紧密小团体：find_cliques
  • 找“价值最高”的完全互联小组：max_weight_clique
  • 判断谁在网络最核心层：core_number
  • 提取网络主干 / 去掉外围噪声：k_core

七、可直接回答的典型问题​

  • “网络中有哪些完全互联的小圈子？”
  • “谁是最核心、最不容易被剥离的节点？”
  • “剥掉所有外围节点后，网络还剩下什么？”
  • “在完全互相兼容的前提下，哪一组节点价值最高？”
  • “这个人/设备/论文，是核心成员还是边缘角色？”