利用导数图检测高阶网络中的社区结构

Detecting communities in higher-order networks by using their derivative graphs

利用导数图检测高阶网络中的社区结构

https://doi.org/10.1016/j.chaos.2023.114200

摘 要

与成对网络领域中发生的情况类似，超图（也称为高阶网络）的节点社区由共享许多超边的节点组形成，因此它们与其余节点共享的超边数量显著较少，这些社区可以被视为超图的独立部分（或超级簇）。在本工作中，我们提出了一种基于超图的所谓导数图的方法，该方法能够在不产生高计算成本的情况下检测高阶网络的社区。同时，我们展示了若干模拟实验，结果表明所提出的方法相较于其他现有方法具有显著的计算优势。

关键词: 超图 超图的导数 高阶网络 社区 超图中的社区 UPGMA（非加权组平均法） 层次聚类

1. 引言

在过去的三十年中，网络科学得到了快速发展，并成为最热门且最成功的研究领域之一，在遗传学、神经科学、系统生物学、人工智能、气象学和网络安全等领域有着跨学科的应用[1-8]。复杂网络模型已成为表示和模拟系统各部分之间不同类型交互关系的不可或缺的工具，广泛应用于工程、语言学、社交网络和经济学等多个领域[6,9-16]。然而，在许多情境和情况下，无法通过成对交互来描述系统中不同组件之间的关系，因此为了建立一个适当的系统模型，必须考虑高于二阶的交互[17-24]。新兴的结构和多种应用模型使得我们能够以非常高效的方式表示复杂系统组成元素之间的不同类型的交互。通过将两节点网络中的交互概念扩展到多节点的交互，超图或高阶网络的概念自然应运而生[17,18,25,26]。值得注意的是，正如成对连接的网络一样，在实际的高阶网络中，节点之间的连接是非常异质的，一些节点具有大量连接，而另一些节点的交互程度则低得多，从而形成了具有高度集中内部交互但与外部组交互较少的节点群。于是，节点被划分为不同的组，揭示了社区结构，这使得可以在微观尺度上分析高阶网络。在这种尺度下，可以通过一个新的图来研究高阶网络，其中顶点是社区，边表示它们之间适当且特定规模的连接或交互。其基本思想是，每个社区聚集了共享许多属性的节点，这些节点可能在网络的功能中扮演类似的角色。

值得注意的是，从网络拓扑结构中识别簇和模块的问题有着悠久的传统。该问题已在不同现象和多个学科领域中进行了研究（在组合图论的背景下，这个问题被称为“图划分”）。因此，针对这一问题的一些方法基于优化、统计推断、随机游走者、构建层次树状图，甚至通过从局部种子节点开始逐步添加节点直到获得某个质量函数的局部最优结果来获取社区[27-29]。无论如何，成对交互网络中的社区结构已经在文献中得到了广泛研究[27-37]。事实上，社区检测算法的发展与这一工具所应用的众多学科密不可分[2,4,8,11,27,29,33,34]。另一方面，在研究和识别密切交互并可能在所考虑结构中发挥相似作用的节点组方面，高阶网络背景下的社区检测也引起了网络科学界的一些关注[38-41]。在本文中，我们提出了一种基于超图导数图概念的新方法[10,42]，用于检测高阶网络中的社区。该方法不仅自然适应于高阶网络，还在此背景下相较于其他算法具有一定的计算优势。

本文的结构如下：引言之后，第2节致力于探讨超图导数的概念，并为通过导数图检测超图中的社区奠定基础。第3节应用前几节定义的数学概念和结构，提出了一种检测高阶网络中社区的新算法。第4节专注于将开发的工具应用于若干实际例子（包括合成数据和真实世界数据）以获取相应的特征社区。最后，在第5节中，我们总结了本工作的结论。

2 基本概念与一些初步结果

如前所述，导数图实现了一种用于衡量节点之间相似性的度量。因此，自然会产生一个问题：我们是否可以利用这一结构所提供的信息，将超图中的节点划分为不同的类别，使这些类别依据该相似性被区分开来？这将构成我们接下来将要讨论的两种社区发现方法的基础。

3 在超图中检测社区的不同方法

现在我们已经建立了一些有用的概念和符号，接下来将介绍我们提出的两种用于获取超图社区的算法。它们都具有层次聚类的背景，但在划分方法上有所不同：第一种本质上是一个数据驱动的算法，而第二种则考虑了问题的超图本质。随后我们还将简要介绍[47]中提出的另一种用于超图中社区检测的替代方法，用于与我们的结果进行比较。

