這項(xiàng)新證明確立了新的導(dǎo)致連接的振子同步搖擺的條件。

動畫圖源：Samuel Velasco、Paul Chaikin|Quanta

作者：Leila Sloman（量子雜志特約記者）2023-7-24

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2025-1-26

六年前，阿方索·班代拉（Afonso Bandeira）和凌舒揚(yáng)試圖找到一種更好的方法來區(qū)分大數(shù)據(jù)集里面的聚類（cluster）時(shí)，他們意外地進(jìn)入了一個(gè)超現(xiàn)實(shí)的世界。

凌舒揚(yáng)意識到，他們提出的方程意外地與自發(fā)同步的數(shù)學(xué)模型完美匹配。自發(fā)同步（spontaneous synchronization）是一種現(xiàn)象，其中振子（oscillator，振蕩器），可能以擺、彈簧、人的心臟細(xì)胞或螢火蟲的形式存在，最終在沒有中央?yún)f(xié)調(diào)機(jī)制的情況下同步移動。

班代拉，瑞士聯(lián)邦理工學(xué)院蘇黎世分校的數(shù)學(xué)家，以及凌舒揚(yáng)，紐約大學(xué)的數(shù)據(jù)科學(xué)家（現(xiàn)任上海紐約大學(xué)數(shù)據(jù)科學(xué)助理教授，譯者注），深入研究同步，獲得了一系列關(guān)于振子之間必須具備的強(qiáng)度和結(jié)構(gòu)才能使得同步發(fā)生的顯著成果。

這項(xiàng)工作在10月份的一篇論文中達(dá)到高潮，其中班代拉（連同5位合著者）證明了在稱為擴(kuò)展圖（expander graph）的特殊網(wǎng)絡(luò)中，同步是不可避免的 https://arxiv.org/abs/2210.12788 ，這些網(wǎng)絡(luò)雖然稀疏，但連通良好。

擴(kuò)展圖不僅在數(shù)學(xué)領(lǐng)域，而且在計(jì)算機(jī)科學(xué)和物理學(xué)領(lǐng)域都有許多應(yīng)用。它們可以用來創(chuàng)建糾錯(cuò)碼，并確定基于隨機(jī)數(shù)的模擬何時(shí)收斂到它們試圖模擬的現(xiàn)實(shí)。

由于大腦內(nèi)部連接空間有限，神經(jīng)元可以在某些研究人員認(rèn)為形成擴(kuò)展圖的圖中進(jìn)行建模。這些圖對于試圖理解如何穿越復(fù)雜表面 https://www.quantamagazine.org/impossible-seeming-surfaces-confirmed-decades-after-conjecture-20220602/ （參閱 ）以及其他問題的幾何學(xué)家來說也非常有用。

新的成果表明“真正深入揭示了哪些類型的圖結(jié)構(gòu)能夠保證發(fā)生同步，”伊利諾伊大學(xué)的并未參與這項(xiàng)工作的數(shù)學(xué)家李德維爾（Lee DeVille）說。

凌舒揚(yáng)（上圖）和阿方索·班代拉正在研究如何識別數(shù)據(jù)中的聚類時(shí)，凌發(fā)現(xiàn)他們的方程可以應(yīng)用于Kuramoto（藏本由紀(jì)）同步模型。

圖源：上海紐約大學(xué)

苦樂交織的同步

“同步（synchronization）確實(shí)是自然界的基本現(xiàn)象之一，”該論文合作者之一，劍橋大學(xué)的數(shù)學(xué)家Victor Souza（維克托·索薩）說道。考慮一下你心臟中的起搏細(xì)胞，它們通過電信號同步它們的搏動。

在實(shí)驗(yàn)室的實(shí)驗(yàn)中，“你可以發(fā)現(xiàn)數(shù)百個(gè)或數(shù)千個(gè)這些胚胎起搏細(xì)胞同時(shí)搏動，”另一位合著者，康奈爾大學(xué)的數(shù)學(xué)家Steven Strogatz（史蒂芬·斯特羅加茨）說?！斑@有點(diǎn)令人毛骨悚然，因?yàn)檫@不是一個(gè)完整的心臟；而是只涉及細(xì)胞層面。”

1975年，日本物理學(xué)家藏本由紀(jì)（Yoshiki Kuramoto，1940 -）提出了一種描述此類系統(tǒng)的數(shù)學(xué)模型。他的模型運(yùn)行在一個(gè)稱為圖（graph）的網(wǎng)絡(luò)上，節(jié)點(diǎn)（node，有時(shí)亦寫成結(jié)點(diǎn)）通過稱為邊（edge）的線連接。如果節(jié)點(diǎn)之間通過邊相連，則稱彼此為鄰居（neighbor）。每條邊都可以分配一個(gè)稱為權(quán)重（weight）的數(shù)字，編碼了節(jié)點(diǎn)之間的連接強(qiáng)度。

