Hypernetwork Science via High-Order Hypergraph Walks

通过高阶超图行走的超网络科学

https://arxiv.org/abs/1906.11295

摘要

我们提出了高阶超图游走作为一个框架，将基于图的网络科学技术推广到超图上。超图中的边关联是定量的，从而产生具有长度和宽度的超图游走。然后可以推广到超图的图方法包括连通分量分析、基于图距离的度量（如接近中心性）以及基于模式的度量（如聚类系数）。我们将这些方法的高阶类比应用于现实世界的超网络，并展示它们揭示了图基方法无法检测到的微妙且可解释的结构。最后，我们将三种生成模型应用于数据，并发现基本的超图属性，如密度和度分布，并不一定控制这些新的结构度量。我们的工作展示了当使用专门设计的工具捕捉超图特有的现象时，对超图结构数据的分析更为丰富，并为实现这一目标提出了一条可能的途径。

1 引言

在复杂系统的研究中，图论通常被视为网络科学的数学基础[7]。在生物学、社会学、电信和物理基础设施等领域研究的系统，通常可以表示为一组实体（“顶点”）和二元关系（“边”）的集合，并且可以使用图论方法进行分析。图模型从简单性和一定程度的普遍性中受益。但作为抽象的数学对象，图限于表示实体之间的成对关系。然而，这些系统中的现实世界现象可能在多方面关系丰富，涉及两个以上实体之间的交互、两个以上变量之间的依赖或两个以上对象集合的属性。

超图是图的推广，其中边可以连接任意数量的顶点，从而表示k-way关系。因此，超图是包括上述多方面关系的广泛系统的自然表示。实际上，超图结构化数据（即超网络）无处不在，每当信息自然呈现为集合值、表格或二分数据时都会发生。此外，作为有限集合系统，超图与数据科学中其他重要的数学结构有关联，包括有限拓扑、单纯复形和施佩纳系统。这使得可以使用更广泛的数学方法，例如计算拓扑中的方法，来识别超网络中特有的高维复杂性特征，而这些特征在使用图时是不可用的。尽管越来越多的研究表明基于超图的分析的效用增加，但许多网络科学方法历来是明确（并且通常，仅）为基于图的分析而开发的。此外，常见的情况是，来自超网络的数据被简化为图。

在继续之前，让我们考虑一个例子。图1展示了两个作者-论文数据集，它们可以自然地被结构化为超图，通过将作者表示为顶点，每个论文上出现的作者集合表示为超边。1 从最右边的网络派生的超图通过有3位作者的论文表现出高阶关系。比较这些示例突出了图和超图表示之间保留和丢失的结构信息。例如，两个网络在每对作者A、B、C都合著了一篇论文（事实上，正好两篇论文）方面是相似的。这被合著图（中间）捕获，因此对于这两个网络是相同的。然而，还有图中表示未捕获的明显差异。例如，每个作者出现在4篇与2篇论文上，每篇论文分别有2位与3位作者。除了这些基本计数之外，这些网络还表现出更微妙的差异：在最左边的网络中，任何一对作者合著的论文集合与任何其他作者对的联合论文集合不同，而在最右边的网络中，每一对作者都合著了完全相同的论文集合。正如这个玩具示例所示，虽然图确实捕获了超网络的一些属性，但它们不足以作为超图的替代品。

尽管图和超图分析之间存在这种不一致性，有效地将图论工具扩展到超图有时落后或难以捉摸。这方面的一个关键方面是公理化：作为一般化，有许多可能的超图概念的定义集，有时是相互不一致的，当实例化为图情况时，可以产生与图论一致的结果。在某些情况下，开发任何连贯的超图类比都面临着重大的理论障碍。例如，将图邻接矩阵的谱理论扩展到超图立即面临挑战，因为超边可能包含多于两个的顶点，从而使常规的（二维）邻接矩阵不足以编码邻接关系。在其他情况下，图论概念可以轻易地扩展到超图，但在这样做的过程中忽略了超图特有的结构细微差别，这些细微差别在图中是不可见的。例如，虽然边关联和顶点邻接在图中最多可以在一个顶点或边上发生，但这些概念对于超图是集合值的，因此是定量的。因此，虽然随后基于图游走的概念，如连通性，立即适用于超图，但它们在未能考虑到与超图游走相关的不同“宽度”时忽略了高阶结构。

