Hypergraphx: 一整套高阶网络分析算法和功能

Hypergraphx: a library for higher-order network analysis

Hypergraphx:用于高阶网络分析的库

https://github.com/HGX-Team/hypergraphx

从社会系统到生物系统，许多现实世界的系统都具有高阶的非二元交互。这些系统可以用超图来方便地描述，其中超边表示任意数量单位之间的交互。在这里，我们介绍了一个开源的 Python 库——HypergraphX（HGX），它提供了一整套用于高阶网络分析的算法和功能。这些功能包括不同的数据转换方式，将数据从一种高阶表示形式转换为另一种高阶表示形式，局部和中观尺度的各种高阶组织度量，高阶数据的稀疏化统计过滤器，广泛的静态和动态生成模型，以及不同的具有高阶交互的动态过程实现。我们的计算框架是通用的，允许分析具有加权、定向、带符号、时间序列和多重群体交互的超图。我们通过各种可视化工具提供高阶数据的可视化洞察。我们提供了一个扩展的高阶数据库，并通过对具有高阶交互的社会网络的系统分析来展示 HGX 的分析能力。该库作为一个不断发展的社区合作项目，将在未来几年进一步扩展其功能。我们的软件可以在 https://github.com/HGX-Team/hypergraphx 上获得。

1. 引言

在过去的几十年中，网络作为一种自然的工具，用于建模各种自然、社会和人造系统已经崭露头角。网络由节点和连接节点对的链接组成，它们只能捕捉二元交互。然而，在许多现实世界的系统中，单位以三人或更多人的组进行交互[1–4]。具有非二元交互的系统无处不在，例子包括细胞网络[5]、药物重组[6]、结构和功能脑网络[7–9]、人类[10]和动物[11]的面对面交互，以及合作网络[12]。这些高阶交互可以通过另一种数学结构——超图来自然描述，其中超边连接任意大小的节点组。

在过去的25年里，技术进步产生了前所未有的大量关系数据，涵盖了各种领域。拓展了网络科学领域的早期开创性贡献[14–16]，这些进步使得开发新的数据驱动框架来研究生物、技术和社会系统成为可能。与理论和方法的进步并行，算法和计算工具的开发在推动网络科学发展中发挥了关键作用。如今，广泛使用的社区基础软件，如 NetworkX [17] 和 igraph [18]，以及诸如 graph-tool [19] 之类的个人努力——仅举几例——使得成千上万的研究人员能够对关系数据进行多方面、大规模的网络分析。最近，一些早期贡献[20–24]，特别是 XGI [25]，已经开始开发计算工具，以匹配对高阶系统兴趣的爆炸性增长。

在此，我们通过介绍 HypergraphX (HGX) 来提供我们的贡献，这是一个用于分析具有高阶交互的网络系统的多用途开源 Python 库。该库由在高阶交互领域有多年经验和直接贡献的研究人员构思开发。HGX 由一个多学科的团队开发，该团队具有互补的技能和专业知识，旨在作为单一来源，提供一套全面的工具和算法，用于构建、存储、分析和可视化具有高阶交互的系统。这些工具包括不同的数据转换方法，以不同的高阶表示形式进行转换；局部和中观尺度的各种高阶组织度量；稀疏化高阶数据的统计过滤器；各种静态和动态生成模型；实现不同的高阶交互动态过程，从流行病到扩散、同步等。我们的计算框架是通用的，允许分析具有加权、定向、带符号、时间序列和多重群体交互的超图。除了领域专家，我们希望我们的库能使所有对探索关系数据高阶维度感兴趣的人都能访问高阶网络分析。

2. 工具

在这里，我们讨论 HGX 提供的主要功能。我们的库中的不同工具通过详细、用户友好的教程在线展示。该库作为一个不断发展的社区基础项目，将在未来几年进一步扩展其功能。

2.1 表示

超图代表了编码具有高阶交互系统的最通用和灵活的框架[2, 13]。然而，特定的研究问题或数据特征可能从其他高阶框架中受益。我们提供了将通常表示为超图的高阶数据轻松且高效地转换为不同表示形式的函数，如二分网络、最大简形复形、高阶线图、对偶超图和 clique 扩展图[2, 26]。