3.1. 通过无监督聚类进行社区检测
在层次聚类中，有两种程序：聚合式（agglomerative）和分裂式（divisive）。本文聚焦的聚合式聚类方法在每一步中将距离最近的两个簇合并，直到最终只剩下一个节点，覆盖整个数据集。

聚合式层次聚类方法特别适用于仅定义了两种成对距离函数的数据集划分。一种距离函数用于衡量节点之间的距离，另一种用于根据节点间的距离衡量簇之间的距离，通常称为连接函数（linkage function）。文献中存在多种连接函数（如最短距离、平均距离或UPGMA、Ward方法等）[48–50]。在本研究中，我们将聚焦于平均距离连接函数，原因将在接下来的段落中讨论。

通常，层次聚类方法处理的数据集可以看作是 R n 中的点。因此，一个经典的选择是使用欧几里得距离来建模数据集中点之间的距离。节点聚类的连续步骤可以用一种称为树状图（dendrogram）的图示表示。具体而言，在图的一个坐标轴上表示数据集的点，垂直坐标轴上表示“高度”，即簇之间的距离。

由于 d 只定义在一个离散集合上，因此考虑使用辅助元素（如质心）来计算簇之间距离的连接函数是没有意义的。因此，在这种情况下，合适的连接函数选择将是平均值（UPGMA，即非加权成对平均连接法）。

为了启动凝聚层次聚类算法，每个初始簇将是一个包含一个节点的单元素集。在每一步中，将使用平均连接法计算簇之间的距离，即

3.2. 切割树状图的一般标准：最大间隔切割

在指出切割树状图的标准之前，正如在 [51] 中提到的，在凝聚层次聚类中，当在聚类过程中不同簇之间的两个或多个距离相同时，对于成对分组方法并不存在唯一性。解决这一缺点的常用方法是采用任意标准来打破距离之间的平局，这会导致根据所遵循的标准产生不同的层次排序。尽管可以考虑其他标准（例如在 [51] 中提出的在平局发生时同时合并两个以上的簇），但在本文考虑的算法 1 中，使用内部变量在不同簇之间的两个或多个距离相同时给出的排序标准在计算上更为高效。

在任何情况下，在更广泛的情境中，我们可以应用一个标准来选择树状图的一个特定划分。尽管这种方法没有使用超图的额外信息，但其结果可能足够准确，值得考虑。尽管它很简单，但这个标准是直观的，值得解释。

在凝聚层次聚类中，每一步都会合并两个不同的簇，以最小化簇之间的距离，这里将这种距离记作 D 。例如，在第一步中，它会寻找

3.3. 基于模块性的树状图切割标准

模块性是传统网络分析中用于量化网络中社区结构或模块化组织存在与否的概念。一个具有模块性的网络以节点划分为不同的组或社区为特征，社区内的节点彼此之间的连接比与其他社区的节点连接更为紧密。

对于成对网络的模块性，它衡量这种社区结构的强度。它是一个介于 -1 到 1 之间的标量值，更高的值表示更强的模块化结构。接近 1 的模块性值表明社区之间的划分非常清晰，而接近 0 或负值则表明社区结构较为随机或不够明确。它定义为：

然而，到目前为止，对于超图模块性的定义尚未达成共识，因为已有多种方法通过使用（3.7）并基于超图构建某种成对邻接矩阵来定义它。特别是，Kumar 等人 [47] 使用超图的团（clique）约简来定义超图模块性，并且由于从团约简得到的图中每个节点的度与超图中的度不一致，他们还进行了一些额外的调整。更具体地说，他们定义了一个具有邻接矩阵的图：

因此，在这种方法中，我们将选择最大化模块性（使用公式 3.8）的划分（由树状图给出）。请注意，尽管导数图（定义 2.4）为我们提供了一个邻接矩阵，但我们不能用它来计算模块性值，因为考虑到导数图的定义，超图中的一些节点可能会在导数图中合并为新的节点。此外，导数的较小值意味着节点之间的相似性更高，而公式 3.8 中导数的较小值则意味着社区结构更弱。此外，由于我们希望将我们的方法与 [47] 中的方法进行比较，我们需要使用相同的邻接矩阵来进行这样的比较。

迭代划分。需要注意的是，根据对社区划分细致程度的需求，算法2可以迭代地应用于每个获得的社区（考虑与它们相关的子超图）。这通常会增加获得的模块性。