由于这些挑战，寻求工具研究超图结构化数据的科学家经常不得不应对超图研究的不同方法。处理超图复杂性的一种方法是将注意力限制在只有统一大小边的超图上，这些边包含相同数量的顶点。数学文献中的许多超图研究，如超图着色[24, 50]、前述的超图谱理论[16, 21]、超图横截[4]和极值问题[70]，只关注这种k-uniform情况。虽然这种假设加强了对所讨论超图的数学复杂性和结构上的忠实分析，但遗憾的是，现实世界的超图数据很少是k-uniform的。因此，这些工具在缺乏适用性方面存在问题，无法适用于真实的超网络数据。另一种超图研究方法是将注意力限制在（潜在的非统一）超图到图的转换上。有时称为超图线图、2-section、团扩展或单模态投影，这样的转换显然能够将图论工具应用于数据。然而，毫不奇怪，这种超图到图的简化不可避免地是有损失的[23, 46]。因此，尽管提供了简单性，但这种方法在揭示超图结构方面的效用有限。

为了使对超网络数据的分析更好地反映其复杂性，但仍然可行且适用，我们认为在忠实度和简单性之间的权衡中找到平衡是至关重要的。本着这一目标，我们在高阶超图游走的框架下，将网络科学中流行的一些图分析工具扩展到超图。我们将超图游走描述为“s-walk”，其中阶数s控制最小游走“宽度”在边重叠大小方面。高阶s-walks（s > 1）在超图上是可能的，而在图上，所有游走都是1-walks。我们开发的基于超图游走的方法包括

连通分量分析、

基于图距离的度量（如接近中心性）和

基于模式的度量（如聚类系数）。由于这些方法基本上基于图论的游走概念，我们通过使用超图游走将它们扩展到超图。最终，我们的目标不仅是以一种连贯的方式制定这些概括，而且要探究这些工具是否揭示了真实超网络数据中普遍且有意义的结构。

为此，我们基于来自不同领域的三个真实数据集的超图游走计算了这些度量，并讨论了结果。

我们的工作组织如下：在第2节中，我们提供了背景定义，并回顾了与超网络理论相关的预备主题。在第3节中，我们定义了支撑我们后续工作的s-walk概念，讨论了相关先前研究，并重申了我们的贡献。在第4节中，我们引入了基于s-walk的分析度量，将它们应用于前述数据集，并分析了结果。在第5节中，我们考虑了三种生成性超图模型，并实验性地测试了第4节中观察到的结构属性在多大程度上可以由合成模型复制。最后，在第6节中我们总结并概述了几个未来研究方向。

2 预赛

超图是图的推广，其中边可以将任意数量的顶点连接在一起。

正如“网络”一词通常用来指产生图结构化数据流的过程或系统一样，我们将使用“超网络”一词来指产生超图结构化数据的系统。

更正式地，我们定义超图如下：

用超图的语言等价地表述：尽管非同构，由S和R表示的超图的加权线图，以及它们的对偶超图的线图，都是相同的。

Kirkland还构建了这样一对超图的无限家族，并表明它们构成了超图的极小比例。因此，虽然在经验数据中不太可能遇到这样的超图对，但Kirkland的工作说明了即使同时考虑超图的对偶性和使用加权线图，超图的结构属性也可能丢失。

因此，根据所考虑的属性，线图忠实地表示超图的程度可能不清楚。尽管如此，研究人员已经提供了初步证据，表明从它们的线图中可以提取出一些有意义的、尽管是不完整的超图结构[28]。

最后，如[53, 73]中所指出的，超图线图的另一个重要限制是计算上的：稀疏的超图仍然可能产生相对密集的线图，这些图可能难以分析或存储在计算机内存中。通过观察超图中的k路边交点（由度为k的顶点保证）在其线图中产生 ( k 2 ) 条边，这一点可以很容易地看出来。特别是如果超图很大，它的顶点度数和边基数分布严重倾斜（现实世界网络数据中的常见特征），它的线图可能太密集而无法计算分析或甚至根本无法构建。

3 从图游走到超图游走