2.2 基本节点和超边统计

我们的库提供了描述基本节点和超边统计的简单工具。这些工具包括超度分布的度量，无论是汇总的还是按交互阶数分开的，以及它们之间的相关性度量。我们包括计算超度-超度关联性的函数，涵盖了阶内和阶间的情况。我们还提供了计算整个系统以及单个节点级别的超边大小分布的简单工具。

2.3 中心性度量

中心性分数是网络分析中的关键工具，允许量化系统中不同节点的重要性或影响力[15]。具有高中心性的节点通常具有大量链接、在其他重要节点之间具有战略连接，或具备这两种特征。我们的库提供了多种高阶中心性度量，考虑了不同群体大小的交互。这些包括基于节点参与不同子超图的中心性度量[27]和基于谱方法的不同中心性分数[28]。我们还实现了基于最短路径和介数流的超边中心性度量[29]。

2.4 模式

模式是网络中过度代表的小的重复子图模式[30]。模式分析已成为网络科学中的一个基础工具，用于描述网络系统的微观尺度，识别其结构和功能构建块[31]。我们提供了高阶模式分析的实现，提取由高阶交互连接的过度丰度子图，正如 Ref. [32] 中最初定义的那样。考虑到它们的广泛应用和预计在大规模现实世界数据集上的使用，我们还提供了一种基于超边采样的高阶模式分析的近似算法，能够在仅有极小精度妥协的情况下显著加速计算[33]。

2.5 中尺度结构

在表示现实世界系统的图中，最相关的特征之一是社区结构[34]。各种图社区检测方法展示了这些划分如何提供对节点交互基本模式的有意义洞察。近年来，定义高阶网络中尺度结构的方法得到了探索。我们提供了一种基于谱方法的实现，通过超图切割优化来恢复硬社区[35]。我们还实现了不同的生成模型，这些模型能够提取重叠社区并联合推断超边[36]，从而捕捉多种中尺度组织结构，包括不关联的和关联的社区结构[37]。我们提供了一种能够提取超链接社区的方法，其中交互而非系统单位被聚类到不同的超图模块中[38]。最后，我们提供了一种方法来提取高阶系统的核心-边缘组织，捕捉在超图中支配整体系统行为的一组中心和紧密连接的节点，这一方法受到了 Ref. [39] 的启发。

2.6 过滤器

许多现实世界的系统特点是过多的噪声和冗余的交互，导致网络连接过于密集。为了通过统计验证的方法确定最有信息的连接，已经开发了不同的过滤技术，这些方法通过与保留一些个体特征（如度数或强度）的随机复制集进行比较，来评估真实系统中交互的统计显著性[40]。我们的库提供了多种过滤工具，用于处理具有高阶交互的系统。这些工具包括提取统计验证的超图，这是一组过度表达的超边，代表在相同大小的固定组中显著交互的节点[41]，以及识别显著的最大交互集，这些集代表交互显著的最大节点组，通过结合不同阶的交互来捕捉[42]。

2.7 生成模型

生成具有不同拓扑特征的合成数据的能力对于各种任务至关重要，从算法基准测试到非平凡网络统计的研究和测试[43, 44]。在我们的库中，我们提供了各种合成超图采样器的现成实现。我们提供了构建广义 Erdös–Rényi 模型的函数，适用于均匀（所有交互具有相同阶数）和非均匀（不同阶的交互）超图。我们实现了无标度随机超图模型，可以调整不同阶之间度序列的相关性。我们还包括各种随机化工具和超图配置模型，其中样本是在尊重给定的节点度和超边大小序列的情况下生成的[45]。基于类似的机制，我们还实现了一个更复杂的采样器，允许指定节点的硬性和软性社区分配以及任意社区结构，如关联和不关联[46]。最后，我们提供了一个高阶活动驱动模型，其中组交互随时间变化[47]，并计算了相关的渗透阈值。

2.8 动态过程

