“扩展”图同步的新数学证明

原创 Quanta Magazine zzllrr小乐

这项新证明确立了新的导致连接的振子同步摇摆的条件。

动画图源：Samuel Velasco、Paul Chaikin|Quanta

作者：Leila Sloman（量子杂志特约记者）2023-7-24

译者：zzllrr小乐（数学科普公众号）2025-1-26

六年前，阿方索·班代拉（Afonso Bandeira）和凌舒扬试图找到一种更好的方法来区分大数据集里面的聚类（cluster）时，他们意外地进入了一个超现实的世界。

凌舒扬意识到，他们提出的方程意外地与自发同步的数学模型完美匹配。自发同步（spontaneous synchronization）是一种现象，其中振子（oscillator，振荡器），可能以摆、弹簧、人的心脏细胞或萤火虫的形式存在，最终在没有中央协调机制的情况下同步移动。

班代拉，瑞士联邦理工学院苏黎世分校的数学家，以及凌舒扬，纽约大学的数据科学家（现任上海纽约大学数据科学助理教授，译者注），深入研究同步，获得了一系列关于振子之间必须具备的强度和结构才能使得同步发生的显著成果。

这项工作在10月份的一篇论文中达到高潮，其中班代拉（连同5位合著者）证明了在称为扩展图（expander graph）的特殊网络中，同步是不可避免的 https://arxiv.org/abs/2210.12788 ，这些网络虽然稀疏，但连通良好。

扩展图不仅在数学领域，而且在计算机科学和物理学领域都有许多应用。它们可以用来创建纠错码，并确定基于随机数的模拟何时收敛到它们试图模拟的现实。

由于大脑内部连接空间有限，神经元可以在某些研究人员认为形成扩展图的图中进行建模。这些图对于试图理解如何穿越复杂表面 https://www.quantamagazine.org/impossible-seeming-surfaces-confirmed-decades-after-conjecture-20220602/ （参阅 ）以及其他问题的几何学家来说也非常有用。

新的成果表明“真正深入揭示了哪些类型的图结构能够保证发生同步，”伊利诺伊大学的并未参与这项工作的数学家李德维尔（Lee DeVille）说。

凌舒扬（上图）和阿方索·班代拉正在研究如何识别数据中的聚类时，凌发现他们的方程可以应用于Kuramoto（藏本由纪）同步模型。

图源：上海纽约大学

苦乐交织的同步

“同步（synchronization）确实是自然界的基本现象之一，”该论文合作者之一，剑桥大学的数学家Victor Souza（维克托·索萨）说道。考虑一下你心脏中的起搏细胞，它们通过电信号同步它们的搏动。

在实验室的实验中，“你可以发现数百个或数千个这些胚胎起搏细胞同时搏动，”另一位合著者，康奈尔大学的数学家Steven Strogatz（史蒂芬·斯特罗加茨）说。“这有点令人毛骨悚然，因为这不是一个完整的心脏；而是只涉及细胞层面。”

1975年，日本物理学家藏本由纪（Yoshiki Kuramoto，1940 -）提出了一种描述此类系统的数学模型。他的模型运行在一个称为图（graph）的网络上，节点（node，有时亦写成结点）通过称为边（edge）的线连接。如果节点之间通过边相连，则称彼此为邻居（neighbor）。每条边都可以分配一个称为权重（weight）的数字，编码了节点之间的连接强度。

在Kuramoto的同步模型中，每个节点包含一个振子，它由围绕圆圈旋转的点表示。这个点可以代表心脏细胞在其搏动周期中的位置。每个振子以自己的偏好速率循环往复。但振子还希望与邻居匹配，邻居可能以不同的频率或在其周期的不同点旋转。

连接两个振子的边的权重衡量它们之间耦合的强度。偏离这些偏好会增加振子消耗的能量。系统试图通过最小化其总能量来平衡所有竞争的欲望。Kuramoto的贡献在于简化了这些数学约束，使得数学家能够对这些系统开展研究。在大多数情况下，如此大的耦合的微分方程组几乎无法求解。

尽管其简单性，Kuramoto模型已被证明在模拟从大脑到电网的网络同步方面非常有用，伦敦玛丽女王大学的应用数学家Ginestra Bianconi表示。“在大脑中，它并不特别准确，但被认为非常有效，”她说。

“数学与物理在这里有一种非常微妙的舞蹈，因为一个能够刻画现象但很难分析的模型并不是很有用，”索萨说。

在他的1975年论文中，Kuramoto假设每个节点都与每个其他节点相连，这被称为完全图（complete graph）。这种情况下，他证明对于无限数量的振子，如果它们之间的耦合足够强，就能推断出它们的长期行为。