在Kuramoto的同步模型中，每個(gè)節(jié)點(diǎn)包含一個(gè)振子，它由圍繞圓圈旋轉(zhuǎn)的點(diǎn)表示。這個(gè)點(diǎn)可以代表心臟細(xì)胞在其搏動周期中的位置。每個(gè)振子以自己的偏好速率循環(huán)往復(fù)。但振子還希望與鄰居匹配，鄰居可能以不同的頻率或在其周期的不同點(diǎn)旋轉(zhuǎn)。

連接兩個(gè)振子的邊的權(quán)重衡量它們之間耦合的強(qiáng)度。偏離這些偏好會增加振子消耗的能量。系統(tǒng)試圖通過最小化其總能量來平衡所有競爭的欲望。Kuramoto的貢獻(xiàn)在于簡化了這些數(shù)學(xué)約束，使得數(shù)學(xué)家能夠?qū)@些系統(tǒng)開展研究。在大多數(shù)情況下，如此大的耦合的微分方程組幾乎無法求解。

盡管其簡單性，Kuramoto模型已被證明在模擬從大腦到電網(wǎng)的網(wǎng)絡(luò)同步方面非常有用，倫敦瑪麗女王大學(xué)的應(yīng)用數(shù)學(xué)家Ginestra Bianconi表示?！霸诖竽X中，它并不特別準(zhǔn)確，但被認(rèn)為非常有效，”她說。

“數(shù)學(xué)與物理在這里有一種非常微妙的舞蹈，因?yàn)橐粋€(gè)能夠刻畫現(xiàn)象但很難分析的模型并不是很有用，”索薩說。

在他的1975年論文中，Kuramoto假設(shè)每個(gè)節(jié)點(diǎn)都與每個(gè)其他節(jié)點(diǎn)相連，這被稱為完全圖（complete graph）。這種情況下，他證明對于無限數(shù)量的振子，如果它們之間的耦合足夠強(qiáng)，就能推斷出它們的長期行為。

在做出一個(gè)額外假設(shè)，即所有振子具有相同的頻率（這將使它們成為所謂的均勻（homogeneous，同質(zhì)、齊次）模型）之后，他找到了一個(gè)解，其中所有振子最終會同時(shí)旋轉(zhuǎn)，每個(gè)振子在它們的圓周上繞著同一個(gè)點(diǎn)以完全相同的時(shí)間旋轉(zhuǎn)。

雖然大多數(shù)現(xiàn)實(shí)世界的圖遠(yuǎn)非完全圖，但Kuramoto的成功促使數(shù)學(xué)家們思考，如果放寬他的要求會發(fā)生什么。

1975年，藏本由紀(jì)（Yoshiki Kuramoto）提出了同步的突破性數(shù)學(xué)模型

圖源：Tomoaki Sukezane

旋律與寂靜

在1990年代初，斯特羅加茨與他的學(xué)生渡邊真也（Shinya Watanabe）一起證明，即使對于有限數(shù)量的振子，Kuramoto的解不僅是可能的，而且是幾乎不可避免的。

2011年，澳大利亞國防科學(xué)與技術(shù)組織的理查德·泰勒（Richard Taylor）對Kuramoto關(guān)于圖必須是完全圖的條件進(jìn)行了挑戰(zhàn)。他證明了 https://arxiv.org/abs/1109.4451 每個(gè)節(jié)點(diǎn)至少與其他94%的節(jié)點(diǎn)相連的均勻圖必定能夠整體同步。泰勒的結(jié)果的優(yōu)勢在于它適用于具有任意連接結(jié)構(gòu)的圖，只要每個(gè)節(jié)點(diǎn)都有大量的鄰居。

2018年，班代拉、凌舒揚(yáng)和耶魯大學(xué)研究生徐瑞圖（音譯）將泰勒的每個(gè)節(jié)點(diǎn)連接到其他94%的節(jié)點(diǎn)的要求降低到79.3% https://epubs.siam.org/doi/10.1137/18M1217644 。

2020年，一個(gè)競爭團(tuán)隊(duì)達(dá)到了78.89%；2021年，斯特羅加茨、亞歷克斯·湯森德（Alex Townsend）和馬丁·卡薩博夫（Martin Kassabov）證明75%就足夠了，確立了當(dāng)前記錄 https://pubs.aip.org/aip/cha/article/31/7/073135/342231/Sufficiently-dense-Kuramoto-networks-are-globally 。

與此同時(shí)，研究人員也從相反的方向攻擊了這個(gè)問題，試圖找到高度連通但并未整體同步的圖。在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)了一個(gè)又一個(gè)可以避免整體同步的圖，盡管每個(gè)節(jié)點(diǎn)都與超過68%的其他節(jié)點(diǎn)相連。

