英语原文共 5 页

网络中社区发现结构的快速算法

M. E. J. Newman

物理系和复杂系统研究中心，

密歇根大学，安娜堡，MI 48109-1120

许多网络展示社区结构——密集的连接之内但是在稀疏之间的顶点组——和近年来为了发现这种结构已经被发展的高敏感度的算法已经被发现了。然而，这些算法计算要求很高，这限制了它们在小型网络中的应用。在这里，我们描述了一种新的给出出色的结果的算法，当在计算机生成和现实世界中进行测试时，现实世界的网络速度要快得多，通常比以前的算法快几千倍。我们提供了几个示例应用程序，包括一个超过50 000物理学家的协作网络。

I.介绍

近年来，物理界对多种网络属性的兴趣激增，包括互联网，万维网，引文网络，交通网络，软件呼叫图，电子邮件网络，食物网， 和社会和生化网络[1,2,3,4]。引起特别关注的一个特性是“社区结构”：网络中的顶点经常被发现聚集成紧密编织的组，其具有高密度的组内边缘和较低的组间边缘密度。Girvan和Newman [5,6]提出了一种基于迭代去除具有高“中间性”分数的边缘的计算机算法，该算法似乎能够以一定的灵敏度识别这种结构，并且该算法已被许多作者用于研究 诸如电子邮件消息网络，动物社交网络，爵士音乐家合作，代谢网络和基因网络等多种系统[5,6,7,8,9,10,11]。正如Newman和Girvan [6]所指出的，他们的算法的主要缺点是它的计算需求很高。 在最简单和最快的形式中，它在具有m个边缘和n个顶点的网络上的最坏情况时间O(m²n)。 中运行，或者在稀疏图形上运行O（n³）（其中m与n在大n的极限中成比例），可能除食物网外，基本上涵盖了当前科学兴趣的所有网络。利用编写本文时可用的典型计算机资源，这将算法的使用限制在最多几千个顶点的网络上，并且对于交互式应用程序而言远远小于此。 然而，越来越多的人对研究更大的网络感兴趣; 例如，引用和协作网络可以包含数百万个顶点[12,13]，而全球网络数字则包含数十亿个[14]。

因此，在本文中，我们提出了一种发现社区结构的新算法。 该算法根据Girvan和Newman（GN）的不同原理运行，但正如我们将要展示的那样，给出了定性相似的结果。 算法的最坏情况运行时间是稀疏图上的O（（m n）n）或O（n²）。 实际上，它可以在合理的时间内在当前计算机上完成，最多可达到一百万个顶点的网络，从而可以实现以前被认为难以处理的许多系统中的社区研究。

II.算法

我们的算法基于模块化的思想。给定任何网络，无论是否具有任何这种自然的划分，GN社区结构算法总是产生一些顶点划分成为社区。为了测试特定划分是否有意义，我们定义质量函数或“模块性”Q如下[6]。设eij是网络中将组i中的顶点连接到组j中的顶点的边缘的一部分，并且让a _i = P j e_ij [19]。然后

（1）

是边缘落在社区内的部分，如果边缘随机下降而不考虑社区结构，则减去相同数量的预期值。如果一个特定的划分给出的社区内边缘不会超过随机机会预期，我们将得到Q = 0.除了0之外的值表示与随机性的偏差，实际上大于约0.3的值似乎表明了重要的社区结构。参考文献中给出了一些例子。6。

但现在这提出了一种寻找社区结构的替代方法。 如果Q的高值代表一个良好的社区划分，为什么不简单地优化所有可能划分的Q以找到最好的划分？ 通过这样做，我们可以避免迭代删除边缘并直接切入追逐。 问题是Q的真正优化是非常昂贵的。将n个顶点划分为g个非空组的方式的数量由第二类S_n^（g）的斯特林数给出，因此不同的社区划分的数量是。 这个总和在闭合形式下是未知的，但我们观察到对于所有ngt; 1，S _n^（1） S _n^（2）= 2^n-1，因此总和必须至少在n中呈指数增长。因此，对于Q的最佳值进行所有可能划分的穷举搜索将至少花费指数量的时间，并且实际上对于大于二十或三十个顶点的系统是不可行的。 可以使用各种近似优化方法：模拟退火，遗传算法等。 在这里，我们考虑一种基于标准“贪婪”优化算法的方案，该算法似乎表现良好。

我们的算法属于凝聚层次聚类方法的一般类别[15,16]。 从每个顶点是n个社区之一的唯一成员的状态开始，我们重复地将社区成对地连接在一起，在每个步骤中选择导致Q中最大增加（或最小减少）的连接。 算法可以表示为“树状图”，这是一个显示连接顺序的树（例如，参见图2）。 在不同的级别上剪切这个树状图，可以将网络划分为更多或更少的社区，并且与GN算法一样，我们可以通过查找Q的最大值来选择最佳切割。