在做出一个额外假设，即所有振子具有相同的频率（这将使它们成为所谓的均匀（homogeneous，同质、齐次）模型）之后，他找到了一个解，其中所有振子最终会同时旋转，每个振子在它们的圆周上绕着同一个点以完全相同的时间旋转。

虽然大多数现实世界的图远非完全图，但Kuramoto的成功促使数学家们思考，如果放宽他的要求会发生什么。

1975年，藏本由纪（Yoshiki Kuramoto）提出了同步的突破性数学模型

图源：Tomoaki Sukezane

旋律与寂静

在1990年代初，斯特罗加茨与他的学生渡边真也（Shinya Watanabe）一起证明，即使对于有限数量的振子，Kuramoto的解不仅是可能的，而且是几乎不可避免的。

2011年，澳大利亚国防科学与技术组织的理查德·泰勒（Richard Taylor）对Kuramoto关于图必须是完全图的条件进行了挑战。他证明了 https://arxiv.org/abs/1109.4451 每个节点至少与其他94%的节点相连的均匀图必定能够整体同步。泰勒的结果的优势在于它适用于具有任意连接结构的图，只要每个节点都有大量的邻居。

2018年，班代拉、凌舒扬和耶鲁大学研究生徐瑞图（音译）将泰勒的每个节点连接到其他94%的节点的要求降低到79.3% https://epubs.siam.org/doi/10.1137/18M1217644 。

2020年，一个竞争团队达到了78.89%；2021年，斯特罗加茨、亚历克斯·汤森德（Alex Townsend）和马丁·卡萨博夫（Martin Kassabov）证明75%就足够了，确立了当前记录 https://pubs.aip.org/aip/cha/article/31/7/073135/342231/Sufficiently-dense-Kuramoto-networks-are-globally 。

与此同时，研究人员也从相反的方向攻击了这个问题，试图找到高度连通但并未整体同步的图。在2006年 https://pubs.aip.org/aip/cha/article-abstract/16/1/015103/321873/The-size-of-the-sync-basin?redirectedFrom=fulltext 至2022年 https://arxiv.org/abs/2209.06362 间的一系列论文中，他们发现了一个又一个可以避免整体同步的图，尽管每个节点都与超过68%的其他节点相连。

许多这样的图类似于人们手拉手围成的圈，每个人伸出手去接触10个甚至100个附近的邻居。这些图被称为环形图（ring graph），可以进入一种状态，其中每个振子相对于下一个都有轻微的偏移。

显然，图结构对同步有重大影响。因此，凌、徐和班代拉对随机生成图的同步性质产生了好奇心。为了使他们的工作更精确，他们使用了两种常见的随机构建图的方法。

第一个是以保罗·埃尔德什（Paul Erdős，1913 - 1996）和阿尔弗雷德·雷尼（Alfréd Rényi,1921 - 1970）命名的模型，他们是两位杰出的图论学家，在该模型上做了开创性的工作。

要使用埃尔德什-雷尼（Erdős-Rényi）模型构建图，可从一些未连接的节点开始。然后对于每一对节点，以概率p随机地将它们连接起来。如果p是1%，你就有1%的机率连接边；如果p是50%，平均每个节点将连接到其他一半节点。

如果p略大于一个取决于图中节点数量的阈值，那么该图极有可能形成一个相互连接的网络（而不是由不相连的聚类组成）。随着图的大小增长，这个阈值变得极小，因此对于足够大的图，即使p很小，使得边的总数也较小，Erdős-Rényi图也将是连通的。

第二种他们考虑的图称为d-正则图（d-regular graph）。在这种图中，每个节点都有相同数量（即d）的边。（因此，在3-正则图中，每个节点连接到其他3个节点，在7-正则图中，每个节点连接到其他7个节点，依此类推。）

扩展图：

有相对少的边（这里每个结点只有3条边），但有高的连通度。

连通性差的图：

从一个结点到另一个结点，只有很少的边

图源：Merrill Sherman|Quanta

图虽然稀疏——只有少量边——但连接良好，被称为扩展图（expander graph）。这些图在数学、物理和计算机科学的许多领域都很重要，但如果你想要构建具有特定性质的扩展图，你会发现这是一个“出人意料的不平凡问题”，著名数学家陶哲轩（Terry Tao）如是说 https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/ 。尽管Erdős-Rényi图并不总是扩展图，但它们共有许多重要特征。结果发现，如果你构建一个d-正则图并随机连接边，你将得到一个扩展图。

连接两头

2018年，凌、徐和班代拉猜测连通阈值可能也度量整体同步的出现：如果生成一个p略大于阈值的Erdős-Rényi图，该图应该整体同步。他们在这一猜想上取得了一定的进展，而斯特罗加茨、卡萨博夫和汤森德后来改进了他们的结果。但他们的数字与连通阈值之间仍存在很大的差距。

