Skip to content
返回搜索结果

社群检测——网络中的图聚类

提出者
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
年份
2002–2019 (algorithm family)
类型
Graph-partitioning / clustering algorithm family

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

社群检测是一系列图划分算法,旨在发现网络中连接紧密的子群——即社群。该领域最初由 Girvan 和 Newman (2002) 通过模块度量化,随后随着 Louvain 方法 (Blondel et al., 2008)、Leiden 改进 (Traag et al., 2019) 和基于信息论的 Infomap 方法的出现而迅速发展。所有这些变体都回答了同一个问题:哪些节点在内部的聚集程度比与网络其他部分的聚集程度更高?

方法背后的直觉

想象一个大型社交网络,其中一些人主要与他们的直接圈子交流,偶尔才与圈子外的人接触。社群检测能够自动发现这些圈子,而无需您预先进行标记。该算法将节点重新分组,使得内部连接密集,跨组连接稀疏——从而最大化一个称为模块度(modularity)的质量分数(或者在 Infomap 中,最小化随机游走通过网络的描述长度)。结果是一个划分:每个节点都属于且仅属于一个社群,您可以将网络可视化为一组内聚的簇。

历史学

Girvan 和 Newman (2002) 引入了边介数(edge betweenness)作为分层网络划分的工具,从而将网络社群结构的研究置于定量基础上。Newman 和 Girvan (2004) 随后将模块度 Q 正式化,使其成为标准的质量判据。Blondel 等人 (2008) 发表了 Louvain 方法——一种两阶段贪婪优化算法,使得在拥有数百万个节点的网络上进行高质量社群检测成为可能。Traag、Waltman 和 van Eck (2019) 发现了 Louvain 的一个结构性缺陷——它可能产生内部不连通的社群——并开发了 Leiden 算法来纠正这一问题,保证了良好连通的划分。与此同时,Rosvall 和 Bergstrom (2008) 开发了 Infomap,它将社群检测重新定义为一个压缩问题:找到能够最小化网络上随机游走描述长度的划分。

何时使用

当您拥有一个网络(至少约 20 个节点)并希望发现潜在的群组结构而无需预先指定群组时,社群检测是合适的。它适用于二元或连续边权重数据的探索性、描述性和分类目标,包括横截面和纵向网络数据。它不要求节点属性或正态分布。当社群数量未知时,该方法特别适用。如果网络太小(少于 20 个节点),则首选描述性网络统计。结果对边权重定义和网络密度敏感,因此这些选择值得仔细考虑。

局限与注意事项

  • 模块度最大化容易陷入局部最优;结果可能因运行而异,应报告多次运行中的最佳结果。
  • 分辨率限制意味着大型网络中非常小的社群可能会被合并,从而掩盖了精细的结构。
  • 结果对边权重的定义方式敏感;不同的加权方案可能会产生显著不同的划分。
  • Girvan-Newman 的复杂度为 O(m²n),在大型网络上不实用;对于大规模网络,应优先选择 Louvain 或 Leiden。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 无需预先指定社群数量——划分大小由数据决定。
  • 可扩展到大型网络:Louvain 和 Leiden 以接近线性的时间运行,使其适用于拥有数百万个节点的网络。
  • Leiden 保证了内部连通且内聚的社群,纠正了 Louvain 社群不连通的缺陷。
  • 适用于无权重和有权重网络,无需对数据进行分布假设。

应用

  • 在引文和合著网络中识别研究群集,以绘制科学领域图谱。
  • 在生物学中检测蛋白质-蛋白质相互作用网络中的功能模块。
  • 在社交媒体和通信网络中发现用户社群,用于行为分析。
  • 在商业和营销中细分客户网络,以揭示内聚的客户群体。
  • 发现基础设施、交通或供应链网络中的结构块。

使用方式

使用方式

1

输入是一个图,其节点代表实体(人、网页、蛋白质、引文),边代表它们之间的关系。边可以是有向的或无向的,并且可以带有权重。邻接结构——哪些节点连接以及连接强度如何——是算法所需的唯一输入。不需要节点标签、类别或外部属性,尽管它们可以在以后用于验证结果。

2

每个算法都从节点到社群的初始分配开始。在 Louvain 和 Leiden 中,每个节点最初都是其自身的单例社群。Girvan-Newman 从完整的网络开始,迭代地移除具有最高介数中心性(betweenness centrality)的边,逐步揭示社群结构。Infomap 从网络的随机游走描述开始,并使用两级映射对其进行编码以最小化代码长度。

3

核心阶段搜索一个能够最大化模块度 Q(Louvain, Leiden)或最小化地图方程代码长度(Infomap)的划分。Louvain 贪婪地在社群之间移动单个节点以提高 Q,然后将社群聚合成超节点并重复——这是一个两阶段过程,具有良好的可扩展性,但可能产生不连通的社群。Leiden 通过在聚合前使用局部移动和细化步骤,保证每个社群内部连通,从而改进了 Louvain。Girvan-Newman 迭代地移除边并记录分裂的树状图;选择在树状图的任何切割处最大化 Q 的划分。社群的数量由算法本身决定;无需预先指定。

4

最终划分的质量由模块度分数 Q 概括,其范围从 -0.5 到 1。高于约 0.3-0.5 的值通常被认为表明存在有意义的社群结构。由于模块度优化可能会陷入局部最优,因此多次运行算法并取最佳结果是标准做法。划分还会通过可视化检查,并与任何可用的节点属性或真实标签进行交叉验证,以确认其具有实质性意义。

常见陷阱

  • 只运行算法一次并将单个结果视为真实情况——应始终多次运行并报告最佳模块度或使用集成方法。
  • 忽略分辨率限制:在大型稀疏网络中,小而真实的社群可能会在没有警告的情况下被吸收到更大的社群中。
  • 将基于模块度的算法应用于节点少于 20 个的网络——在该规模下无法可靠地识别社群结构。
  • 将高模块度分数与已确认的真实世界社群结构混淆;模块度是划分的质量度量,而不是社群是否具有统计显著性的推断检验。

常见问题

我应该选择哪种算法——Louvain、Leiden、Girvan-Newman 还是 Infomap?

Louvain 是一种快速、广泛使用的大型网络基线算法。当正确性很重要时,Leiden 是首选,因为它保证了内部连通的社群,并且通常能达到更高的模块度。Girvan-Newman 产生一个树状图,可用于分层探索,但对于大型网络来说太慢。Infomap 非常适合有向或基于流的网络,其中随机游走的路径具有意义。

我需要预先指定社群数量吗?

不需要。Louvain、Leiden 和 Infomap 会根据网络结构自动确定社群数量。Girvan-Newman 产生一个完整的树状图,可以从中读取任意数量的社群;通常选择最大化 Q 的划分。

我如何知道发现的社群是否有意义?

模块度分数 Q 提供了一个数据内部的质量度量;高于约 0.3-0.5 的值表明存在非平凡的社群结构。除此之外,社群应根据领域知识、节点属性或外部标签进行验证。仅仅高 Q 并不能证明其社会学或生物学意义。

如果运行结果不同怎么办?

模块度优化是一种启发式方法,不同的运行可能会产生略微不同的划分,尤其是在 Louvain 中。多次运行算法(在大型网络上至少 10-100 次),并报告具有最高 Q 的划分。Leiden 比 Louvain 更稳定,因为其细化步骤更彻底,但重复运行仍然是良好实践。

相关方法

参考文献

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    打开 DOI 文献
    已复制。
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

    打开出版物文献
    已复制。