期刊：PNAS

中文题目：社会与生物网络中的社区结构

英文题目：Community structure in social and biological networks

作者：M. Girvan and M. E. J. Newman

发表日期：2002年6月11日

摘要

近年来，多项研究聚焦于社交网络和万维网等网络系统的统计特性。研究人员尤其关注一些在许多网络中普遍存在的特征：小世界特性、幂律度分布以及网络的传递性。在本文中，我们重点探讨了另一种广泛存在于各类网络中的特性——社区结构。在这种结构中，网络节点以紧密相连的群组形式聚合，而不同群组之间则仅存在较为松散的连接。我们提出了一种用于识别此类社区的方法，其核心思想是利用中心性指标来界定社区边界。我们将在社区结构已知的计算机生成图和真实世界图上测试我们的方法，结果表明该方法能够以较高的灵敏度和可靠性识别出这些已知的社区结构。此外，我们将该方法应用于两个社区结构尚不明确的网络——一个合作网络和一个食物网——并发现，在这两种情况下都能检测到显著且具有信息价值的社区划分。

研究方法

作者的核心策略并非去寻找社群内部“最应该加入”的紧密连边，而是反过来，聚焦于社群之间“最应该移除”的薄弱边界。

借用了Freeman提出的“点介数”概念，并将其拓展至“边介数”：一条边的介数，等于网络中所有节点对之间的最短路径中，经过该边的路径数量。直觉上，连接不同社群的“桥梁”边会被大量跨社群最短路径所使用，因而具有极高的边介数。基于此，算法流程极为简洁：

Ø 计算网络中所有边的介数；

Ø 移除介数最高的那条边；

Ø 重新计算受影响的边的介数（这一步至关重要）；

Ø 重复上述过程，直至所有边被移除。

随着边不断被删去，网络逐步裂解为越来越小的连通分量，这些分量便构成一棵层次化的社群树（dendrogram），可在不同尺度上观察社群划分。算法在稀疏图上的时间复杂度为O(n³)，但作者指出，一旦网络分裂成多个独立分量，后续计算仅需在分量内进行，实际运行速度往往优于最坏情形。

研究结果与案例应用

为了全面检验算法的有效性，作者从多个网络展开验证，并将验证结果与具体案例应用紧密结合。

在社会网络上的精准验证：作者选取了Zachary空手道俱乐部这一社会学经典案例——34名成员因管理员与教练之间的矛盾最终分裂为两个实际阵营。应用该算法后，其输出的层次树第一次分裂就将网络清晰地切分为两个群体，这一划分与后来实际发生的分裂几乎完全吻合，仅有节点3被错误归类。而传统层次聚类方法在同一数据集上生成的树状图则与实际分裂情况关联甚微，充分印证了新算法的敏锐性（图1）。

图1（a）扎卡里空手道俱乐部研究中的友谊网络。与俱乐部管理员派系相关的节点以圆形表示，与教练派系相关的节点以正方形表示。（b）此处为分层树状图，展示了采用本文所提出算法计算得到的网络完整社区结构。网络最初的二元划分与扎卡里观察到的实际派系相符，但节点3被错误地归类。（c）采用边独立路径计数法计算得到的层次树，未能提取出网络已知的社区结构。

在大学体育联赛网络中的印证：作者还分析了2000赛季美国大学生橄榄球联赛的赛程网络（115支队伍，连边表示两队曾进行常规赛）。由于赛程安排天然受到联盟划分的影响，该网络具有已知的社群参照。算法识别出的社群与现实中各联盟（conferences）的构成高度一致，进一步证明了其在实际场景中的可靠性（图2）。

图2 2000年美国大学橄榄球一级联赛常规赛赛程的层次树状图。图中的节点代表球队，边则表示球队之间的比赛。我们的算法几乎完整地识别出了该网络中的所有联盟结构。

在未知结构网络中的探索性应用：作者将算法应用于圣塔菲研究所的科研合作网络（271位科学家及其合作者，连边代表合著关系）。算法将最大连通分量（118人）清晰地切分为若干社群：有的按学科主题聚集（如统计物理、RNA结构、生态学模型），有的则按方法论聚集（如使用基于Agent建模研究经济学与交通流问题的群体）。后者尤其有趣——它跨越了传统学科界限，反映了跨学科研究机构特有的合作模式（图3）。在切萨皮克湾食物网（33个代表性类群，连边表示捕食关系）中，算法识别出的两大社群几乎完美对应于上层水体生物（pelagic）和底栖生物（benthic）的栖息地划分。值得注意的是，这一社群结构并不按传统的“营养级”聚类，而是揭示了该生态系统中沿着栖息地形成的相对独立的能量流动子系统。不过作者也谨慎指出，该算法更适用于稀疏网络，而某些食物网连边密度过高，可能并不具备清晰的社群结构（图4）。

图3圣塔菲研究所协作网络中规模最大的组成部分，其中由我们的算法检测到的主要子群以不同的顶点形状加以标识

图4切萨皮克湾食物网的层级树状图。

创新之处

（1）视角的根本转换，从“寻找社群核心”转向“拆除社群边界”，通过移除而非添加边来揭示结构，巧妙地绕开了传统层次聚类易孤立叶节点的痼疾。（2）边介数指标的创造性引入，将原本用于衡量节点信息控制力的最短路径统计迁移到边上，使“桥梁”连边得以被定量识别。（3）“移除后必须重新计算介数”的策略，这一看似麻烦的步骤恰恰保证了算法在多个社群间存在多条连边时仍能准确命中边界，是一次重要的方法论纠偏。

启示

（1）空间交互网络的边界识别：人口迁移流、交通流、贸易流等均可建模为网络。该算法提供了一种数据驱动的方式，来自动划定城市群、经济协作区、流域单元等地理空间的自然边界，而非依赖行政或经验预设。（2）多尺度地理分区的层级构建：算法输出的层次树本身就是天然的多尺度划分体系，从微观节点聚合到宏观分区，可为嵌套式空间规划（如生态分区、国土功能区划）提供定量依据。（3）关键廊道与脆弱通道的识别：介数最高的“桥梁”边，对应连接不同地理社群的关键通道。识别这些通道，对于交通瓶颈预警、生态廊道保护、物资调配节点的布设具有直接指示意义。（4）方法论迁移：“拆边界而非找中心”的思路，也适用于地理学中边界检测、区域同质化划分等经典问题，为传统基于相似性聚类的分析提供了另一种互补路径。

文献来源：https://doi.org/10.1073/pnas.122653799

声明：以上中文翻译为译者个人对于文章的概略理解，论文传递的准确信息请参照英文原文。

撰稿：王晓辰

初审：任    杰

复审：杜    军

终审：鲁    鹏