3.4. 其他方法：迭代加权模块性最大化（IRMM）

在文献中，已经存在一种基于团约简（3.8）的超图社区检测方法，该方法通过最大化模块性来实现，即迭代加权模块性最大化（Iteratively Reweighted Modularity Maximization, IRMM）算法。我们将在后续部分将其与我们的方法进行比较，因此这里先简要概述。

IRMM算法的核心思想是在超图 H 的团约简图上应用Louvain算法，以获得最大化模块性的划分。随后，算法通过依赖于当前划分的重新加权函数重新计算超边的权重。重新加权的目的是强调当前聚类能够较好捕捉的超边的重要性，并降低信息量较少的超边的影响。通过迭代地重新加权超边并最大化模块性，IRMM算法旨在发现能够最大化超图社区结构的划分。迭代过程通过逐步调整超边权重和节点分配，帮助细化聚类结果。

4. 应用与现实世界示例

现在我们已经建立了两种社区检测算法（算法1和算法2）的理论基础，接下来我们将转向它们在合成网络和真实网络中的应用，并与之前提出的社区检测方法 [47] 进行比较。

我们将首先将这些算法应用于一个“手工设计”的超图，在这个超图中，通过简单的视觉检查，我们可以预期两种算法都能找到合理的划分。随后，我们使用一个真实且带有标签的小学学生数据集 [53, 54]，发现这些算法能够以高精度预测节点标签（即个体所属的班级）。最后，我们在这一部分的结尾将这些算法应用于一个更具异质性的数据集——科学合作网络。

所有数值模拟均在专用服务器（4.0 GHz Intel Xeon Gold 5220R）上进行，数据和代码可在以下链接获取，以确保结果的可重复性： 。

4.1. 一个简单的玩具模型

为了实践和讨论前一节中引入和讨论的想法，我们考虑了一个“玩具模型”，即一个预先设计好预期社区结构的超图。这个超图包含14个节点（按字母顺序标记为字母）和21条超边，如图2所示。我们还展示了其导数图对应的树状图。

通过一般方法（在最大间隔处切割树状图），我们找到了以下划分：

如果我们改用最大模块性来划分，得到的划分结果是相同的（这意味着在最大间隔处切割树状图可以得到具有最大模块性的划分，如图2d所示），模块性值为 Q = 0.34056 。

使用Kumar算法，我们发现了一组不同的社区：

很容易看出，这两个划分之间的唯一区别是，在第一个划分中我们有一个额外的社区 ，而在第二个划分中，它被拆分到了社区中。鉴于社区检测本身总是存在一定的主观性（并且在这个人为设计的例子中没有所谓的“真实情况”），这种差异是在合理范围内的。

在简单的例子中验证了一切如预期般运行之后，我们现在转向更现实的用例。

4.2. 用真实数据验证划分结果

将社区检测应用于真实网络时，面临的一个主要问题是：获得的划分是否“合理”。这种合理性通常来源于图之外的信息，通常与所讨论网络的特征和/或数据中未用于构建图或超图的信息或标签有关。

因此，为了验证所提出的方法，将其应用于一个真实的数据集（而不是像前面的玩具模型那样人为设计的）是很有意义的，这个数据集可能基于数据集的信息对获得的社区有一些“普遍共识”。

为此，我们将分析法国里昂一所小学在两天内232名学生和10名教师之间的面对面互动数据 [53, 54]。该数据集包括10个不同的班级，每个年级（从一年级到五年级）各有2个班级。互动是通过近距离传感器测量的，每个传感器都与一个组相关联：对于学生是特定的班级，对于教师则是“教师”标签。因此，超图由这242个节点组成，代表学生和教师，以及12699条超边，这些超边代表近距离传感器在20秒时间框架内捕获的面对面互动。

应用算法1和算法2，我们得到了有意义的结果。使用基于高度的切割算法，我们识别出8个社区。其中6个分别对应单独的班级：1A、1B、2A、2B、4A和4B。剩下的两个分别对应3A与3B的合并，以及5A与5B的合并。需要注意的是，一些社区中包含来自其他班级的少数“异常值”，但绝大多数都属于其同龄人。如果我们改用基于模块性最大化的算法，我们会发现1A、1B、2A和2B会被合并在一起。