2022年3月，汤森德访问了苏黎世的班代拉。他们意识到有机会达到连接阈值，于是邀请了班代拉的毕业生佩德罗·阿布达拉（Pedro Abdalla），阿布达拉又招募了他的朋友维克托·索萨（Victor Souza）。阿布达拉和索萨开始商讨细节，但很快遇到了障碍。

似乎随机性伴随着不可避免的问题。除非p显著大于连接阈值，否则每个节点拥有的边数可能会出现大幅波动。一个节点可能连接了100条边；另一个节点可能没有连接任何边。“就像每个好问题一样，它会反击，”索萨说。

阿布达拉和索萨意识到从随机图的角度来解决这个问题是不可行的。相反，他们会利用大多数Erdős-Rényi图都是扩展图的事实。“在这个看似无辜的改变之后，拼图的许多碎片开始落位，”索萨说。

“最终，我们得到了一个比我们预期的结果更强的结果。”图有一个称为扩展系数（expansion）的数字，它衡量将图分成两半的难度，这两半按图的大小进行标准化。这个数字越大，通过移除节点将其分成两半就越困难。

阿方索·班代拉在过去六年里试图理解迫使振子同步的条件

图源：Giulia Marthaler

在接下来的几个月里，团队完善了其余的论据，并在10月份将他们的论文发布在网上。他们的证明 https://arxiv.org/abs/2210.12788 表明，给定足够的时间，如果图有足够大的扩展系数，均匀Kuramoto模型将始终整体同步。

沿着唯一的道路

在对同步的数学研究中最大未解之谜之一，只需在新论文中对模型进行微小调整：如果一些振子相互拉入同步，而另一些则将其推出同步，会发生什么？在这种情况下，“我们几乎所有工具都立即消失了，”索萨说。

如果研究人员能在这一版本的问题上取得进展，这些技术可能会帮助班代拉解决他在转向同步之前设定的数据聚类问题。

除此之外，除了扩展图之外，还有比整体同步更复杂的模式，以及不假设每个节点和边都相同的同步模型。2018年，加州大学圣塔芭芭拉分校的Saber Jafarpour和Francesco Bullo提出了一种适用于整体同步的测试方法 https://ieeexplore.ieee.org/document/8496811 ，该方法在旋转器不具有相同权重和偏好频率时仍然有效。

Bianconi的团队 https://journals.aps.org/pre/abstract/10.1103/PhysRevE.99.022307 以及其他研究人员 https://www.nature.com/articles/s41467-021-21486-9 一直在与涉及三个、四个或更多节点的网络链接进行合作，而不仅仅是针对成对节点。

班代拉和阿布达拉已经试图超越Erdős-Rényi模型和d-正则模型，转向其他更现实的随机图模型。去年八月，他们与克拉拉·因韦尼齐（Clara Invernizzi）共同发表了一篇关于随机几何图同步的论文 https://arxiv.org/abs/2208.12246 。

在1961年构思的随机几何图中，节点在空间中随机分布，可能在一个球面或平面上。如果节点之间的距离在一定范围内，则在这些节点之间放置边。其发明者埃德加·吉尔伯特（Edgar Gilbert）希望以此模型模拟只能短距离传输消息的通信网络，或者需要近距离接触才能传播的传染病的扩散。班代拉说，随机几何模型还能更好地刻画一群萤火虫之间的联系，它们通过观察邻居来实现同步。

当然，将数学结果与现实世界联系起来具有挑战性。“我认为说这是由应用所驱动的是个无伤大雅的小谎言，”斯特罗加茨说，他还指出，均匀Kuramoto模型永远无法刻画生物系统中的固有变异。索萨补充说：“还有很多基本问题我们不知道如何解决。这更像是在探索丛林。”

参考资料

https://www.quantamagazine.org/new-proof-shows-that-expander-graphs-synchronize-20230724/

https://arxiv.org/abs/2210.12788

https://shanghai.nyu.edu/cn/stories/qa-data-science-professor-ling-shuyang

https://www.quantamagazine.org/impossible-seeming-surfaces-confirmed-decades-after-conjecture-20220602/

https://epubs.siam.org/doi/10.1137/18M1217644

https://pubs.aip.org/aip/cha/article/31/7/073135/342231/Sufficiently-dense-Kuramoto-networks-are-globally

https://arxiv.org/abs/2210.12788

https://ieeexplore.ieee.org/document/8496811

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.99.022307

https://www.nature.com/articles/s41467-021-21486-9

https://arxiv.org/abs/2208.12246