复杂网络的结构特性会影响在其上发生的动态过程[48]。最近的研究揭示了高阶交互显著影响各种动态过程，包括渗透[49]、扩散[50, 51]、模式形成[52, 53]、同步[54–58]、传染[59–61]和进化博弈[62–64]。我们提供了研究这些过程的功能。这些工具包括用于分析高阶交互的同步工具，从对 Kuramoto 动力学的多阶拉普拉斯矩阵分析[55]，到用于同步稳定性的主稳定性函数方法[54, 65]的实现。我们还提供了模拟简形社会传染的算法[60]，以及分析和数值工具来研究超图上的随机游走[50]。

2.9 加权、定向、带符号、时间序列和多层超图

我们的库具有高度的灵活性。它允许存储和分析具有丰富特征的超图，包括不同强度、方向、符号的交互，这些特征可能随时间变化或属于多层系统的不同层。

2.10 可视化

随着对高阶网络的应用迅速增加，开发标准工具来可视化这些网络仍在进行中。我们的库提供了不同的可视化工具，以便对现实世界系统中的高阶组织结构获得视觉洞察。我们提供了绘制高阶交互系统的工具，其中任意大小的超边表示节点之间的关系。由于可能的高阶交互及其重叠数量的组合性迅速增加，这种直接的方法特别适用于节点数量适中的系统，而在其他情况下可能效果不佳。因此，我们提供了替代方案，可以在各种情况下协助用户，例如节点数量或超边大小较大的关系数据。例如，我们提供了绘制超图的二部投影的选项，其中两个节点集分别代表原始系统单元和它们参与的超边。我们还可以绘制超图的克利克投影，这将生成一个简单的图，其中每个大小为s的超边被分解为s(s−1)/2个无序的对偶交互。此外，我们实现了超图的多层表示，其中每一层编码了给定大小的交互，两个节点仅在它们通过大小为s的超边在超图中交互时才在第s层连接。最后，我们提供了一种新颖的超图可视化方式，其中超图表示为图，图的节点是饼图。这些饼图显示了每个节点的交互大小比例，两个节点之间的连接表示它们在多个阶次中有显著的交互。

3. 数据

在这里，我们介绍了附带我们库的数据集存储库。该存储库旨在提供一个初始核心的高阶关系数据，我们计划在接下来的几年中扩展这些数据集。我们通过对其中一个数据集进行不同的高阶分析来展示HGX的功能。

3.1 高阶数据存储库

数据的可用性在不同科学领域和应用中开发理论框架和计算工具方面发挥了重要作用。近年来，高阶关系数据的激增促使了研究高阶系统的新方法，这些方法需要广泛的数据集来进行测试和验证。一些数据本质上是高阶的，而另一些数据最初是通过对偶方法研究的，但最近重新以高阶网络分析的新视角进行了探索。这促使我们为我们的库提供一个易于访问且精心策划的数据存储库，作为分析高阶系统的数据集的统一来源。我们提供了来自不同领域的高阶系统的数据集，包括生态（动物接近度[66]）、社会（人际面谈互动[67–71]、共同作者[72–74]、投票[75]）、技术（电子邮件[73, 76, 77]）和生物（基因-疾病[78]和药物[73]关联）系统。这些数据集中有些记录了描述系统单元的元数据（例如，医院中的个体是病人还是医生）和它们之间的交互（例如，涉及一组作者的科研论文的科学领域）。此外，它们还存储了群体交互的结构特征，这些特征可能是非互惠的、多重关系的和时间变化的。数据集可以在加载时明确突出一些这些特征。实际上，我们的库允许在数据加载过程中应用过滤器，例如，通过选择特定的节点集合来满足某些元数据限制，或提取限制于特定大小、类型或时间间隔的群体交互。在未来几年，我们计划不断扩展数据存储库，并为数据加载函数添加更多过滤选项。

3.2 分析现实世界的高阶系统：引导之旅