图论中最基础的概念之一，支撑着包括哈密顿图和欧拉图、距离和中心性度量、图上的随机过程和PageRank在内的众多领域，就是游走的概念。对于图，长度为k的游走是一系列顶点 ，使得每对连续的顶点都是相邻的。根据（简单）图的定义，两个相邻的顶点恰好属于一条边，反之，两条相交的边恰好在一个顶点处相交。因此，任何有效的图游走可以等价地表示为一系列相邻顶点的序列，或者作为一系列相交边的序列，即

在超图的背景下，这种简单的观察不再适用。超图中的边缘关联和顶点相邻性是集合值和定量的，因为两个超边可以在任意数量的顶点处相交，而两个顶点可以属于任意数量的共享超边。这引发了两种关于超图的路径概念，它们既对偶又不同：顶点层面的路径（由连续相邻的顶点组成）和边缘层面的路径（由连续相交的边缘组成）。为了方便叙述，并与相关的先前工作保持一致，我们将讨论限制在边缘层面的超图路径。然而，当考虑对偶性时，这两种概念都被捕捉到，因为在超图 H 上基于顶点的路径只是其对偶超图 H∗ 上的边缘路径。我们定义超图路径为超图上的“s-路径”，其中 s 控制边缘交集的大小，定义如下：

在超图的解释中，s-游走对应于一系列相邻顶点的序列，其中每对连续的顶点至少属于s个共享的超边。由于在图中，一对顶点最多只能属于1条边，所以在图G上的顶点x和y之间的常规图游走等同于在对偶图G*上的超边x*和y*之间的1-游走。因此，s=1的情况恢复了常规的图游走，而s>1的s游走只能在超图上实现。

在后续部分中，一系列基本但重要的图游走属性将立即扩展到超图上的s游走。例如，就像任何以顶点vk结束的图游走都可以与以顶点vk开始的任何游走连接起来形成另一个游走一样，任何以特定边结束的s游走都可以连接到从该边开始的任何其他s游走。因此，超边之间存在s游走定义了一个等价关系，根据这个关系，超边可以被划分为s连通分量，这将在第4.2节中探讨。此外，这也确保了边之间最短s游走的长度，称为s距离（第4.3节），满足三角形不等式，并在超图上定义了一个真正的距离度量。最后，在第4.4节中，我们探讨了如何以层次化的方式区分不同类型的s游走，以及随后的s迹、s漫步、s路径和s循环的概念如何有助于识别超图特有的子结构，如s三角形。对于对超图上的随机游走感兴趣的读者，附录A简要讨论了近期文献及其与s游走的关系。

先前的工作：许多研究者考虑了在超图、抽象单纯复形和相关集合系统上的“高阶游走”的不同概念。与s游走密切相关的概念在数学文献中早已出现。Bermond、Heydemann和Sotteau[10]引入并分析了均匀超图的k线图，这些图是通过将每个超边表示为顶点，并在它们的对应超边至少在k个顶点上相交时将这两个顶点连接起来，从超图中派生出来的。通过这种方式，他们线图上的（图）游走对应于超图上的s游走。在[56]中，Lu和Peng为k一致超图定义了高阶游走，作为在恰好s个顶点上相交的边序列，其中每个边内的顶点都是有序的。他们的工作与k一致超图中哈密顿回路的丰富文献相关（例如[38, 45]），并采用了谱方法：这些广义游走被用来定义所谓的s-Laplacian矩阵。Wang和Lee[76]定义了超图路径为边序列，其中没有连续的交点是另一个的子集。他们的动机是为某些超图中的循环结构证明枚举公式。在[20, 18, 19]的三篇近期论文中，Kang、Cooley、Koch等人考虑了顶点s元组之间的s游走概念。他们对二项随机k一致超图的渐近s游走属性进行了严格的数学分析，考虑了击中时间、高阶s组件的演化和高阶“超树”结构。最后，在[42, 67]中，本论文的作者简要考虑了s游走基于s距离的概念，分别应用于域名系统（DNS）网络数据和Enron电子邮件数据集。

贡献：本工作的主要贡献是：

• 使用s游走框架开发超图的图网络科学度量的推广，

• 将这些新度量应用于真实的超网络，分析和比较结果，讨论它们揭示的结构见解，

• 通过实验测试现有的生成性超图零模型在多大程度上能够复制这些度量在真实数据中捕获的属性。

