這項新證明確立了新的導致連接的振子同步搖擺的條件。

動畫圖源：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

科普薦書

【更多讀者好評數學書單推薦、數學科普作家自薦、出版社書單推薦通道已陸續打開，敬請期待】

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！