許多這樣的圖類似于人們手拉手圍成的圈，每個(gè)人伸出手去接觸10個(gè)甚至100個(gè)附近的鄰居。這些圖被稱為環(huán)形圖（ring graph），可以進(jìn)入一種狀態(tài)，其中每個(gè)振子相對于下一個(gè)都有輕微的偏移。

顯然，圖結(jié)構(gòu)對同步有重大影響。因此，凌、徐和班代拉對隨機(jī)生成圖的同步性質(zhì)產(chǎn)生了好奇心。為了使他們的工作更精確，他們使用了兩種常見的隨機(jī)構(gòu)建圖的方法。

第一個(gè)是以保羅·埃爾德什（Paul Erd?s，1913 - 1996）和阿爾弗雷德·雷尼（Alfréd Rényi,1921 - 1970）命名的模型，他們是兩位杰出的圖論學(xué)家，在該模型上做了開創(chuàng)性的工作。

要使用埃爾德什-雷尼（Erd?s-Rényi）模型構(gòu)建圖，可從一些未連接的節(jié)點(diǎn)開始。然后對于每一對節(jié)點(diǎn)，以概率p隨機(jī)地將它們連接起來。如果p是1%，你就有1%的機(jī)率連接邊；如果p是50%，平均每個(gè)節(jié)點(diǎn)將連接到其他一半節(jié)點(diǎn)。

如果p略大于一個(gè)取決于圖中節(jié)點(diǎn)數(shù)量的閾值，那么該圖極有可能形成一個(gè)相互連接的網(wǎng)絡(luò)（而不是由不相連的聚類組成）。隨著圖的大小增長，這個(gè)閾值變得極小，因此對于足夠大的圖，即使p很小，使得邊的總數(shù)也較小，Erd?s-Rényi圖也將是連通的。

第二種他們考慮的圖稱為d-正則圖（d-regular graph）。在這種圖中，每個(gè)節(jié)點(diǎn)都有相同數(shù)量（即d）的邊。（因此，在3-正則圖中，每個(gè)節(jié)點(diǎn)連接到其他3個(gè)節(jié)點(diǎn)，在7-正則圖中，每個(gè)節(jié)點(diǎn)連接到其他7個(gè)節(jié)點(diǎn)，依此類推。）

擴(kuò)展圖：

有相對少的邊（這里每個(gè)結(jié)點(diǎn)只有3條邊），但有高的連通度。

連通性差的圖：

從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)，只有很少的邊

圖源：Merrill Sherman|Quanta

圖雖然稀疏——只有少量邊——但連接良好，被稱為擴(kuò)展圖（expander graph）。這些圖在數(shù)學(xué)、物理和計(jì)算機(jī)科學(xué)的許多領(lǐng)域都很重要，但如果你想要構(gòu)建具有特定性質(zhì)的擴(kuò)展圖，你會發(fā)現(xiàn)這是一個(gè)“出人意料的不平凡問題”，著名數(shù)學(xué)家陶哲軒（Terry Tao）如是說 https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/ 。盡管Erd?s-Rényi圖并不總是擴(kuò)展圖，但它們共有許多重要特征。結(jié)果發(fā)現(xiàn)，如果你構(gòu)建一個(gè)d-正則圖并隨機(jī)連接邊，你將得到一個(gè)擴(kuò)展圖。

連接兩頭

2018年，凌、徐和班代拉猜測連通閾值可能也度量整體同步的出現(xiàn)：如果生成一個(gè)p略大于閾值的Erd?s-Rényi圖，該圖應(yīng)該整體同步。他們在這一猜想上取得了一定的進(jìn)展，而斯特羅加茨、卡薩博夫和湯森德后來改進(jìn)了他們的結(jié)果。但他們的數(shù)字與連通閾值之間仍存在很大的差距。

2022年3月，湯森德訪問了蘇黎世的班代拉。他們意識到有機(jī)會達(dá)到連接閾值，于是邀請了班代拉的畢業(yè)生佩德羅·阿布達(dá)拉（Pedro Abdalla），阿布達(dá)拉又招募了他的朋友維克托·索薩（Victor Souza）。阿布達(dá)拉和索薩開始商討細(xì)節(jié)，但很快遇到了障礙。

似乎隨機(jī)性伴隨著不可避免的問題。除非p顯著大于連接閾值，否則每個(gè)節(jié)點(diǎn)擁有的邊數(shù)可能會出現(xiàn)大幅波動。一個(gè)節(jié)點(diǎn)可能連接了100條邊；另一個(gè)節(jié)點(diǎn)可能沒有連接任何邊?！熬拖衩總€(gè)好問題一樣，它會反擊，”索薩說。