为了清楚地说明这些新的超图度量是如何推广它们的图对应物的，在适当的时候，我们包含了一个称为“图情况和等价性”的定义副标题。这个副标题解决两个不同的问题：首先，它描述了当超图是图时，所讨论的定义如何简化为图情况。正如我们将看到的，大多数提出的超图度量通过取s=1并检查图的对偶G*（取对偶将我们基于边的解释转换为网络科学中常见的基于顶点的概念），就可以简化为图类比。

其次，这个标题描述了超图度量是否等同于超图的s线图（定义7）上的图度量，这是前述线图的概括。在s连通分量和s距离度量（第4.2-4.3节）的情况下，它们在s线图上有自然的等价性，因此可以通过s线图获得。然而，s路径、s周期和s聚类系数（第4.4节）依赖于子集信息，这些信息没有编码在s线图中，因此也无法从s线图中辨别出来。此外，我们考虑的超图生成模型的属性，例如超图度数分布和变形系数，也无法从s线图中确定。从这一点可以得出，我们对s游走和超网络科学的研究包括但不限于s线图的研究。

最后，我们简要比较了我们的方法与上文“先前工作”中调查的相关研究：虽然当前工作同样基于高阶超图游走的概念，但我们利用它们达到不同的目的。特别是，我们使用这个框架开发针对混乱的真实超图数据的网络科学概念。与上述所有工作不同，除了Wang和Lee[76]之外，我们不假设k一致性，因为真实的超网络经常是非一致的。此外，我们的方法适用于断开连接的超图，并允许复制超边——这两种情况在真实数据中也很常见。此外，我们做出设计选择以确保我们的方法在面对超图中固有的组合爆炸时更具计算可行性。例如，与Lu和Peng不同，他们定义了任意有序s元组顶点之间的s游走，我们定义了无序超边对（或者在处理对偶时，单个顶点对）之间的s游走，这允许开发在应用真实数据时更可行的方法。

4 超图游走框架

在本节中，我们将探讨网络科学分析工具如何在超图游走框架中扩展到超图。在每个子部分中，我们专注于一个主题（例如s距离，超图测地线），并在“方法”部分中介绍相关方法。在“数据应用”部分中，我们将这些方法应用于真实的超网络并分析结果。我们的目标不是使用特定领域的分析来解释观察到的结构存在的原因。相反，我们识别这些度量揭示的抽象结构属性，并强调这些属性在每个数据集中（当我们改变游走顺序s时）以及跨数据集时的差异。这展示了这些度量捕获的特定属性，以及通过考虑基于s游走的度量揭示的新见解。虽然我们在这里采取了更广泛的方法论观点，但我们相信这种方法在未来在多个领域中指导这些方法的应用特定研究方面可能更有用。为此，我们考虑了来自三个领域的三个数据集：公司治理、生物学和文本分析。

4.1 测试数据集

对于每个数据集，我们定义了相关的超图，回顾了这些（或密切相关的）数据集的先前图或超图分析，并讨论了在图3中总结的基本属性。在本图和全文中，我们使用与定义4中相同的符号来引用与数据集相关联的对偶超图（例如，LesMis*指的是LesMis的对偶超图，在其中顶点和边的角色相对于下面定义的方式进行了交换）。图3绘制了边基数分布和成对边交集中位数分布。例如，“边”分布上的点(x, y) = (3, 100)表示有100条边恰好由3个顶点组成；“成对边交集中位数”分布上的同一点表示有100对不同的、无序的超边，它们的交集中恰好有3个顶点。我们提醒读者，对偶超图H*的边基数分布与H的顶点度数分布相同。

图3中的表格突出了每个超图的基本统计数据。"多边"的数量是指在集合相等意义上复制（即|{i : ei = ej for j < i}|）另一个边的边的数量。最大边大小和边交集中位数，在多边计数下方报告，特别相关，因为它们决定了我们度量的范围：前者决定了定义s游走基于度量的最大s值，而后者决定了s游走基于度量是非平凡的最大s值。最后，“密度”度量相对于可能的顶点-超边成员关系数量的顶点-超边成员关系数量。换句话说，这是关联矩阵S中非零项的数量除以|V| · |E|的乘积。根据定义，密度对于超图及其对偶总是相同的，而其他报告的值是基于边的，可能会有所不同。