为了展示HGX在加载、处理、分析和可视化具有群体交互的现实世界系统中的强大功能，我们在图1中展示了对SocioPattern合作数据集的示例分析，该数据集记录了高中中的面对面社交互动[69]。这个数据集在高阶交互的文献中得到了广泛研究[32, 36, 46, 60, 73]，记录了327名学生的活动，这些学生分为九个不同的高中班级。我们的分析特别集中在2人、3人和4人之间的互动，因为对于较大群体的统计数据有限。

在图1(A)中，我们展示了不同的高阶度分布。对于成对的交互，度数最大，一般来说，曲线显示出不同的轮廓。高阶度分布在不同的阶次之间显示出不同的相关性（皮尔逊相关系数 ρ，ρ2,3 = 0.74，ρ2,4 = 0.46，ρ3,4 = 0.72）。为了在微观尺度上表征这样的高阶系统，在图1(B)中，我们进行了高阶图案分析，如Ref. [32]中介绍的那样。我们考虑了三节点的子超图，并捕捉了在数据中较多（正丰度分数较高）和较少（负丰度分数）出现的图案，相较于随机的高阶配置模型[45]。发现有群体交互支持的局部结构特别相关。在图1(C)中，我们描述了系统的中尺度结构，通过使用Ref. [36]中的方法提取重叠的社区。为简化起见，我们考虑了三类的子集，并仅绘制了成对的交互。节点用饼图表示，颜色与它们所属的高阶社区成比例。一般而言，推断出的模块与节点元数据很好地对齐，大多数学生主要在其班级相关的社区内进行交互。在图1(D)中，我们展示了数据集中交互的统计信息。我们观察到交互数量与群体大小之间的反向趋势。我们还绘制了过滤系统的统计信息，其中我们考虑了统计验证的超图[41]，去除了冗余超边，并识别了最具信息性的群体交互。接下来，我们展示了Ref. [46]中介绍的模型生成与原始数据集相似的超图的能力。为了验证这一点，在图1(E)中，我们绘制了现实和采样超图中（一个重新缩放版本的）高阶中心性度量的分布，显示了两者之间的良好一致性。为了进一步说明我们计算框架的灵活性，我们考虑了高阶交互的时间维度。特别是在图1(F)中，我们展示了不同交互规模的时间自相关性，这是Ref. [79]中引入的用于表征高阶系统时间演变的测量方法之一。结果显示所有交互阶次都存在长程相关性，时间截止点取决于群体大小。除了结构分析，我们的库还允许研究多种高阶交互的动态过程。在这里，我们模拟了高中生中的高阶传播，采用了一种模型，其中感染个体的群体与高阶传染项相关联，此外还有传统的成对机制[60]。在图1(G)中，我们展示了两种配置下的感染节点比例随时间的变化，一种包含高阶感染，另一种不包含。如图所示，存在这种高阶项可能显著改变集体动态，将系统从健康状态推向流行状态。最后，在图1(H)中，我们呈现了高阶系统的直接超图可视化。为了简化起见，我们绘制了单一班级的个体，并显示了他们之间的所有统计显著交互[41]，包括两个、三个和四个个体之间的交互。

结论

随着新理论和方法的不断发展，高效算法和软件的开发在现代网络科学的进步中发挥了关键作用。在这里，我们介绍了HGX，一个多功能且强大的Python库，提供了一个灵活高效的框架来分析具有高阶交互的网络系统。其用户友好的环境和广泛的功能使其对实践者和研究人员都非常有用，可以解决各种需求和问题。未来，我们计划继续扩展HGX的工具集，探索多个新维度。例如，我们已经预见到将实现调查高阶系统在不同攻击策略下的鲁棒性工具。我们还将提供有效总结高阶信息和降低高阶数据维度的方法。我们计划包括用于从多变量时间序列构建和分析高阶依赖关系的工具[9]，以及捕捉冗余和协同高阶交互的信息理论度量[80]。此外，我们还计划扩展对高阶过程的覆盖，包括不同的进化博弈[62, 64]、生态动态[81]等。

我们希望HGX能够让所有处理网络数据的研究人员都能进行高阶网络分析，并邀请社区探索该库并进行贡献。