阿布達(dá)拉和索薩意識到從隨機(jī)圖的角度來解決這個(gè)問題是不可行的。相反，他們會利用大多數(shù)Erd?s-Rényi圖都是擴(kuò)展圖的事實(shí)?！霸谶@個(gè)看似無辜的改變之后，拼圖的許多碎片開始落位，”索薩說。

“最終，我們得到了一個(gè)比我們預(yù)期的結(jié)果更強(qiáng)的結(jié)果?！眻D有一個(gè)稱為擴(kuò)展系數(shù)（expansion）的數(shù)字，它衡量將圖分成兩半的難度，這兩半按圖的大小進(jìn)行標(biāo)準(zhǔn)化。這個(gè)數(shù)字越大，通過移除節(jié)點(diǎn)將其分成兩半就越困難。

阿方索·班代拉在過去六年里試圖理解迫使振子同步的條件

圖源：Giulia Marthaler

在接下來的幾個(gè)月里，團(tuán)隊(duì)完善了其余的論據(jù)，并在10月份將他們的論文發(fā)布在網(wǎng)上。他們的證明 https://arxiv.org/abs/2210.12788 表明，給定足夠的時(shí)間，如果圖有足夠大的擴(kuò)展系數(shù)，均勻Kuramoto模型將始終整體同步。

沿著唯一的道路

在對同步的數(shù)學(xué)研究中最大未解之謎之一，只需在新論文中對模型進(jìn)行微小調(diào)整：如果一些振子相互拉入同步，而另一些則將其推出同步，會發(fā)生什么？在這種情況下，“我們幾乎所有工具都立即消失了，”索薩說。

如果研究人員能在這一版本的問題上取得進(jìn)展，這些技術(shù)可能會幫助班代拉解決他在轉(zhuǎn)向同步之前設(shè)定的數(shù)據(jù)聚類問題。

除此之外，除了擴(kuò)展圖之外，還有比整體同步更復(fù)雜的模式，以及不假設(shè)每個(gè)節(jié)點(diǎn)和邊都相同的同步模型。2018年，加州大學(xué)圣塔芭芭拉分校的Saber Jafarpour和Francesco Bullo提出了一種適用于整體同步的測試方法 https://ieeexplore.ieee.org/document/8496811 ，該方法在旋轉(zhuǎn)器不具有相同權(quán)重和偏好頻率時(shí)仍然有效。

Bianconi的團(tuán)隊(duì) https://journals.aps.org/pre/abstract/10.1103/PhysRevE.99.022307 以及其他研究人員 https://www.nature.com/articles/s41467-021-21486-9 一直在與涉及三個(gè)、四個(gè)或更多節(jié)點(diǎn)的網(wǎng)絡(luò)鏈接進(jìn)行合作，而不僅僅是針對成對節(jié)點(diǎn)。

班代拉和阿布達(dá)拉已經(jīng)試圖超越Erd?s-Rényi模型和d-正則模型，轉(zhuǎn)向其他更現(xiàn)實(shí)的隨機(jī)圖模型。去年八月，他們與克拉拉·因韋尼齊（Clara Invernizzi）共同發(fā)表了一篇關(guān)于隨機(jī)幾何圖同步的論文 https://arxiv.org/abs/2208.12246 。

在1961年構(gòu)思的隨機(jī)幾何圖中，節(jié)點(diǎn)在空間中隨機(jī)分布，可能在一個(gè)球面或平面上。如果節(jié)點(diǎn)之間的距離在一定范圍內(nèi)，則在這些節(jié)點(diǎn)之間放置邊。其發(fā)明者埃德加·吉爾伯特（Edgar Gilbert）希望以此模型模擬只能短距離傳輸消息的通信網(wǎng)絡(luò)，或者需要近距離接觸才能傳播的傳染病的擴(kuò)散。班代拉說，隨機(jī)幾何模型還能更好地刻畫一群螢火蟲之間的聯(lián)系，它們通過觀察鄰居來實(shí)現(xiàn)同步。

當(dāng)然，將數(shù)學(xué)結(jié)果與現(xiàn)實(shí)世界聯(lián)系起來具有挑戰(zhàn)性。“我認(rèn)為說這是由應(yīng)用所驅(qū)動的是個(gè)無傷大雅的小謊言，”斯特羅加茨說，他還指出，均勻Kuramoto模型永遠(yuǎn)無法刻畫生物系統(tǒng)中的固有變異。索薩補(bǔ)充說：“還有很多基本問題我們不知道如何解決。這更像是在探索叢林。”

參考資料

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ù)學(xué)書單推薦、數(shù)學(xué)科普作家自薦、出版社書單推薦通道已陸續(xù)打開，敬請期待】

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

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號主頁

右上角

數(shù)學(xué)科普不迷路！