CompBoard 数据集。一个公司-董事会网络。顶点代表人员，超边代表公司董事会。如果一个人在公司董事会上任职，则该顶点属于一个超边。数据包括4573家公司和32,189人。公司通过在2018年10月1日的NYSE、AMEX和NASDAQ股票交易所上市8中不包括任何位置或交易所代码后缀的标记符号来识别（例如，Vodafone集团仅由VOD代表，而不是VOD.L或VOD.O）。

数据是从Reuters公开可用的9董事会董事信息中收集的。董事会董事的姓名与年龄数据进行了交叉引用，以更好地区分具有相同全名的不同人员。

先前的工作。公司-董事会网络研究在历史上植根于公司精英理论，关注拥有共同董事会成员的公司，称为交叉董事会。许多这样的研究集中在网络的线图表示上，将董事会交叉的公司联系起来。例如，Conyon和Muldoon[17]研究了美国、英国和德国公司-董事会网络的小世界属性，重点关注线图的聚类系数和平均路径长度。在[63]中，Newman将公司-董事会网络线图的聚类系数与随机模型进行了比较。10 Levine和Roy[55]似乎是最早直接分析公司-董事会网络的二分表示而不是仅线图的人之一。他们考虑了平均路径长度、连通分量大小等主题，并提出了一个“橡皮筋模型”11来聚类二分网络。后来，Robins和Alexander设计了一种基于二分4-环与3-路径比率的二分全局聚类系数，以衡量“董事们在两个或更多董事会上重新相互遇见的程度”[68]。在第4.4节中，我们提出了一种新的超图聚类系数概念，并解释了它与Robins和Alexander以及在线图上测量的图聚类系数的比较。更一般地说，由于“交叉董事会”由超边交点表示，我们的方法可以在这个背景下解释为不仅基于交叉的存在（即纯粹的线图分析），而且基于它们的大小和相对集合关系。

基本属性。边大小分布显示，公司董事会的规模紧密集中在7-10名成员左右，两端急剧下降：只有约3%的公司少于4名成员，3%的公司有超过14名成员。相比之下，对偶超图的边大小分布单调递减，显示超过99%的董事会成员属于1-3家公司董事会。超图及其对偶的成对边交集中位数分布同样表现出急剧下降，这些分布的范围意味着不同的公司最多共享12名董事会成员，而不同的成员最多在5个共同的公司董事会上任职。在三个数据集中，CompBoard是最稀疏的：它包含大约0.03%的可能顶点-超边成员关系，而Diseasome和LesMis分别为0.33%和2.68%。

Diseasome 数据集。

来自[33]的人类基因-疾病网络。顶点代表基因，超边代表遗传疾病。如果一个基因的突变与一种疾病有关，则该顶点属于一个超边。数据包括903个基因和516种疾病。

先前的工作。Goh等人[33]在2005年从在线门德尔遗传继承人（OMIM）[37]汇编中收集了基因、疾病及其关联的列表。他们的研究考虑了超图及其对偶的线图，他们称之为人类疾病网络和疾病基因网络。他们展示了这些网络中最大连通分量的大小与随机模型生成的有所不同。在第4.2节中，我们研究了高阶连通分量的一般概念，并在第5.1节中将这些与随机超图模型进行了比较。有关在生物学和基因组学中应用超图和超图统计的潜在应用的更广泛讨论，请参阅[47]。

基本属性。Diseasome及其对偶的边大小分布显示，一个疾病涉及的基因最多为41个，而一个基因涉及的疾病最多为11个。成对边交集中位数分布显示，94%的疾病对涉及共同基因的疾病共享确切的1个基因；反之，检查对偶超图的这一分布揭示了98%的基因对与共同疾病相关的确共享确切的1个疾病。在三个数据集中，Diseasome及其对偶具有成对边交集中位数范围最窄，最大边大小分别为5和4。

LesMis 数据集是一个角色-场景网络，来自文献[48]。顶点表示角色，超边表示维克多·雨果小说《悲惨世界》中的场景。该数据集中有80个角色和402个场景。

