论文题目：

20 years of network community detection

论文地址：

https://www.nature.com/articles/s41567-022-01716-7

网络存在于我们生活的许多方面，从在线和离线的个人关系社交网络，基因、代谢物和神经元之间相互作用的生物网络，到互联网、基础设施和交通网络等技术网络。现代网络科学研究网络的结构和功能，例如由代表系统基本单元的节点以及连接它们的链接或边组成的网络[1]。

网络的一个显著特征是它们的社团结构——将节点组织成组，其中同一组中的节点紧密连接或共享相似的特征或角色（图1）。网络中社团检测的算法方法已经在许多学科中有了广泛的应用[2]。关于这个问题的早期研究可以追溯到20世纪80年代的社会学文献[3]，但在 20年前Girvan和Newman的工作之后[4]，这个问题引起了物理学界的广泛关注。在这里，我们回顾了过去20年在网络社团结构检测方面的进展。

主要方法

社团检测是一个丰富且具有挑战性的问题，部分原因是它不是很好地提出（关于网络中的社团结构目前还没有被广泛认可的唯一的定义）：我们所说的社团到底是什么意思？在大多数情况下，社团被定义为不重叠的节点组，使得组内的边比它们之间的多，但是这个定义仍然留下了许多可能性，并且相应地有许多计算方法。

‍

最常见的方法是基于优化的。为网络的每个可能的社团划分分配一个分数，这样“好的”划分获得高分，然后寻找得分最高的划分。有多种分配分数的方法。最流行的方法利用了被称为模块度的质量函数[5,6]，它明确支持在社团内具有许多边的划分。

模块度被定义为社团内部边的比例与一个随机网络中的期望比例的差值。形式上，模块度可以写成自旋模型，类似于网络上的Ising或Potts模型，以及统计物理中的一系列技术对其优化和解释产生了影响，包括马尔可夫链蒙特卡罗[7]、和离散优化方法[6,8]。

近年来受到广泛关注的优化方法的另一种变体是基于统计推断的。在这种方法中，社团不仅是网络结构的一个特征，而且是它的一个主要驱动因素：节点之间的连接正是因为它们所属的社团，就像在社交网络具有相似兴趣的人的情况或具有相似主题的网页。边的位置使用概率模型来表示，例如随机块模型 (SBM) [9]，其中两个节点连接的概率完全取决于它们所属的社团。一个“好的”社团结构是模型以高概率生成观察到的网络结构，因此该概率可以用作寻找最佳社团划分的评分函数。由于描述边概率的参数通常是未知的，因此计算变得复杂。为了解决这个问题，我们可以对这些参数进行单独优化，也可以将它们整合出来。前一种方法在数值上更有效，但后者的优点是不需要事先了解社团的数量。还有一个SBM的微规范版本，它不是固定概率而是固定边的数量，从而产生了一种基于最小描述长度的不同社团检测方法[10]。

第三类主要的社团检测算法依赖于社团结构和发生在网络上的动态过程之间的联系，特别是随机游走。由于网络社团之间通常只有稀疏连接，网络上的随机游走将倾向于在社团内徘徊，因此可以使用随机游走的概率分布进行社团检测。在这种类型中最流行的方法，称为InfoMap[11]，我们考虑随机步行者访问的社团序列——就像公路旅行可以用所访问地区的顺序来描述——如果一个序列的描述只需要很少的信息，在香农熵的意义上，一个划分被认为是好的。这种方法的一个很好的特点是，人们不需要实际执行任何随机游动来计算信息：对于无限长随机游走的熵有一个封闭形式的表达式，人们可以直接使用它作为社团检测的质量函数。

全局和局部

尽管这些社团检测方法工作良好，但所有这些方法都依赖于整个网络结构，这并不总是理想的。有时，人们可能只想知道一个小区域内的社团，并希望避免分析整个事件的计算负担。更重要的是，在某些情况下，对完整网络的关注可能会导致有问题的结果。一个社团的成员资格可能依赖于距离很远的网络部分结构似乎令人难以置信，例如，一个社交网络中的一群朋友的成员资格，可能受到与他们没有联系的遥远国家的人的影响。然而，这正是我们所描述的一些方法中发生的事情。

例如，模块度最大化返回的结果依赖于网络的总体大小，从而产生了所谓的分辨率限制，从而阻止了该方法在大型网络中找到小社团[12]。类似的限制也出现在其他方法中，比如那些基于SBMs的方法[10]。这些问题可以通过引入控制分辨率规模的参数[13]，或通过构建一个嵌套的划分层次结构，允许人们探索更小的社团规模来缓解[14]。但另一种选择是采用局部方法进行社团检测，在这种方法中，在不分析整个网络的情况下发现社团。局部检测方法的工作原理通常是通过在指定的种子节点周围构建单个社团，贪婪地添加节点，直到达到某个质量函数的局部最优值，这是一种计算效率很高的方法[15,16]。

基准测试和性能测试

鉴于社团检测的大量相互竞争的方法，一个关键问题是如何在其中进行选择。性能通常通过算法在恢复人工基准网络中已知社团方面的成功来衡量。例如，可以使用SBM生成此类网络，这是早期工作中的常见方法[4,17]，但由SBM生成的网络与现实世界的网络有很大的不同，后者的特征是度和社团规模的独特异质分布[18]。为了解决这个问题，已经提出了更现实的SBM变体，例如度-校正SBM [19]和LFR模型[20]，后者近年来成为标准基准。算法在恢复这些网络中的已知社团方面的成功通常是使用信息论度量来估计的，例如标准互信息[17,21]。

