https://link.springer.com/article/10.1140/epjds/s13688-024-00458-1
The simpliciality of higher-order networks
高阶网络的简单性
摘要
高阶网络被广泛用于描述那些一次可以涉及两个以上实体的复杂系统。在本文中，我们专注于高阶网络中的包含性，这指的是特定实体参与交互，而这些实体的子集也相互交互的情况。传统的高阶网络建模方法往往要么完全不考虑包含性（例如，超图模型），要么明确假设完美和完整的包含性（例如，单纯复形模型）。为了更细致地评估高阶网络中的包含性，我们引入了“单纯性”的概念和几种相应的度量方法。与当前建模实践相反，我们展示了实证观察到的系统很少位于单纯性谱的任一端。此外，我们展示了拟合这些数据集的生成模型难以捕捉其包含结构。这些发现为高阶网络科学领域指明了新的建模方向。
关键词：高阶网络；超图；单纯复形；单纯性
1 引言
广泛的复杂系统是由涉及多个实体的交互塑造的：社交网络由群体行为驱动[1]，电子邮件通常有多个收件人[2-4]，细胞中的分子途径涉及多蛋白相互作用[5]，科学文章涉及合作者群体[6]。高阶网络是对网络的自然扩展，明确设计用于模拟这种多向关系[7]。
两种数学表示最常用于建模高阶网络：超图和单纯复形[8]。超图是实体（节点）通过交互（超边）连接的集合，这些实体的数量可以是任意的。单纯复形可以被看作是一种超图，它有一个额外的要求，称为向下封闭，即当m个实体之间存在交互时，所有可能的子交互也存在。这种数学构造起源于代数拓扑，并且是出于理论应用的动机；例如，形成边界矩阵这样的算子来识别数据集中的循环，或霍奇拉普拉辛算子来描述高阶网络中的动态过程[9, 10]。
最近的工作已经处理了为给定的复杂系统选择适当表示—单纯复形、超图或其他—的问题和后果。例如，参考文献[11]显示，由于单纯复形中包含的边驱动的同步，使用单纯复形和超图建模的系统之间的同步可能大不相同，而三项最近的研究调查了包含对传染的影响[12-14]。此外，参考文献[8]讨论了每种表示对应于不同的建模假设，因此，不同的分析流程。
这些研究中缺少的是分析高阶表示适合描述实际观察到的交互的适用性。当一组交互被提供给数据科学家或建模者时，表示的选择本质上是经验性的。数据是否满足向下封闭？（如果是这样，单纯复形可能最好地表示它。）或者数据违反了向下封闭？（如果是这样，它应该被建模为超图。）
在本文中，我们引入了单纯性的概念来描述一组交互满足向下封闭要求的程度。我们用三种衡量数据集整体单纯性的度量来实现这个概念，并描述了如何定义这些全局度量的局部版本。使用这些度量，我们调查了经验数据集的单纯性，并展示了通常分析的高阶交互数据集占据了单纯性的全部谱系。我们发现，根据选择的经验数据集和单纯性的度量，单纯性可能有大的变化。此外，我们展示了现有模型显示的单纯性水平通常不被现有的高阶网络生成模型所捕获。
因此，本文确定了当前高阶度量和模型集合中的一个重要差距。
这些新的单纯性度量补充了其他高阶结构度量，如社区结构[15-17]、中心性[18-20]、聚类[21, 22]、同配性[23, 24]和度数异质性[25]。虽然这些度量有助于理解高阶数据是如何组织的，但它们不解决超图与单纯复形的关系。最接近我们工作的是最近的参考文献[13]，其中作者描述了封装图，这是任何给定数据集包含模式的结构描述，以及基于包含的动态过程，从包含的超边传播到更大的包含超边。同样相关的是参考文献[26]，它定义了一个包含的全局度量。有大量文献围绕嵌套性的概念[27]，它衡量单一部分和双部分网络的包含结构，特别是在生态学背景中[28]。然而，嵌套性的度量并不使用单纯复形作为比较的参考点。相比之下，我们的方法用简单的全局度量简洁地描述了向下包含，为理解高阶数据是如何组织的提供了新的视角。
1.1 数学定义
2. 测量单纯性
本文引入了单纯性的概念。广义上，单纯性衡量了超图的包含结构以及高阶数据集与单纯复形结构的相似程度；见图1A。测量单纯性的方法有很多种，我们在第2.1节中将详细介绍这些方法。然而，在此之前，我们必须首先介绍相关术语。
2.1 测量
本节介绍单纯性的测量方法。我们遵循几个指导原则来设计这些测量方法。第一，单纯复形必须在任何单纯性测量中都是最大单纯的。第二，为了便于数据集之间的比较，单纯性测量应进行归一化，使其将超图映射到0到1之间的值。第三，如果向超图中添加一个子面，单纯性必须增加。第四，当数据集在定性上更接近单纯复形时，单纯性应该增加。第五，我们规定空超图的单纯性是未定义的。
有多种方法可以定义单纯性测量，同时保持这些指导原则。为了突出不同的结构元素对包含结构的贡献，我们定义了三种测量方法：单纯性分数、编辑单纯性和平均面单纯性。这些测量方法在图1 B-D中都有说明。
单纯性分数
在单纯复形中，每个子面本身都是单纯形，因此当一个超图是单纯复形时，它包含每个超边的所有子集。单纯性分数（SF）测量这种情况的程度，定义为也为单纯形的超边的比例。
单纯性分数 单纯性分数直接测量数据集中单纯形的数量，因此具有很高的解释性。然而，一个潜在的缺点是，几乎达到向下封闭的边在整体单纯性中完全没有计算。此外，这一定义对较小的单纯形权重较重，因为小单纯形会对所有包含它们的超边的单纯性产生贡献。
编辑单纯性 编辑单纯性（ES）定义为使超图成为单纯复形所需的最少边数（或在归一化情况下的比例）。
面编辑单纯性
最后，基于编辑单纯性的概念，我们定义了一个更局部的单纯性概念，使用必须添加的子面的数量，以使特定面成为单纯形。
我们称这种最后的度量为面编辑单纯性（FES）。
FES将面编辑距离标准化为其最大单纯性的一部分。这种标准化消除了在计算σES时大边的主导地位，并且实际上以指数方式降低了这些边的贡献。此外，由于这个度量是在面上计算的，这是一个平均的局部度量。
2.2 测量单纯性时的重要考虑因素
在我们转向第3节的应用之前，让我们讨论三个设计选择，这些选择可能会影响我们对数据集单纯性的结论。
首先，我们注意到，当使用单纯复形来表示完美的包含结构时，其正式定义可能过于严格。根据定义，一个单纯形总是包含单点集（由单个节点组成的边）和空集。由于构造原因，某些数据集可能不会包含这些交互。一个例子是邻近数据集，其中边表示在观察期间两个或多个节点变得接近的事件。由于其空间性质，这些数据集通常非常密集，并包含许多包含关系[7]。然而，根据标准定义，由于缺乏单点集，它们永远不会是单纯复形。另一个例子是电子邮件数据集，这些数据集也不包含单点集，除非包括个体发送给自己的电子邮件。由于我们将包含的概念定义为单纯复形，我们的测量方法将这些数据集标记为没有任何包含结构。
为了解决这个问题，我们使用了一个放宽的向下封闭定义，该定义在合适的情况下排除了单点集。这个放宽的定义使用了大小限制幂集 的概念，其中K 是一个整数集合，定义为：
请注意，这种设计选择与通过修改的幂集（见公式 (4)）施加的大小限制不同；在那个背景下，我们主张忽略那些可能阻止其他边成为单纯形的边，而在这里，我们建议将最小面计入潜在单纯形将会强烈影响单纯性值。我们的策略如下：
对于单纯性分数（SF），这意味着 S 和 E 都排除了最小大小的边。
对于编辑单纯性（ES），我们在构建最小单纯复形时排除那些同时是最小面的最大面。
对于面编辑单纯性（FES），我们仅对那些不是最小面的最大边进行平均。
第三，最后，由于超边的潜在子面的数量随着其大小呈指数增长，计算问题阻止我们将我们的测量应用于大型超边。因此，我们选择一个最大面大小k（在整个过程中我们使用
2.3 局部单纯性
3 结果
3.1 实证数据集
作为单纯性度量的首次展示，我们分析了来自几个一般领域的实证高阶数据集。所有数据集均从 xgi-data 数据库[31] 获得，并公开可用。根据第2.2节中强调的考虑因素，我们对这些数据集进行了预处理，移除了单点集、多重边和孤立节点。此外，为了计算的可行性，我们仅考虑大小为11的超边（阶数，即大小减去1，为10）及更小的边。预处理数据集的基本结构属性见表1。
我们的数据集样本包含了各种复杂系统。我们分析了三个接触数据集 [1, 2, 31–33]（contact-primary-school、contact-high-school 和 hospital-lyon），这些数据通过接触传感器收集，传感器的范围大约为 1 米。节点是个人，当两个人的距离小于 1 米时，会创建一个边。为了创建一个高阶数据集，每个最大团在每个时间步长都被转换为一个超边。接触数据集的独特之处在于它们的几何约束，由于接触传感器的范围，5-超边是这些数据集中存在的最大边。我们还包括了两个电子邮件互动数据集 [2–4, 34]：email-enron 和 email-eu。在这两种情况下，节点是电子邮件地址，超边是电子邮件，在前者的情况中，超边来自已解散的公司 Enron，后者来自一个大型欧洲研究机构。三个数据集与生物过程有松散的关联 [2, 35, 36]：diseasome、disgenenet 和 ndc-substances。在这些数据集中，节点是化合物、疾病或基因，而超边是这些之间的相互作用，用以表示药品、症状和疾病。最后，我们还包括了两个杂项数据集：tags-ask-ubuntu [2]，这是一个高阶数据集，其中节点是 Stack Overflow 上的标签，边是与这些标签相关的问题；以及 congress-bills 数据集 [2, 37, 38]，其中节点是国会议员，边代表某一法案的发起人和共同发起人。
这些数据集的单纯性度量的数值见表1。我们发现，不同数据集的单纯性值填满了从 0 到 1 的范围。接触数据集在所有三个度量下具有较大的单纯性，而生物数据集在所有三个度量下都具有较低的单纯性。电子邮件数据集的 ES 单纯性非常小，而其他两个度量则有中等的单纯性。（由于我们使用大小限制来排除单点集，因此缺少或没有发送给自己电子邮件的情况不会影响此评估。）类似地，tags-ask-ubuntu 数据集的单纯性值取决于我们考虑的度量。这表明，我们在第2.1节中定义的度量捕捉了包含结构的不同特征。
虽然这些度量给出了每个数据集的不同视角，但我们通过相关性分析验证了它们的大致一致性。SF 和 ES 之间的皮尔逊相关系数为 ρ = 0.97，SF 和 FES 之间为 ρ = 0.95，ES 和 FES 之间为 ρ = 0.90（所有显著性水平为 p = 0.001）。因此，在我们的样本中，这些值是紧密且线性相关的。它们还以相似的方式对数据集进行排序，从最少到最多的单纯性，因为 SF 和 ES 之间的斯皮尔曼等级相关系数为 ρ = 0.89，SF 和 FES 之间为 ρ = 0.997，ES 和 FES 之间为 ρ = 0.90（所有显著性水平相同）。
虽然我们的相关性分析确认这些度量大致捕捉了相同的概念，但它们在不同数据集上的差异突显了它们的关键区别。在我们的实验中，这些差异是由于大边含有很少包含边、许多边大多是闭合向下的以及不同的边大小分布等特征所致。组织电子邮件消息的网络是第一种情况的例子，在这种情况下，可能会发送非常大的组织或部门范围的电子邮件，但不能保证电子邮件也会在每个可能的子群体之间发送。在这种情况下，我们期望 ES 极低，而 SF 不必低。接触网络是第二种情况的例子，即密集的向下闭合数据集。我们通过注意到 SF 不为 1，而 ES 和 FES 接近 1 来看到这一点，因为 SF 对几乎单纯的边施加了惩罚。最后，边大小分布对所有度量有强烈的影响；对于相同的平均边大小和边数量，增加小边和大边的数量都会影响 SF 和 ES 度量。对于 ES，大边会指数性地增加创建单纯复形所需的子面数量，从而将单纯性驱动到零。相比之下，增加小边的数量可以创建更多的小单纯体，增加 SF。
3.2 高阶网络的生成模型
为了补充对实际数据的分析，我们还检查了使用生成模型生成的合成数据的单纯性。
我们重点关注旨在描述和分析任意高阶结构的超图模型。有几种随机超图模型，包括优先附着模型 [39–42]、具有社区结构的模型 [15, 43–46]、具有指定度数和大小序列的模型 [23, 43]、Erdös-Rényi 模型 [47, 48]、具有潜在节点变量的模型 [49] 和几何模型 [42, 50, 51]。常用于拟合实际数据的高阶随机模型包括配置模型 [23]、二分 Chung-Lu 模型 [23, 43] 和二分度修正随机块模型 [52]。参见文献 [7] 以获取详尽的概述。生成的超图模型通常缺乏对超边包含结构的明确控制，因此通常只有相对较少的单纯体。
我们将分析重点放在三个模型上：配置模型 [23]、二分 Chung-Lu 模型 [43] 和二分度修正随机块模型（biSBM）[52]。
我们将每个模型拟合到表1中的实际数据集，使用拟合的模型生成一系列高阶网络（在贝叶斯术语中为后验预测分布），并分析生成的单纯性值的分布。
在所有情况下，当从这三种生成模型中采样合成高阶网络时，我们为每个实际数据集生成了次每种模型的实现。我们使用文献 [23] 中提出的双边交换算法从配置模型中采样，并执行了 10 × |E| 次边交换，粗略符合文献 [53] 的要求。对于二分 Chung-Lu 模型 [43]，我们提取了度数和边大小序列，然后使用文献 [54] 中介绍的二分变体算法（在 XGI [55] 中可用）从该模型中采样。最后，在从 biSBM 采样时，我们使用了 Markov 链 Monte Carlo 方法和二分先验，使用了文献 [52] 中描述的算法。
所有结果均报告在图 2 中。我们可以明显看到，当数据集具有非平凡的包含结构时，生成模型无法准确捕捉单纯性。虽然生成的值不完全正确，但超图配置模型始终比 biSBM 和二分 Chung-Lu 模型更好地捕捉了包含结构，这与使用的单纯性度量无关。这可能是由于度数和边大小序列的精确指定；Chung-Lu 模型和 biSBM 仅在期望上匹配这些序列。
3.3 单纯性的局部度量
作为最后的展示，我们将我们的局部单纯性度量应用于 Enron 员工发送的电子邮件数据集（142 个节点和 1126 个超边，筛选以包括大小为 2 和 3 的交互）。结果见图 3。
首先关注直方图，我们发现 SF 具有最大的变异性，而 FES 也覆盖了类似的范围。相比之下，ES 告诉我们几乎每个邻域都是强单纯的。这是预期的行为，因为 ES 依赖于在自我超图上诱导的单纯复形；这个自我超图中的最大超边的大小可能比整个超图中的最大超边要小得多。因此，方程 (2) 的分母减小，从而系统地增加局部 ES。相反，当我们选取一个节点子集以形成自我超图时，很容易遗漏由许多超边共享的小子面，从而导致 SF 和 FES 非常小。
从插图中显示的空间分布来看，我们看到 SF 和 FES 在网络核心区域发现了高单纯性区域，而在边缘区域则发现了低单纯性区域。实际上，这两个度量在很大程度上是一致的，局部 SF 和 FES 之间的 Pearson 相关系数为 ρ = 0.84。（当比较 SF 和 ES 时，相关系数下降到 ρ = 0.69）。我们还观察到几个节点的单纯性是未定义的。这些节点仅通过自我超图中的最小面连接，而在计算潜在和实际单纯体时，这些最小面被排除在外。
最终，检查图 3 时，我们注意到在这种情况下，具有相似单纯性节点往往相互连接。为了量化这一观察结果，我们定义了单纯性同配性（simplicial assortativity），即由至少一条超边连接的节点对的单纯性 Pearson 相关系数。更正式地，我们使用超图的无权邻接矩阵 A，定义为：
在 tags-ask-ubuntu 数据集中，FES 显示出弱同配性，而其他两个度量显示出弱异配性。特别引人注目的是，尽管 hospital-lyon 数据集在图 2 中表现出高度的单纯性，但它也显示出弱异配性。
结论
在本文中，我们引入了总结超图包含结构（即单纯性）的度量方法。我们展示了三种单纯性度量方法，但也认识到其他定义的单纯性可能同样有用。我们讨论了高阶数据集的单纯性如何依赖于许多因素，包括数据集的收集方式、领域和单纯性度量方法。在将常见的生成模型拟合到多个实证高阶网络时，我们发现原始数据集的单纯性通常高于任何度量的拟合模型的后验预测分布的单纯性。单纯性同配性测量表明，单纯性表现出不同程度的局部化。
我们希望这项研究能成为网络科学家在描述高阶网络数据集时的起点，并期待未来在多个感兴趣的维度上发展这些方法。
首先，我们展示了全局和节点级别的单纯性定义，但其他交互尺度可能会提供对数据包含结构的进一步见解 [27]。未来的工作可以探索描述例如单纯性在社区之间如何变化的中尺度单纯性度量。还可以获取超图中的最大单纯性组件或单纯性组件集。此外，我们限制在无权单纯性复合体，但可以考虑将这些概念扩展到加权单纯性复合体 [57]。
其次，我们的方法补充了关于二分网络中的嵌套性 [27] 的现有文献，这些文献表明，嵌套性存在于各种单层和双层网络中 [58]。现有工作表明，嵌套性对许多领域的网络功能至关重要 [28, 59–61]，从单纯性的角度比较这些发现可能会从结构和机制角度提供额外的见解。
最后，我们展示了人工数据集和观测数据集之间的单纯性差异。因此，我们的发现应当指导新的高阶网络模型，这些模型需要指定网络的包含结构，并能够拟合到实证高阶数据集。