前期工作 这个数据集由Donald Knuth [48] 收集，并可以根据不同的粒度结构化，其中超边表示小说中的场景、章节、书或卷。LesMis超图的线图，通常被称为Les Mis共现网络，经常出现在网络科学文献中，用于演示聚类或模块化方法 [31, 62]，或中心性和排名方法 [5]。对于后者，我们在第4.3节中应用我们提出的超图中心性度量来对LesMis角色进行排名。

基本属性 在LesMis及其对偶图中，最大的超边分别具有9个角色和137个场景，后者（毫不意外地）对应于主人公冉阿让。与其他数据集相比，LesMis的边交集大小分布特别明显。LesMis∗ 具有所有数据集中最广泛的边交集大小范围。LesMis及其对偶图还以其相对于可能的边交集数的边交集数量最多而著称：分别有22%和8%的LesMis及其对偶图中的边对相交，而对于Diseasome及其对偶图，这个比例小一个数量级，而对于CompBoard及其对偶图，这个比例小两个数量级。

4.2 连通分量

方法 根据定义1，图的连通性和连通分量的概念自然扩展到s-路径框架。

虽然超图H的s连通分量是边的等价类，但通过对偶超图H简单地应用上述定义，就可以得到基于顶点的s连通分量概念。在比较这些基于边和基于顶点的概念时，注意H和H的1连通分量的数量总是相同的：在任一情况下，都很容易看出，这些分量的数量与超图的二分图表示中的非平凡连通分量（即不包括孤立顶点）的数量相同。在这个意义上，当s=1以及H是图的时候，基于边和基于顶点的连通性是等价的。然而，对于s ≥ 2，H和H*的s连通分量的数量可能会有所不同。因此，超图中的s连通性在高阶时更丰富、更多样化，产生了对偶但不同的基于顶点和基于边的概念。

通过其s线图来可视化和研究s连通分量的基本属性是一种有效的方法。正如之前提到的，Bermond、Heydemann和Sotteau[10]早在1977年就对k一致超图的s线图进行了研究。一般情况的定义可以陈述如下：

换句话说，s线图中的每个顶点代表了一个在超图中至少有s个顶点的超边，如果它们对应的超边在超图中至少在s个顶点上相交，那么s线图中的两个顶点就被连接起来。通过这种方式，1线图就是定义4中的线图，而s线图的连通分量代表了超图的s连通分量。因此，我们有：

4.3 距离和中心性

方法 在定义1下，很容易证明最短s游走的长度作为一个距离度量函数适用于一组超边。更准确地说：

在应用定义8到实际数据时，会出现一些重要的警告。正如我们所观察到的，对于某些s的值，H可能包含多个s分量，这种情况下某些边对之间的s距离是无限的。因此，每条边的s偏心率（以及s直径和s半径）和平均s距离都是无限的；同样，每条边的s接近中心性显然是0。类似于有时如何处理图的这些问题，一种选择是在仅最大的s分量上计算这些度量。根据分析者的目标，这种方法可能是令人满意的，特别是如果Es中的大多数超边包含在最大的s分量中，就像在LesMis*中似乎的情况一样。

然而，如果最大的s分量并不构成Es中边的绝大多数，如CompBoard对s ≥ 2的情况，限制在最大分量可能就不满意了。在这种情况下，人们可能希望在每个分量的基础上计算s偏心率，将所有s分量的极值作为s直径和s半径。同样，可以按分量计算平均s距离或s接近中心性，但不清楚如何正确地综合这些值，以便在前一种情况下获得单一的全局数值度量，或在后一种情况下获得整个网络中超边的排名。与其按分量的方法，Newman [61] 提倡使用倒数的调和平均值而不是算术平均值，这是一种优雅的替代方法，用于在断开连接的图中平均图距离。这种方法被Latora和Marchiori [54] 采用，用来定义网络效率作为倒数的调和平均路径长度，作为小世界性的定量度量。Latora和Marchiori将这种度量称为“效率”，指的是信息可能在网络上交换的效率。后来，Rochat [69] 类似地采用这种方法来定义断开连接的图中顶点的调和接近中心性指数。将这些概念扩展到超图背景中，上述基于s距离的概念的更实用定义由以下给出：

4.4 路径、循环与聚类系数

方法

