图论新维度：数据驱动的数学理论，揭秘复杂联系的新工具( 二 ) 作者|StephenOrnes编译|王晔校对

这种高阶方法在应用研究中已经被证明是有用的。例如， 20世纪90年代，生态学家展示了向黄石国家公园重新引进狼群时，生物多样性和食物链结构的变化过程。在最近的一篇论文中，美国西北太平洋国家实验室的数学家milie Purvine和她的同事分析了一个病毒感染的生物反应数据库，使用超图来确定所涉及的最关键基因。在论文中，他们还展示了这些相互作用是如何被图论提供的通常成对分析遗漏的。
【图论新维度：数据驱动的数学理论，揭秘复杂联系的新工具】康奈尔大学的Austin Benson最近使用高阶马尔科夫链和张量模拟了纽约市的出租车行程。虽然仍有改进空间，但结果比传统的马尔科夫链要好。
然而，从图到超图的泛化很快就会变得复杂。例如图论中的规范切割问题，该问题问道："给定一个图上的两个不同的节点，你最少可以切割多少条边来完全切断两者之间的所有联系？给定一个图上的两个不同的节点，要完全切断这两个节点之间的所有联系，你能切断的最少的边数是多少？许多算法可以很容易地找到给定图形的最佳切割数。
但是如何切割超图呢？康奈尔大学的数学家Austin Benson说：“有很多方法可以将这种切割的概念推广到超图中。但没有一个明确的解决方案” ，他说“因为超边可以以各种方式被切断，创造出新的节点组” 。
最近， Benson 与两位同事一起，尝试将分割超图的所有不同方式正式化。但对于某些情况，这个问题基本上是无法解决，或者说无法确定是否存在解决方案。
2数学三明治
超图并不是探索高阶互动的唯一方法。拓扑学是一种对几何属性的数学研究，其假设是：当你拉伸、压缩或以其他方式转换对象时，这些属性不会改变。拓扑学提供了一种更直观的方法。当拓扑学家研究一个网络时，他们寻找形状、表面和尺寸。他们可能会注意到连接两个节点的边是一维的，并询问不同网络中一维物体的属性。或者他们可能会看到连接三个节点所形成的二维三角形表面，并提出类似的问题。

文章图片

文章图片
拓扑学家把这些结构称为 simplicial complexes 。实际上，这是通过拓扑学的框架来看的超图，神经网络提供了一个很好的例子。它们由旨在模仿我们大脑的神经元如何处理信息的算法驱动。图形神经网络（GNNs）将事物之间的连接建模为成对连接，擅长推断大数据集中缺失的数据，但在其他应用中，它们可能会错过仅由三个或更多群体产生的相互作用。近年来，计算机科学家开发了 simplicial neural networks ，它使用高阶复数来概括GNN的方法，以求发现这些效应。
simplicial complexes 将拓扑学与图论联系起来，与超图一样，它们提出了引人注目的数学问题。例如，在拓扑学中， simplicial complexes 的特殊类型的子集本身也是simplicial complexes，因此具有相同的属性。如果超图也是如此，子集将包括其中的所有超边——包括所有嵌入的双向边。
但情况并非总是如此。“我们现在看到的是，数据落入了中间地带，你可以进行三向互动，但不是成对的互动。”Purvine表示， “大数据集已经清楚地表明，无论是在生物信号网络中还是在同行压力等社会行为中，群体的影响往往远远超过个人的影响” 。
Purvine将数据描述为数学三明治的中间部分，上限是拓扑学思想，下限是图论。
3随机游走和矩阵
这种创造性的 "游戏 "感也延伸到了其他工具。在图和其他描述数据的工具之间存在着各种美妙的联系。但是一旦你转移到高阶设置，这些联系就难以出现了。当你试图考虑马尔科夫链的高维版时，这一点尤其明显。