从这次分析中，我们可以得出两个结论：从社区检测的角度来看，这些算法能够得出合理的分类结果，因为它们（特别是基于高度的切割算法，在这个特定例子中）符合应用于小学的社区检测预期。从社会网络的角度来看，这暗示了年幼的孩子可能跨越不同年级形成社区，而年长的孩子则更多地按年龄分化。

在表1中可以找到对这个数据集应用这两种方法的更定量的比较。值得注意的是，尽管超图中存在大量的超边，基于高度的切割方法在社区检测任务中表现得非常高效。而模块性最大化方法受到构建团约简图（3.8）的计算成本的限制，这是计算模块性所必需的。

在真实数据集中验证了获得的划分结果的合理性之后，我们将转向一个更具异质性的数据集，以进行最终比较，验证我们方法相对于文献中已有的方法的优势。

4.3. 真实数据的进一步结果

为了展示和比较我们的算法应用于真实数据时的表现，我们考虑了斯特凡诺·博卡莱蒂（Stefano Boccaletti）教授的合著者网络作为一个“试验场”来检测社区。我们将首先描述该数据集的主要特征以及构建超图时所做的不同选择。随后，我们将对我们的算法进行测试，并将其与其他已提出的算法进行比较，就像我们之前对玩具模型所做的那样。

数据集 我们构建了一个初始的合作超图，其中每个节点是一位与Boccaletti教授合作过的作者，每条超边代表一篇科学出版物。数据来源是Scopus，总计有338篇出版物和413位合著者。

为了给超图增加更多的结构，我们加入了另一组数据，这次不包括Boccaletti教授，而是包含每位合著者的全部出版物（原则上可能包括从未与Boccaletti教授合作过的其他作者，但这些作者并未被纳入超图中）。因此，超图得以扩展，现在总共包含15237条超边。

虽然我们的算法可以直接处理这个超图，但我们发现，当将其应用于该超图时，文献[47]中提出的IRMM算法无法在合理时间内收敛（在一台配备4.0 GHz Intel Xeon Gold 5220R的专用服务器上运行超过24小时）。为了比较两种方法，我们决定根据以下标准对超图进行过滤：仅保留与Boccaletti教授有5篇或更多共同出版物的作者（即我们考虑频繁合作的作者）。经过过滤后的超图包含67位作者，涉及他们之间和/或Boccaletti教授的1685篇出版物。

社区检测 我们将四种方法（导数图最大间隙切割、最大模块度、迭代最大模块度、IRMM）应用于Stefano Boccaletti的合作者超图。在展示实际分区结果（图3）之前，让我们先介绍每种方法的一些定量结果和指标。

从表2可以清楚地看出，尽管在模块度方面最佳的分区是IRMM方法得到的，但其计算成本并不值得这种微小的模块度提升，其运行速度比我们的最大模块度方法慢了约320倍。还应指出，IRMM能够获得最高的模块度是可以预期的，因为这是一种专门设计用于优化该分数的算法，而其他方法并非如此。因此，令人印象深刻的是，通过简单地扫描树状图中的个分区并选择模块度最大的一个，能够如此高效地达到类似的分数（仅相差0.04）。需要注意的是，尽管IRMM和模块度最大化都使用了团缩减方法（在小学示例中代价较高，见前一小节），但由于超边数量的减少，团缩减的计算速度显著加快。然而，IRMM的重新加权过程非常耗时，因为它需要在团缩减图上多次运行Louvain算法[52]，这抵消了部分加速效果。

5. 结论

在本文中，我们提出了两种用于检测高阶网络社区（在超图背景下）的方法，这些方法依赖于超图的导数图。通过多个例子和模拟实验表明，导数图所诱导的节点相似性和半距离概念对于在聚合过程中获得的簇之间建立连接距离特别有用。

通过多次模拟实验表明，尽管IRMM方法在模块性方面给出了略微更好的划分结果，但本文提出的方法在效率和计算成本方面更具优势。第一种方法是识别树状图中分支之间的最大距离。这种算法不仅速度最快，而且效率最高，因为它能够达到非常高的模块性值，接近IRMM的结果。此外，IRMM在计算上要昂贵得多，并且在其中一个例子中，它无法在合理的时间内完成所需的计算。另一方面，本文提出的第二种方法在模块性方面有所改进，尽管它增加了额外的计算成本，但这种成本与IRMM相比微不足道，IRMM虽然能够产生略微更好的模块性值，但其计算成本显著更高。

原文链接： https://doi.org/10.1016/j.chaos.2023.114200