已经进行了大量大规模的研究来比较各种社团检测方法的性能[17,22]。发现上述所有方法在基准测试中通常都具有良好的性能，尽管当测试网络中的社团结构变弱时会出现有趣的转折。当社团内边的概率远高于社团之间边的概率时，算法很容易找到已知的社团结构。但随着概率变得越来越相似，社团检测变得更加困难，直到当概率相等时，社团完全消失。然而，令人惊讶的是，社团检测实际上在达到这一点之前就失败了：在参数空间中存在一个大小不为零的区域，其中社团存在于网络中，但算法无法找到它们。已经正式证明存在一个尖锐的相变点，即可检测性阈值，低于该阈值，所有算法都必定无法找到隐藏的结构[23-25]，这一结果不仅对社团检测，而且对更普遍的网络科学也具有指导意义。它告诉我们，有一些关于网络的问题有明确的答案，但却不可能找到这些答案。

量化社团检测算法性能的另一种方法是衡量它们在真实网络中恢复已知真实社团的能力。这样做的优点是可以在真实环境中测试性能，但缺点是很少确切地知道真实社团，因此正确答案存在一些模糊性。在许多情况下，人们使用某种节点属性或元数据作为真实社团的代理，但不能保证这些元数据与社团完全对应，尽管有经验证据表明两者往往是相关的[26]。或者，人们可以利用这种相关性，创建通过结合元数据知识和网络结构来推断社团的算法，而这样的算法，至少在一些研究中，似乎优于那些仅基于结构的算法[27,28]。

社团重叠结构、层次结构、嵌入结构

到目前为止，我们关注的是将一个网络划分为离散的、不重叠的社团的经典问题，但也有一系列对其他类型结构的变体和扩展。例如，社团可以通过一个层次结构来细分为连续的更小的社团，该层次结构捕获从整个网络到单个节点的规模结构[29]。在社交网络和其他一些网络中，相同节点属于多个社团的重叠或混合成员社团很常见[30,31]。术语“核心-外围结构”描述的网络分为高密度组和低密度组，具有密集的核心和较稀疏的外围，或具有不同密度的较大嵌套组[32,33]。所有这些结构类型都可以使用模块度变体或统计模型来检测。

稍远一点的领域是具有潜在空间结构或分层的网络。这些网络中具有（或可以指定）与边的位置相关的数值。社交网络中的年龄分层就是一个例子：人们往往与年龄相近的人成为朋友，因此边位于年龄值相似的节点之间。分层可以被认为是一种具有连续的、标量值的社团标签的社区结构，而不是离散的分类标签。每个节点上也可以有多个数值，并将其视为空间中定位节点的坐标，边往往位于附近节点之间，这种方法称为网络嵌入[34,35]。存在一系列算法，用于在低维空间中查找网络嵌入，即使节点值事先未知，也可以有效地推断节点值。例如，将社交网络嵌入一维空间中，即使没有任何有关个体身份的数据，也可以推断个体的大致年龄。

网络嵌入算法包括经典方法，如弹簧嵌入算法和拉普拉斯谱嵌入，这最初是考虑网络可视化开发的，统计方法更类似于社团检测的连续版本[36,37]。在很大程度上独立于这些努力-但可以说解决了类似的问题-是计算机科学中网络表示学习方法的发展，该方法试图为网络中的每个节点分配一个或多个维度的分数，这样在某种意义上相似的节点将获得相似的分数。在实践中，表示学习方法与本评论中描述的方法有很大不同，通常采用深度学习或神经网络方法。然而，如果将得到的分数视为几何空间中的坐标，则表示学习可以给出与嵌入方法类似的结果。除了对自身感兴趣之外，嵌入还提供了另一种检测标准离散社团的途径：可以将社团定义为嵌入空间中紧密相连的节点组，并使用经典数据聚类方法检测此类群体。

展望

网络中的社团检测是一个正在进行的积极研究的领域。新算法的开发继续受到极大的关注，特别关注于提高准确性，提供正式的性能保证，并开发计算高效的方法，应用于非常大的数据集。在数学和理论计算机科学中，已经并将有广泛的限制算法性能和形式检测边界的工作。另一个感兴趣的领域是为网络结构开发新的统计模型，既用于生成基准网络，也用于社团推理算法和其他更一般的结构形式的推理算法。我们设想在措施方面取得进一步的进展，特别是基于信息理论原则，以描述社团，比较网络的替代划分，并将划分聚为有代表性的群体。表示学习的进步将使我们能够利用多种数据类型进行社团检测，而不仅仅是网络结构，为解决问题提供新的强大方法。最后，社团检测方法的应用令人眼花缭乱，揭示了物理学、生物学、工程学、计算机科学、社会科学等领域的网络结构。

随着对现实世界的探索不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了【高阶网络读书会】。

集智俱乐部读书会是面向广大科研工作者的系列论文研读活动，其目的是共同深入学习探讨某个科学议题，激发科研灵感，促进科研合作。【高阶网络读书会】由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，每周分享时间为每周四 19:30-21:30 进行，预计持续 10-12 周。这其间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。