由于没有边缘的一对社区的连接永远不会导致Q的增加，我们只需要考虑那些有边缘的对，其中任何时候最多都是m，m再次是图中边的数量。加入两个社区时Q的变化由Delta;Q= eij eji - 2aiaj = 2（eij - aiaj）给出，可以在恒定时间内清楚地计算。在连接之后，必须通过将对应于连接的社区的行和列加在一起来更新一些矩阵元素eij，其采用最坏时间O（n）。因此，算法的每个步骤都采用最坏情况时间O（m n）。构造完整的树形图需要最多n-1个连接操作，因此整个算法在稀疏图上以时间O（（m n）n）或O（n²）运行。该算法具有计算Q值的附加优势，使得发现最佳社区结构变得特别简单。

值得注意的是，通过使矩阵元素eij的初始值等于那些强度而不是仅仅为零或一，我们的算法可以简单地推广到加权网络，其中每个边缘具有与之相关的数值强度; 否则算法如上所述并具有相同的运行时间。 然而，本文研究的网络都是未加权的。

III.应用

作为我们算法工作的第一个例子，我们使用计算机生成了大量具有已知社区结构的随机图，然后我们通过该算法来量化其性能。 每个图由n = 128个顶点组成，这些顶点被分成四组，每组32个。每个顶点具有平均zin边缘，将其连接到同一组的成员，并将zout边缘连接到其他组的成员，选择zin和zout，使得总预期程度zin zout = 16，在这种情况下。 随着zout从较小的值增加，结果图对社区发现算法提出了越来越大的挑战。

图1：我们的算法在文本中描述的计算机生成的图中正确识别了顶点的分数。 这两条曲线显示了新算法（圆圈）和Girvan和Newman [5]（正方形）算法的结果。 每个点平均超过100个图。

在图1中，我们显示了算法作为zout函数正确分配给四个社区的顶点分数。 如图所示，该算法运行良好，正确识别超过90％的顶点，用于zout lt;~6的值。仅当zout接近值8时，每个顶点的社区内和社区之间的边数相同 算法是否开始失败。 在同一个图上，我们还展示了GN算法的性能，并且正如我们所看到的，该算法对较小的zout值执行略微但可测量的更好。 例如，对于zout = 5，我们的新算法正确识别平均97.4（2）％的顶点，而旧算法正确识别98.9（1）％。 然而，两者都表现良好。

有趣的是，对于更高的zout值，我们的新算法比旧算法表现更好，而且我们遇到了一些现实世界的网络，其中也是如此。 然而，通常情况下，GN算法似乎有优势，这应该不会让人感到惊讶。 我们的新算法的决策基于关于个体社区的纯粹本地信息，而GN算法使用关于整个网络的非本地信息 - 来自中间性得分的信息。 由于社区结构本身从根本上说是一个非本地数量，如果一个人可以随意使用非本地信息，那么人们可以更好地找到该结构。

对于足够小的系统，GN算法在计算上易于处理，因此，我们认为没有理由不继续使用它 - 它似乎给出了最好的结果。 然而，对于太大而无法使用这种方法的系统，我们的新算法提供了有用的社区结构信息，而且效率相对较低。

图2：我们的算法在Zachary的“空手道俱乐部”网络中发现的社区的树状图[5,17]。 顶点的形状代表俱乐部因内部争议而分裂的两个群体。

我们已将算法应用于各种真实世界网络。例如，我们已经在[5]中研究的“空手道俱乐部”网络上看到了这个网络，该网络代表了美国大学一个俱乐部的34名成员之间的友谊，这是Zachary在两年内所记录的[17]。在研究过程中，由于组织内部的争议，俱乐部分成两组，一组的成员离开，开始自己的俱乐部。在图2中，我们展示了通过将友谊网络馈入我们的算法而得到的树形图。峰值模块化为Q = 0.381，对应于分为两组17，如图所示。顶点的形状表示分裂后的球杆成员的对齐，并且如我们所见，算法找到的分割几乎完全对应于这些对齐;只有一个顶点，数字10，被错误地分类。 GN算法在此任务上执行类似，但并不是更好 - 它也可以找到分割，但是错误地分类了一个顶点（尽管不同的是顶点3）。在其他测试中，我们发现我们的算法也成功地检测到Lusseau的海豚社交网络的主要双向划分[6,18]，以及Gleiser和Danon的爵士乐网络中黑人和白人音乐家之间的划分[11] 。