到目前为止，我们的方法主要围绕着 s s-游走的基础定义。然而，正如图的游走可以被进一步区分为更细的类别，如径迹、路径、回路和循环， s s-游走也可以相互区分并组织成层次结构。正如我们将展示的那样，这样做可以定义原生于超图的高阶子结构，如 s s-三角形，这些子结构无法从它们的 s s-线图中确定。

5. 与生成超图空模型的比较

图生成在科学各个领域中具有广泛的用途。生成图模型用于基准测试、算法测试以及创建替代图以保护受限数据的匿名性。在这里，我们应用超图生成模型作为空模型，实验性地测试第 4 节中探讨的高阶属性的显著性。所谓“空模型”，指的是控制数据某些基本特征的生成模型。这些模型可用于测试数据中的观察测量是否必然与控制特征一致。例如，在 Erd˝os–R´enyi 图模型中，用户指定所需的顶点数 n 和边的概率 p；因此，通过控制 n 和 p，可以生成具有相同期望边密度的随机图集。随后，将给定图数据上的测量与具有相同边密度的随机图上的测量进行比较，以测试所测特征是否可以解释为边密度的唯一结果。在实际中，如果真实图和合成图的性质存在差异，这提供了证据表明这些属性不能仅仅解释为模型保留的结构属性的结果。

与图的对应模型相比，生成超图模型相对较少。虽然对随机均匀超图的研究可以追溯到至少上世纪 70 年代，研究人员最近开始开发更多种类的超图模型，包括均匀超图 [20, 18, 19, 65] 和非均匀超图 [14, 22, 23, 32, 43]。我们考虑了 [3] 中的三种生成超图模型，它们可以被视为图模型 Erd˝os–R´enyi (ER) [26]、Chung–Lu (CL) [15] 和 Block Two-Level Erd˝os–R´enyi (BTER) [49, 75] 的超图解释。这些模型最初被称为“二分模型” [3]，与第 2 节中讨论的双色图-超图对应关系相似。虽然这些模型受到其图对应物的启发并以此命名，但在超图/双色图环境中，可能有多种方式来构思这些模型，就像图到超图扩展中的情况一样。事实上，其他研究者提出了 Erd˝os–R´enyi 和 Chung–Lu 的非均匀超图类似物（见 [23] 和 [43]），这些模型在所需输入、模型本身和假设的超图定义上与这里考虑的模型有所不同。

我们选择这些特定模型有几个原因。首先，它们可以生成符合定义 1 全般性的非均匀超图。特别地，这三种模型都允许重复的边，这在超图结构数据中经常发生，并且在我们的特定数据中非常普遍（见图 3）。可以预期，在作者-论文网络中，重复边也可能很常见，当相同的作者组合多次合作撰写论文时（例如图 1 左侧网络中的论文 1 和 4）。这些共同撰写的论文暗示了相关作者之间的更强关系；忽视重复边会忽略这一点，并扭曲例如 s-中心性等旨在捕捉这种属性的测量。与我们考虑的模型相比，[23] 和 [43] 提出的非均匀超图 ER 和 CL 模型不允许重复超边，而是将超边本身视为多重集合。

其次，作为一组，这些模型对三个基本属性提供了分层控制：（1）顶点-超边密度，（2）顶点度数和边基数分布，以及（3）来自 [3] 的社区结构度量，即形变系数。具体来说，ER 控制顶点-超边密度，CL 控制密度以及度数分布，而 BTER 控制上述三项属性。按顺序考虑，ER、CL 和 BTER 可以被形式上看作是前一个模型的推广。这三种模型都提供了可扩展的实现，并且 [3, 39] 报告了使用这些模型生成的具有数亿顶点-超边成员关系的超图的结果；开源实现可在 The Chapel HyperGraph Library (CHGL, [39]) 中找到，这是一个为大规模超图生成和分析编写的原型 HPC 库，使用新兴的 Chapel 编程语言。

5.1 三种生成性超图模型

我们下面定义我们考虑的生成性模型，然后简要比较它们的属性。

最后，BTER 模型（如 [3] 中所述，它利用 CL 模型作为子程序）可以被理解为 CL 的推广。BTER 模型不仅旨在匹配顶点和边大小分布，还匹配每度变形系数。变形系数的完整定义比较复杂；有兴趣的读者可以参考 [3] 以获取详细信息。尽管如此，为了阐明变形系数在超图设置中的解释，我们提供一个高层次的描述。

