跳到主要内容

Clustering & Community 聚类与社区算子集

算子类别：Clustering & Community（聚类系数、社区发现、传递性与环结构）

适用阶段：网络结构洞察、圈层/团伙识别、群落质量评估、闭环/循环检测、关系紧密度量化

产品定位：为“网络是否存在紧密小圈子 / 如何把人群或实体切成社区 / 这个切法好不好 / 是否存在闭环循环”提供统一算子能力底座

一、算子集概述​

Clustering & Community 算子集覆盖两大类能力：

  1. 局部紧密度与网络聚集性（Clustering / Transitivity）

    • 节点/网络整体是否“抱团”？
    • 三角闭合（triangle closure）倾向强不强？
    • 适合从“微观局部结构”判断网络是否存在小圈子、团伙、强关系群。

  2. 社区发现与方案评估（Community Detection & Evaluation）

    • 在没有标签的情况下，自动找到社区/阵营/圈层。
    • 支持不同机制：模块度最大化、标签传播、分层拆分、k-clique 渗透（可重叠社区）。
    • 对得到的社区切分进行质量评分与合法性校验。

另外，本类别也包含环结构/循环检测能力（simple_cycles / cycle_basis），用于识别资金回流、循环依赖、反馈回路等闭环模式。

二、算子能力分类​

能力类型对应算子功能描述
节点聚类系数clustering计算指定节点或全部节点的聚类系数
平均聚类系数average_clustering计算全图或子集节点的平均聚类系数
三角闭合计数triangles统计节点参与的三角形数量
全局传递性transitivity计算网络整体“朋友的朋友也是朋友”的程度
四环聚类square_clustering计算节点参与 4-cycle 的局部冗余结构倾向
社区发现-贪心模块度greedy_modularity_communitiesClauset–Newman–Moore 贪心合并最大化模块度
社区发现-分层拆分girvan_newman迭代移除“最关键边”得到分层社区结构
社区发现-同步标签传播label_propagation_communities通过邻居多数标签扩散形成社区
社区发现-异步标签传播asyn_lpa_communities异步更新标签传播（可控权重与随机种子）
社区发现-k cliquek_clique_communities基于 k 团渗透的可重叠社区发现
社区发现-Louvainlouvain_communities多层模块度优化，适合大图快速社区划分
社区发现-Leidenleiden_communitiesLouvain 改进版，更稳定且保证社区内部连通性
环结构-简单环枚举simple_cycles列举图中的所有简单环（可设置长度上限）
环结构-环基cycle_basis无向图的基础环集合（cycle space basis）
方案质量-模块度modularity对给定划分计算 modularity(Q)
方案质量-覆盖/性能partition_quality计算(coverage, performance)
方案合法性is_partition检查社区列表是否为严格 partition（不重叠且覆盖全节点）

三、通用输入输出约定​

  • 输入 G：NetworkX Graph / DiGraph
  • 输出类型：
    • 指标类（聚类/传递性/模块度）：float
    • 计数类（三角形）：dict 或 int
    • 社区结果：list[set] / iterable[set] / iterator[tuple[set]]
    • 环结构：list[list[node]] 或迭代器
    • 校验：bool

四、算子详细说明​

4.1 局部紧密度与聚集性​

1) clustering —— 节点聚类系数​

功能说明
计算节点聚类系数：衡量一个节点的邻居之间互相连接的比例（“邻居是否也彼此认识”）。

产品价值

  • 找“紧密朋友圈”中心节点
  • 团伙/密集团体的候选核心点

关键参数

  • nodes：单个节点 / 多节点 / None（全图）
  • weight：加权聚类（边权表示关系强度）

复杂度：O(V * d^2)（d 为平均度）

2) average_clustering —— 平均聚类系数​

功能说明
返回全图或指定节点集合的平均聚类系数，取值 0~1。

产品价值

  • 一句话概括“整体抱团程度”
  • 用于网络对比、版本对比、区域对比

关键参数

  • nodes：只看某个子群
  • weight：考虑关系强度
  • count_zeros：是否把聚类系数为 0 的节点计入平均值

复杂度：O(V * d^2)

3) triangles —— 三角形数量统计​

功能说明
统计每个节点参与的三角形数量，或返回指定节点的三角形数。

产品价值

  • 三角形越多，节点越处于“闭合小圈子”中
  • 可用于反欺诈/团伙识别中的结构特征

关键参数

  • nodes：单节点 / 多节点 / None（全图）

复杂度：O(V * d^2) 或 O(E^{1.5})（实现相关）

4) transitivity —— 全局传递性​

功能说明
全局指标：闭合三元组（triangle）占所有三元组的比例，衡量整体“三角闭合”程度。

产品价值

  • “朋友的朋友也更可能是朋友”在网络整体是否成立
  • 判断网络是否更像随机网络还是小世界网络（倾向性指标）

复杂度：O(V * d^2)

5) square_clustering —— 四环聚类系数（4-cycle）​

功能说明
衡量节点参与“4-cycle（四元环）”结构的倾向，常用于二部图或替代路径冗余分析。

产品价值

  • 发现“通过两条不同路径连接同一目标”的冗余关系
  • 二部图中经常比三角形更有意义（例如用户-商品）

关键参数

  • nodes：只计算子集节点

复杂度：O(V * d^2)

4.2 社区发现（Community Detection）​

6) greedy_modularity_communities —— 贪心模块度社区​

功能说明
通过贪心合并策略最大化 modularity，输出社区列表（按规模排序）。

适用特点

  • 速度快、实现经典
  • 适合中大规模无向图，支持边权

