数学|图论新维度：数据驱动的数学理论，揭秘复杂联系的新工具( 二 ) 支付宝|民政通|小程序|婚姻登

康奈尔大学的Austin Benson最近使用高阶马尔科夫链和张量模拟了纽约市的出租车行程。虽然仍有改进空间，但结果比传统的马尔科夫链要好。
然而，从图到超图的泛化很快就会变得复杂。例如图论中的规范切割问题，该问题问道："给定一个图上的两个不同的节点，你最少可以切割多少条边来完全切断两者之间的所有联系？给定一个图上的两个不同的节点，要完全切断这两个节点之间的所有联系，你能切断的最少的边数是多少？许多算法可以很容易地找到给定图形的最佳切割数。
但是如何切割超图呢？康奈尔大学的数学家Austin Benson说：“有很多方法可以将这种切割的概念推广到超图中。但没有一个明确的解决方案”，他说“因为超边可以以各种方式被切断，创造出新的节点组”。
最近，Benson 与两位同事一起，尝试将分割超图的所有不同方式正式化。但对于某些情况，这个问题基本上是无法解决，或者说无法确定是否存在解决方案。

数学三明治

超图并不是探索高阶互动的唯一方法。拓扑学是一种对几何属性的数学研究，其假设是：当你拉伸、压缩或以其他方式转换对象时，这些属性不会改变。拓扑学提供了一种更直观的方法。当拓扑学家研究一个网络时，他们寻找形状、表面和尺寸。他们可能会注意到连接两个节点的边是一维的，并询问不同网络中一维物体的属性。或者他们可能会看到连接三个节点所形成的二维三角形表面，并提出类似的问题。

文章插图

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

随机游走和矩阵

这种创造性的 "游戏 "感也延伸到了其他工具。在图和其他描述数据的工具之间存在着各种美妙的联系。但是一旦你转移到高阶设置，这些联系就难以出现了。当你试图考虑马尔科夫链的高维版时，这一点尤其明显。
马尔科夫链描述了一个多阶段的过程，其中下一阶段只取决于元素的当前位置；研究人员已经使用马尔科夫模型来描述信息、能量甚至金钱等事物如何在一个系统中流动。马尔科夫链最著名的例子也许是随机漫步，它描述了一条路径，其中每一步都是由之前的步骤随机决定的。随机漫步也是一个特定的图。任何沿着图的轨迹都可以显示为一个沿着链接从节点到节点的序列。