变形系数是基于二分图中 4-循环（也称为蝴蝶）和 3-路径（也称为毛虫）的计数来度量网络社区结构的。在超图的语言中，蝴蝶是一个包含两个顶点和两个在这两个顶点相交的边的子超图；毛虫是一个边，其中两个顶点与另一个在其中一个顶点相交的边相交。[3] 的作者为二分图中每个分区的顶点定义了变形系数，这些系数基于这些顶点参与的蝴蝶与毛虫计数的比率。等效地，这为超图的顶点和超边定义了变形系数。如果一个超边 e 的变形系数很大，这意味着 e 所交集的大部分边在至少 2 个顶点上相交；同样地，如果一个顶点 v 的变形系数很大，则表示顶点 v 共享边的大部分顶点与至少 2 个边相交。例如，在图 1 中，左侧的网络中每位作者在 3 篇其他论文中与某人重复了合著关系，因此其变形系数为 1/3；而在右侧的网络中，每位作者与其他所有论文重复了合著关系，因此其变形系数为 1。BTER 匹配度分布以及给定度数和基数的顶点和超边的平均变形系数。

作为一个整体，这三个模型作为零假设模型表现良好，因为每个模型比前一个模型提供了逐级的超图结构控制，提供了选择生成超图的不同结构细节的灵活性。在下一节中，我们将每个模型在每个数据集上运行多次，并研究每个模型在复制 s-行走属性方面的效果。例如，“在 LesMis 上运行 CL” 意味着从数据中提取模型输入（在此情况下为顶点度数和超边大小），并使用 Chung–Lu 模型在这些输入下生成一个超图。

5.2 比较

图 9 比较了 LesMis∗、Diseasome 和 CompBoard 的 s-行走属性与由 ER、CL 和 BTER 生成的合成超图的属性。对于每个数据集，我们生成了每个合成模型的 100 个实例，并计算了每个实例的相关属性。图中报告了 100 次试验中的平均值，按每个 s 值进行汇总。

6 结论

超网络数据的普遍性和复杂性要求我们使用既适用又能捕捉超图固有现象的分析方法。我们提出了超图 s-行走，作为一种框架，使得网络科学中流行的图分析工具能更有意义地扩展到超图中。在应用这些度量方法于实际数据时，我们探讨了它们如何揭示数据中各种可解释且重要的结构属性，而这些属性在使用传统图行走方法分析超图时可能会丢失。我们关注的方法——连通组件分析、基于距离的度量、高阶结构和聚类系数——旨在展示这一方法的适用工具的广度。然而，我们的工作显然还远未全面探索。我们通过以下几点总结未来的研究方向：

1. 方法的进一步推广

一个直接的开放问题是如何进一步推广我们开发的方法。例如，理论和实际应用上都有兴趣开发适用于加权超图（具有实值顶点和/或边权重）、有向超图（每个边的顶点要么在其“头部”要么在“尾部”）、有序超图（每个边的顶点是完全有序的）或时间超图（由超图序列组成）的可处理的 s-行走度量。关于后者，我们的工作没有涉及超图及我们观察到的结构属性如何随时间演变。我们考虑的生成模型作为结构零模型是有效的，但并未明确提出超网络生长的过程或机制。相比之下，其他研究者提出并研究了超图演化机制，例如非均匀超图的优先连接模型 [34, 35]。分析这些机制或开发新的时间超图模型可能会揭示高阶结构属性如何在网络拓扑中出现。

2. 高效计算方法的开发

另一个开放方向是为这里提出的 s-行走度量制定高效的计算方法。我们没有探索这些方法背后的算法方面。在某些情况下，尽管我们使用的方法在数据上足够有效，但对于大规模超图数据的可扩展性不足（例如，通过 s-线图计算 s-中心性在顶点度数分布偏斜的大型超图中迅速变得不可行，因为 s-线图的密度在最大顶点度数的平方量级上增加）。开发利用超图稀疏性的算法（而不是计算密集的 s-线图）将有助于将这些方法应用于更大规模的数据。此外，正如研究人员开始开发高效方案来计算原子二分图模式（如长度为 4 的周期）[72, 77]，类似的工作对于实现超图中大规模 s-三角形计数也将非常有用。