這項新證明確立了新的導致連接的振子同步搖擺的條件。
動畫圖源：Samuel Velasco、Paul Chaikin|Quanta
作者：Leila Sloman（量子雜志特約記者）2023-7-24
譯者：zzllrr小樂（數(shù)學科普公眾號）2025-1-26
六年前，阿方索·班代拉（Afonso Bandeira）和凌舒揚試圖找到一種更好的方法來區(qū)分大數(shù)據(jù)集里面的聚類（cluster）時，他們意外地進入了一個超現(xiàn)實的世界。
凌舒揚意識到，他們提出的方程意外地與自發(fā)同步的數(shù)學模型完美匹配。自發(fā)同步（spontaneous synchronization）是一種現(xiàn)象，其中振子（oscillator，振蕩器），可能以擺、彈簧、人的心臟細胞或螢火蟲的形式存在，最終在沒有中央協(xié)調機制的情況下同步移動。
班代拉，瑞士聯(lián)邦理工學院蘇黎世分校的數(shù)學家，以及凌舒揚，紐約大學的數(shù)據(jù)科學家（現(xiàn)任上海紐約大學數(shù)據(jù)科學助理教授，譯者注），深入研究同步，獲得了一系列關于振子之間必須具備的強度和結構才能使得同步發(fā)生的顯著成果。
這項工作在10月份的一篇論文中達到高潮，其中班代拉（連同5位合著者）證明了在稱為擴展圖（expander graph）的特殊網絡中，同步是不可避免的 https://arxiv.org/abs/2210.12788 ，這些網絡雖然稀疏，但連通良好。
擴展圖不僅在數(shù)學領域，而且在計算機科學和物理學領域都有許多應用。它們可以用來創(chuàng)建糾錯碼，并確定基于隨機數(shù)的模擬何時收斂到它們試圖模擬的現(xiàn)實。
由于大腦內部連接空間有限，神經元可以在某些研究人員認為形成擴展圖的圖中進行建模。這些圖對于試圖理解如何穿越復雜表面 https://www.quantamagazine.org/impossible-seeming-surfaces-confirmed-decades-after-conjecture-20220602/ （參閱 ）以及其他問題的幾何學家來說也非常有用。
新的成果表明“真正深入揭示了哪些類型的圖結構能夠保證發(fā)生同步，”伊利諾伊大學的并未參與這項工作的數(shù)學家李德維爾（Lee DeVille）說。
凌舒揚（上圖）和阿方索·班代拉正在研究如何識別數(shù)據(jù)中的聚類時，凌發(fā)現(xiàn)他們的方程可以應用于Kuramoto（藏本由紀）同步模型。
圖源：上海紐約大學
苦樂交織的同步
“同步（synchronization）確實是自然界的基本現(xiàn)象之一，”該論文合作者之一，劍橋大學的數(shù)學家Victor Souza（維克托·索薩）說道?？紤]一下你心臟中的起搏細胞，它們通過電信號同步它們的搏動。
在實驗室的實驗中，“你可以發(fā)現(xiàn)數(shù)百個或數(shù)千個這些胚胎起搏細胞同時搏動，”另一位合著者，康奈爾大學的數(shù)學家Steven Strogatz（史蒂芬·斯特羅加茨）說。“這有點令人毛骨悚然，因為這不是一個完整的心臟；而是只涉及細胞層面?！?/p>
1975年，日本物理學家藏本由紀（Yoshiki Kuramoto，1940 -）提出了一種描述此類系統(tǒng)的數(shù)學模型。他的模型運行在一個稱為圖（graph）的網絡上，節(jié)點（node，有時亦寫成結點）通過稱為邊（edge）的線連接。如果節(jié)點之間通過邊相連，則稱彼此為鄰居（neighbor）。每條邊都可以分配一個稱為權重（weight）的數(shù)字，編碼了節(jié)點之間的連接強度。
在Kuramoto的同步模型中，每個節(jié)點包含一個振子，它由圍繞圓圈旋轉的點表示。這個點可以代表心臟細胞在其搏動周期中的位置。每個振子以自己的偏好速率循環(huán)往復。但振子還希望與鄰居匹配，鄰居可能以不同的頻率或在其周期的不同點旋轉。
連接兩個振子的邊的權重衡量它們之間耦合的強度。偏離這些偏好會增加振子消耗的能量。系統(tǒng)試圖通過最小化其總能量來平衡所有競爭的欲望。Kuramoto的貢獻在于簡化了這些數(shù)學約束，使得數(shù)學家能夠對這些系統(tǒng)開展研究。在大多數(shù)情況下，如此大的耦合的微分方程組幾乎無法求解。
盡管其簡單性，Kuramoto模型已被證明在模擬從大腦到電網的網絡同步方面非常有用，倫敦瑪麗女王大學的應用數(shù)學家Ginestra Bianconi表示?！霸诖竽X中，它并不特別準確，但被認為非常有效，”她說。
“數(shù)學與物理在這里有一種非常微妙的舞蹈，因為一個能夠刻畫現(xiàn)象但很難分析的模型并不是很有用，”索薩說。
在他的1975年論文中，Kuramoto假設每個節(jié)點都與每個其他節(jié)點相連，這被稱為完全圖（complete graph）。這種情況下，他證明對于無限數(shù)量的振子，如果它們之間的耦合足夠強，就能推斷出它們的長期行為。
在做出一個額外假設，即所有振子具有相同的頻率（這將使它們成為所謂的均勻（homogeneous，同質、齊次）模型）之后，他找到了一個解，其中所有振子最終會同時旋轉，每個振子在它們的圓周上繞著同一個點以完全相同的時間旋轉。
雖然大多數(shù)現(xiàn)實世界的圖遠非完全圖，但Kuramoto的成功促使數(shù)學家們思考，如果放寬他的要求會發(fā)生什么。
1975年，藏本由紀（Yoshiki Kuramoto）提出了同步的突破性數(shù)學模型
圖源：Tomoaki Sukezane
旋律與寂靜
在1990年代初，斯特羅加茨與他的學生渡邊真也（Shinya Watanabe）一起證明，即使對于有限數(shù)量的振子，Kuramoto的解不僅是可能的，而且是幾乎不可避免的。
2011年，澳大利亞國防科學與技術組織的理查德·泰勒（Richard Taylor）對Kuramoto關于圖必須是完全圖的條件進行了挑戰(zhàn)。他證明了 https://arxiv.org/abs/1109.4451 每個節(jié)點至少與其他94%的節(jié)點相連的均勻圖必定能夠整體同步。泰勒的結果的優(yōu)勢在于它適用于具有任意連接結構的圖，只要每個節(jié)點都有大量的鄰居。
2018年，班代拉、凌舒揚和耶魯大學研究生徐瑞圖（音譯）將泰勒的每個節(jié)點連接到其他94%的節(jié)點的要求降低到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 間的一系列論文中，他們發(fā)現(xiàn)了一個又一個可以避免整體同步的圖，盡管每個節(jié)點都與超過68%的其他節(jié)點相連。
許多這樣的圖類似于人們手拉手圍成的圈，每個人伸出手去接觸10個甚至100個附近的鄰居。這些圖被稱為環(huán)形圖（ring graph），可以進入一種狀態(tài)，其中每個振子相對于下一個都有輕微的偏移。
顯然，圖結構對同步有重大影響。因此，凌、徐和班代拉對隨機生成圖的同步性質產生了好奇心。為了使他們的工作更精確，他們使用了兩種常見的隨機構建圖的方法。
第一個是以保羅·埃爾德什（Paul Erd?s，1913 - 1996）和阿爾弗雷德·雷尼（Alfréd Rényi,1921 - 1970）命名的模型，他們是兩位杰出的圖論學家，在該模型上做了開創(chuàng)性的工作。
要使用埃爾德什-雷尼（Erd?s-Rényi）模型構建圖，可從一些未連接的節(jié)點開始。然后對于每一對節(jié)點，以概率p隨機地將它們連接起來。如果p是1%，你就有1%的機率連接邊；如果p是50%，平均每個節(jié)點將連接到其他一半節(jié)點。
如果p略大于一個取決于圖中節(jié)點數(shù)量的閾值，那么該圖極有可能形成一個相互連接的網絡（而不是由不相連的聚類組成）。隨著圖的大小增長，這個閾值變得極小，因此對于足夠大的圖，即使p很小，使得邊的總數(shù)也較小，Erd?s-Rényi圖也將是連通的。
第二種他們考慮的圖稱為d-正則圖（d-regular graph）。在這種圖中，每個節(jié)點都有相同數(shù)量（即d）的邊。（因此，在3-正則圖中，每個節(jié)點連接到其他3個節(jié)點，在7-正則圖中，每個節(jié)點連接到其他7個節(jié)點，依此類推。）
擴展圖：
有相對少的邊（這里每個結點只有3條邊），但有高的連通度。
連通性差的圖：
從一個結點到另一個結點，只有很少的邊
圖源：Merrill Sherman|Quanta
圖雖然稀疏——只有少量邊——但連接良好，被稱為擴展圖（expander graph）。這些圖在數(shù)學、物理和計算機科學的許多領域都很重要，但如果你想要構建具有特定性質的擴展圖，你會發(fā)現(xiàn)這是一個“出人意料的不平凡問題”，著名數(shù)學家陶哲軒（Terry Tao）如是說 https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/ 。盡管Erd?s-Rényi圖并不總是擴展圖，但它們共有許多重要特征。結果發(fā)現(xiàn)，如果你構建一個d-正則圖并隨機連接邊，你將得到一個擴展圖。
連接兩頭
2018年，凌、徐和班代拉猜測連通閾值可能也度量整體同步的出現(xiàn)：如果生成一個p略大于閾值的Erd?s-Rényi圖，該圖應該整體同步。他們在這一猜想上取得了一定的進展，而斯特羅加茨、卡薩博夫和湯森德后來改進了他們的結果。但他們的數(shù)字與連通閾值之間仍存在很大的差距。
2022年3月，湯森德訪問了蘇黎世的班代拉。他們意識到有機會達到連接閾值，于是邀請了班代拉的畢業(yè)生佩德羅·阿布達拉（Pedro Abdalla），阿布達拉又招募了他的朋友維克托·索薩（Victor Souza）。阿布達拉和索薩開始商討細節(jié)，但很快遇到了障礙。
似乎隨機性伴隨著不可避免的問題。除非p顯著大于連接閾值，否則每個節(jié)點擁有的邊數(shù)可能會出現(xiàn)大幅波動。一個節(jié)點可能連接了100條邊；另一個節(jié)點可能沒有連接任何邊?！熬拖衩總€好問題一樣，它會反擊，”索薩說。
阿布達拉和索薩意識到從隨機圖的角度來解決這個問題是不可行的。相反，他們會利用大多數(shù)Erd?s-Rényi圖都是擴展圖的事實?！霸谶@個看似無辜的改變之后，拼圖的許多碎片開始落位，”索薩說。
“最終，我們得到了一個比我們預期的結果更強的結果。”圖有一個稱為擴展系數(shù)（expansion）的數(shù)字，它衡量將圖分成兩半的難度，這兩半按圖的大小進行標準化。這個數(shù)字越大，通過移除節(jié)點將其分成兩半就越困難。
阿方索·班代拉在過去六年里試圖理解迫使振子同步的條件
圖源：Giulia Marthaler
在接下來的幾個月里，團隊完善了其余的論據(jù)，并在10月份將他們的論文發(fā)布在網上。他們的證明 https://arxiv.org/abs/2210.12788 表明，給定足夠的時間，如果圖有足夠大的擴展系數(shù)，均勻Kuramoto模型將始終整體同步。
沿著唯一的道路
在對同步的數(shù)學研究中最大未解之謎之一，只需在新論文中對模型進行微小調整：如果一些振子相互拉入同步，而另一些則將其推出同步，會發(fā)生什么？在這種情況下，“我們幾乎所有工具都立即消失了，”索薩說。
如果研究人員能在這一版本的問題上取得進展，這些技術可能會幫助班代拉解決他在轉向同步之前設定的數(shù)據(jù)聚類問題。
除此之外，除了擴展圖之外，還有比整體同步更復雜的模式，以及不假設每個節(jié)點和邊都相同的同步模型。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 一直在與涉及三個、四個或更多節(jié)點的網絡鏈接進行合作，而不僅僅是針對成對節(jié)點。
班代拉和阿布達拉已經試圖超越Erd?s-Rényi模型和d-正則模型，轉向其他更現(xiàn)實的隨機圖模型。去年八月，他們與克拉拉·因韋尼齊（Clara Invernizzi）共同發(fā)表了一篇關于隨機幾何圖同步的論文 https://arxiv.org/abs/2208.12246 。
在1961年構思的隨機幾何圖中，節(jié)點在空間中隨機分布，可能在一個球面或平面上。如果節(jié)點之間的距離在一定范圍內，則在這些節(jié)點之間放置邊。其發(fā)明者埃德加·吉爾伯特（Edgar Gilbert）希望以此模型模擬只能短距離傳輸消息的通信網絡，或者需要近距離接觸才能傳播的傳染病的擴散。班代拉說，隨機幾何模型還能更好地刻畫一群螢火蟲之間的聯(lián)系，它們通過觀察鄰居來實現(xiàn)同步。
當然，將數(shù)學結果與現(xiàn)實世界聯(lián)系起來具有挑戰(zhàn)性。“我認為說這是由應用所驅動的是個無傷大雅的小謊言，”斯特羅加茨說，他還指出，均勻Kuramoto模型永遠無法刻畫生物系統(tǒng)中的固有變異。索薩補充說：“還有很多基本問題我們不知道如何解決。這更像是在探索叢林?！?/p>
參考資料
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
科普薦書
【更多讀者好評數(shù)學書單推薦、數(shù)學科普作家自薦、出版社書單推薦通道已陸續(xù)打開，敬請期待】
·開放 · 友好 · 多元 · 普適 · 守拙·
讓數(shù)學
更加
易學易練
易教易研
易賞易玩
易見易得
易傳易及
歡迎評論、點贊、在看、在聽
收藏、分享、轉載、投稿
查看原始文章出處
點擊zzllrr小樂
公眾號主頁
右上角
數(shù)學科普不迷路！
熱門跟貼