关键参数

  • weight：边权
  • resolution：控制社区尺度（<1 更大社区；>1 更小社区）
  • cutoff / best_n：控制停止条件与社区数量范围

7) girvan_newman —— Girvan–Newman 分层社区​

功能说明
迭代移除“最关键边”（默认边介数最大）使图逐步分裂，得到一棵分层社区结构（从粗到细）。

产品价值

  • 适合解释性强的“结构拆分”
  • 能输出多层级方案（适合小图/需要层次结构）

关键参数

  • most_valuable_edge：自定义“最关键边”的评分/选择方式

复杂度：较高（O(E^2 * V)），不适合超大图

8) label_propagation_communities —— 同步标签传播​

功能说明
基于邻居多数投票的标签扩散，无需优化目标，通常速度快。

产品价值

  • 超大图快速粗分群
  • 适合“先出结果再细化”的场景

复杂度：每轮 O(V + E)（迭代轮数依图而定）

9) asyn_lpa_communities —— 异步标签传播​

功能说明
与 LPA 类似，但采用异步更新顺序，允许通过随机种子控制可复现性，并可使用权重影响标签频率。

关键参数

  • weight：边权影响邻居标签“出现频率”
  • seed：随机状态，影响结果稳定性/可复现性

10) k_clique_communities —— k 团渗透（可重叠社区）​

功能说明
以 k-clique（完全子图）为基本单元，若两个 k-clique 共享 k-1 个节点则视为相邻，从而形成“渗透社区”。节点可属于多个社区（重叠）。

产品价值

  • 找“非常紧密”的核心圈子
  • 允许成员重叠，符合真实社交/合作网络

关键参数

  • k：最小 clique 大小（越大越严格，社区更小更紧）
  • cliques：可传入预计算 clique 列表（可显著节省重复计算）

复杂度：受 clique 枚举影响，通常指数级（适合中小图或局部子图）

11) louvain_communities —— Louvain 社区​

功能说明
经典多层模块度优化方法，速度快、适合大规模无向图（支持权重）。

关键参数

  • weight：边权
  • resolution：社区尺度
  • threshold / max_level / seed：收敛阈值、层数、随机性控制

特点

  • 工业界常用的“默认首选”之一
  • 结果可能随随机性变化（seed 可控）

12) leiden_communities —— Leiden 社区​

功能说明
Louvain 的改进版本，通常更稳定，且强调社区内部连通性（避免“看起来一组但内部断裂”的坏社区）。

关键参数

  • weight / resolution
  • max_level / seed

特点

  • 质量更稳，适合对社区结构有严谨性要求的场景

4.3 环结构与循环检测​

13) simple_cycles —— 简单环枚举​

功能说明
枚举图中所有简单环（不重复节点，起点=终点）。可设置 length_bound 限制环长度。

产品价值

  • 发现资金回流、循环交易
  • 发现软件依赖中的循环依赖
  • 发现生物代谢/调控网络的反馈环

关键参数

  • length_bound：限制环长度，避免爆炸式输出

复杂度：O((V + E) * (C + 1))（C 为环数量）

14) cycle_basis —— 环基（无向图）​

功能说明
为无向图输出一个 cycle basis：能够组合生成所有环的“基础独立环集合”。

产品价值

  • 电路网格分析（基尔霍夫法则）
  • 道路网络的基本闭合街区识别
  • 分解复杂环结构为基本构件

4.4 社区结果评估与校验​

15) modularity —— 模块度评分（Q 值）​

功能说明
对给定社区划分计算 modularity：衡量“组内边多、组间边少”的程度。

关键参数

  • communities：必须是对节点的 partition（互斥且覆盖）
  • weight / resolution

产出：float（通常越大越好，但需结合网络类型与分辨率理解）

16) partition_quality —— 覆盖率与性能​

功能说明
输出 (coverage, performance)：

  • coverage：社区内部边占比（内部边多不多）
  • performance：内部边 + 外部非边的比例（分隔做得好不好）

17) is_partition —— 分区合法性校验​

功能说明
检查给定社区列表是否是严格 partition：

  • 是否覆盖全部节点
  • 是否互相不重叠

注意

  • 对于允许重叠社区的算法（如 k_clique_communities），其输出通常不满足 partition 定义，此时不应强行用 is_partition 验证。

五、推荐使用指南（选型建议）​

  • 想先衡量网络是否“抱团”：average_clustering + transitivity
  • 想找局部紧密核心点/团伙特征：clustering + triangles（必要时 square_clustering）
  • 想快速得到社区（大图优先）：louvain_communities 或 leiden_communities
  • 想要更解释性的分层拆分（小图）：girvan_newman
  • 想极快粗分群（超大图）：label_propagation_communities / asyn_lpa_communities
  • 想找可重叠、极紧密的小圈子：k_clique_communities
  • 想给划分打分：modularity + partition_quality（先 is_partition 校验）
  • 想查闭环/循环依赖/资金回流：simple_cycles（必要时加 length_bound），无向图用 cycle_basis

六、可直接回答的典型问题（示例）​

  • “网络整体更像松散随机还是小世界？给我一个总体指标。”
  • “哪些节点的朋友圈最紧？列 Top-20 的聚类系数/三角形数。”
  • “把网络自动分成几个自然社区，并输出每个社区成员。”
  • “我有两种社区划分方案，哪个更好？给出 modularity 和 coverage/performance。”
  • “这个社区结果是不是严格分区？有没有漏人/重复分配？”
  • “找出所有资金闭环/循环依赖链路（可限制环长度）。”
  • “找允许重叠的核心小圈子（铁三角串起来的社群）。”