作为我们的算法有时会错过网络中某些结构的演示，我们从Ref中再举一个例子。 5，表示美国大学橄榄球队在一个赛季中的比赛日程的网络。由于团队分为小组或“会议”，会议内游戏比会议间游戏更频繁，我们提前有一个合理的想法，我们的算法应该找到哪些社区。该算法生成的树形图如图3所示，其最佳模块度为Q = 0.546，与[5]中报告的最佳分割值略差0.601。正如树形图所揭示的，该算法找到了六个社区。其中一些对应于单个会议，但大多数对应于两个或更多。相比之下，GN算法会发布所有11个会议，以及准确识别不属于会议的独立团队。尽管如此，很明显新算法能够从网络中挑选出有用的社区结构，当然它也是更快的算法。在作者的个人计算机上，算法在不可测量的小时间内完成，不到百分之一秒。 Girvan和Newman的算法只花了一点时间。

在大多数实际情况下，这种程度的时间差异不会成为一个大问题，但当我们研究更大的网络时，性能会迅速成为一个问题。 我们期望运行时间的比率随着顶点的数量而增加。 因此，例如，在将我们的算法应用于上述爵士音乐家合作的1275节点网络时，我们发现它在大约一秒的CPU时间内运行完成。 相比之下，GN算法需要三个多小时才能达到非常相似的结果。

作为通过新算法的速度实现分析的一个例子，我们已经研究了物理学家之间的合作网络，如arxiv.org上广泛使用的Physics E-print Archive上发表的论文所记录的那样。网络是参考文献中描述的网络的更新版本。 13，如果科学家与他人合着了一份或多份在档案上发表的论文，他们就会被认为是联系在一起的。我们只分析网络中最大的组成部分，其中包含归档所涵盖的所有物理分支中的n = 56276名科学家。由于两个未被任何路径连接的顶点永远不会被我们的算法放在同一个社区中，因此在我们的算法意义上，可以安全地假设不属于最大组件的一小部分顶点位于不同的社区中。我们的算法需要42分钟才能找到完整的社区结构。我们的最佳估计表明GN算法需要三到五年的时间才能完成相同计算的版本。

分析表明，所讨论的网络由大约600个社区组成，具有Q = 0.713的高峰模块性，表明物理世界中的社区结构很强。 发现的四个社区很大，其中包含所有顶点的77％，而其他的很小 - 见图4，左图。 这四个大型社区与主题分区紧密对应：一个是天体物理学，一个是高能物理，两个是凝聚态物理。 因此，我们的算法找到的结构与人类观察者所感知的社区划分之间似乎存在很强的相关性。 正是这种相关性使得社区结构分析成为理解网络系统行为的有用工具。

图3：文本中描述的大学橄榄球网络中发现的社区的树状图。 现实社区 - 会议 - 由图例中指示的不同形状表示。

我们可以重复与任何子社区的分析，以观察他们如何分手。例如，再次通过算法喂养两个凝聚物质组中较小的一个，我们发现了更强的峰值模块化Q = 0.807-我们在任何网络中观察到的最强 - 相当于分裂成大约一百个社区所有尺寸（图4，中心面板）。大小似乎大致具有幂指数分布，指数约为-2 [20]。将我们的重点进一步缩小到包含本作者的这些社区中的特定一个，我们找到了图4右侧面板中显示的结构。最后一次通过算法提供这一结构，它分解成与个别机构研究小组，作者的小组出现在图的角落，由虚线框突出显示。人们可以进一步追求这种分析，识别各个群体，反复分解它们，并寻找它们之间合作模式的例子，但我们将其留待以后的研究。

IV.结论

在本文中，我们描述了一种从网络中提取社区结构的新算法，它比以前的算法具有相当大的速度优势，可以按照网络大小的平方进行缩放。 这使我们能够研究比以前更大的系统。 在其他例子中，我们将算法应用于超过五万物理学家之间的合作网络，并发现由此产生的社区结构与该领域的专业和研究小组之间的传统划分密切相关。

我们相信，我们的方法不仅可以将社区结构分析扩展到现在正在研究的一些非常大的网络，而且还提供了一个有用的工具，用于可视化和理解这些网络的结构， 迄今为止令人畏惧的规模使得它们的许多结构性质变得模糊不清。

致谢

作者感谢Leon Danon，Pablo Gleiser，David Lusseau和Douglas White提供的示例中使用的网络数据。 这项工作部分由国家科学基金会资助，编号为DMS-0234188。

图4：左图：物理学家协作网络中的社区结构。 该图分为四大类，每组主要由一个专业的物理学家组成，如图所示。 专业是由电子印刷档案的子部分确定的，其中个人发表论文：“C.M。”表示浓缩物; “H.E.P.

资料编号：[3949]