Nov dokaz kaže, da se 'razširitveni' grafi sinhronizirajo | Revija Quanta

Pred šestimi leti sta Afonso Bandeira in Shuyang Ling poskušala najti boljši način za razločevanje grozdov v ogromnih nizih podatkov, ko sta naletela na nadrealistični svet. Ling je spoznal, da se enačbe, ki so jih iznašli, nepričakovano odlično ujemajo z matematičnim modelom spontane sinhronizacije. Spontana sinhronizacija je pojav, pri katerem se oscilatorji, ki so lahko v obliki nihala, vzmeti, človeških srčnih celic ali kresnic, na koncu premikajo v koraku brez kakršnega koli osrednjega koordinacijskega mehanizma.

Bandeira, matematik na Švicarski zvezni tehnološki inštitut Zurich, in Ling, a podatkovni znanstvenik na Univerzi v New Yorku, se je poglobil v raziskave sinhronizacije in pridobil vrsto omembe vrednih rezultatov o moči in strukturi, ki jo morajo imeti povezave med oscilatorji, da prisilijo oscilatorje k sinhronizaciji. To delo je doseglo vrhunec v oktobrskem prispevku, v katerem je Bandeira dokazal (skupaj s petimi soavtorji), da sinhronizacija je neizogibna v posebnih vrstah omrežij, imenovanih razširitveni grafi, ki so redki, a tudi dobro povezani.

Izkazalo se je, da imajo razširitveni grafi množico aplikacij ne le v matematiki, ampak tudi v računalništvu in fiziki. Uporabljajo se lahko za ustvarjanje kod za popravljanje napak in za ugotavljanje, kdaj se simulacije, ki temeljijo na naključnih številkah, približajo resničnosti, ki jo poskušajo simulirati. Nevrone je mogoče modelirati v grafu, za katerega nekateri raziskovalci verjamejo, da tvori ekspander zaradi omejenega prostora za povezave v možganih. Grafi so uporabni tudi geometrom, ki poskušajo razumeti kako prečkati zapletene površine, med drugimi težavami.

Novi rezultat "res daje ogromen vpogled v to, katere vrste struktur grafov bodo zagotovile sinhronizacijo," je dejal Lee DeVille, matematik na Univerzi v Illinoisu, ki ni bil vključen v delo.

Grenka in sladka sinhronizacija         

"Sinhronizacija je res eden temeljnih pojavov narave," je dejal victor souza, matematik z Univerze v Cambridgeu, ki je sodeloval z Bandeiro na papirju. Razmislite o celicah srčnega spodbujevalnika v vašem srcu, ki sinhronizirajo svoje utripanje z električnimi signali. V laboratorijskih poskusih "lahko dobite na stotine ali tisoče teh embrionalnih celic srčnega spodbujevalnika, ki utripajo usklajeno," je dejal Steven Strogatz, matematik na Univerzi Cornell in drugi soavtor. »Nekako grozljivo je, ker ni celo srce; je le na ravni celic.«

Leta 1975 je japonski fizik Yoshiki Kuramoto predstavil matematični model, ki opisuje tovrsten sistem. Njegov model deluje na omrežju, imenovanem graf, kjer so vozlišča povezana s črtami, imenovanimi robovi. Vozlišča se imenujejo soseda, če so povezana z robom. Vsakemu robu je mogoče dodeliti številko, imenovano utež, ki kodira moč povezave med vozlišči, ki jih povezuje.

V Kuramotovem sinhronizacijskem modelu vsako vozlišče vsebuje oscilator, ki je predstavljen s točko, ki se vrti okoli kroga. Ta točka kaže, recimo, kje je srčna celica v svojem pulzacijskem ciklu. Vsak oscilator kroži s svojo želeno hitrostjo. Toda oscilatorji se želijo ujemati tudi s sosedi, ki morda krožijo na drugi frekvenci ali na drugi točki v svojem ciklu. (Teža roba, ki povezuje dva oscilatorja, meri moč sklopitve med njima.) Odstopanje od teh preferenc prispeva k porabi energije, ki jo oscilator porabi. Sistem poskuša uravnotežiti vse konkurenčne želje tako, da minimizira svojo skupno energijo. Kuramotov prispevek je bil dovolj poenostaviti te matematične omejitve, da so lahko matematiki napredovali pri proučevanju sistema. V večini okoliščin je tako velike sisteme sklopljenih diferencialnih enačb skoraj nemogoče rešiti.

Kljub svoji preprostosti se je model Kuramoto izkazal za uporabnega za modeliranje sinhronizacije v omrežjih od možganov do električnih omrežij, je dejal Ginestra Bianconi, uporabni matematik na univerzi Queen Mary v Londonu. "V možganih ni posebej natančen, vendar se razume kot zelo učinkovit," je dejala.

"Tukaj je zelo lep ples med matematiko in fiziko, ker model, ki zajame pojav, vendar ga je zelo težko analizirati, ni zelo uporaben," je dejal Souza.

V svojem dokumentu iz leta 1975 je Kuramoto domneval, da je vsako vozlišče povezano z vsakim drugim vozliščem v tako imenovanem popolnem grafu. Od tam je pokazal, da bi za neskončno število oscilatorjev, če bi bila povezava med njimi dovolj močna, lahko ugotovil njihovo dolgoročno obnašanje. Ob dodatni predpostavki, da imajo vsi oscilatorji enako frekvenco (kar bi pomenilo nekaj, čemur bi rekli homogeni model), je našel rešitev, v kateri bi se vsi oscilatorji na koncu vrteli hkrati, pri čemer bi vsak zaokrožil isto točko na svojih krogih točno na istočasno. Čeprav večina grafov v resničnem svetu še zdaleč ni popolna, je Kuramotoov uspeh privedel matematike do vprašanja, kaj bi se zgodilo, če bi omilili njegove zahteve.

Melodija in tišina

V začetku devetdesetih let prejšnjega stoletja je skupaj s svojim študentom Shinya Watanabe, Strogatz je pokazal, da Kuramotova rešitev ni le mogoča, ampak skoraj neizogibna, tudi za končno število oscilatorjev. leta 2011, Richard Taylor iz avstralske organizacije za obrambno znanost in tehnologijo je zavrnil Kuramotovo zahtevo, da mora biti graf popoln. On dokazano da se bodo homogeni grafi, kjer je vsako vozlišče povezano z vsaj 94 % drugih, zagotovo globalno sinhronizirali. Taylorjev rezultat je imel to prednost, da se je uporabljal za grafe s poljubnimi strukturami povezljivosti, dokler je imelo vsako vozlišče veliko število sosedov.

Leta 2018 so Bandeira, Ling in Ruitu Xu, podiplomski študent na univerzi Yale, znižal Taylorjevo zahtevo da je vsako vozlišče povezano s 94 % ostalih na 79.3 %. Leta 2020 je konkurenčna skupina dosegla 78.89 %; leta 2021, Strogatz, Alex Townsend in Martin Kassabov ustanovljena trenutni rekord ko so pokazali, da je 75% dovolj.

Medtem so raziskovalci problem napadli tudi iz nasprotne smeri in poskušali najti grafe, ki so bili zelo povezani, vendar se niso globalno sinhronizirali. V seriji prispevkov od 2006 da 2022, so odkrili graf za grafom, ki bi se lahko izognili globalni sinhronizaciji, čeprav je bilo vsako vozlišče povezano z več kot 68 % drugih. Mnogi od teh grafov spominjajo na krog ljudi, ki se držijo za roke, kjer vsaka oseba doseže 10 ali celo 100 bližnjih sosedov. Ti grafi, imenovani obročni grafi, se lahko usedejo v stanje, kjer je vsak oscilator nekoliko zamaknjen od naslednjega.

Jasno je, da struktura grafa močno vpliva na sinhronizacijo. Tako so Ling, Xu in Bandeira postali radovedni glede sinhronizacijskih lastnosti naključno ustvarjenih grafov. Da bi bilo njihovo delo natančno, so uporabili dve običajni metodi za naključno gradnjo grafa.

Prvi je poimenovan po Paulu Erdősu in Alfrédu Rényiju, dveh uglednih teoretikih grafov, ki sta opravila temeljno delo na modelu. Če želite zgraditi graf z uporabo modela Erdős-Rényi, začnete s kupom nepovezanih vozlišč. Nato za vsak par vozlišč ju z določeno verjetnostjo naključno povežete skupaj p. Če p je 1 %, povežete robove 1 % časa; če je 50 %, se bo vsako vozlišče v povprečju povezalo s polovico drugih.

If p nekoliko večji od praga, ki je odvisen od števila vozlišč v grafu, bo graf z veliko verjetnostjo tvoril eno medsebojno povezano mrežo (v nasprotju z grozdi, ki se ne povezujejo). Ko velikost grafa raste, postane ta prag majhen, tako da pri dovolj velikih grafih, tudi če p majhna, zaradi česar je tudi skupno število robov majhno, bodo Erdős-Rényijevi grafi povezani.

Druga vrsta grafa, ki so jo obravnavali, se imenuje a d- navaden graf. V takih grafih ima vsako vozlišče enako število robov, d. (Torej je v 3-pravilnem grafu vsako vozlišče povezano s 3 drugimi vozlišči, v 7-pravilnem grafu je vsako vozlišče povezano s 7 drugimi vozlišči in tako naprej.)

Grafi, ki so dobro povezani, čeprav so redki – imajo le majhno število robov – so znani kot razširitveni grafi. Te so pomembne na številnih področjih matematike, fizike in računalništva, a če želite zgraditi razširitveni graf z določenim naborom lastnosti, boste ugotovili, da je to "presenetljivo netrivialen problem," po navedbah ugledni matematik Terry Tao. Grafi Erdős-Rényi, čeprav niso vedno razširitveni, imajo skupne številne pomembne značilnosti. In jazvendar se izkaže, da če sestavite a d-pravilni graf in naključno povežite robove, dobili boste razširitveni graf.

Zbliževanje konca s koncem

Leta 2018 so Ling, Xu in Bandeira ugibali, da bi lahko prag povezljivosti meril tudi pojav globalne sinhronizacije: če ustvarite Erdős-Rényijev graf z p samo malo večji od praga, bi se moral graf globalno sinhronizirati. Pri tej domnevi so delno napredovali, Strogatz, Kassabov in Townsend pa so kasneje izboljšali svoj rezultat. Toda med njihovim številom in pragom povezljivosti je ostal velik razmik.

Marca 2022 je Townsend obiskal Bandeiro v Zürichu. Ugotovili so, da imajo možnost doseči prag povezljivosti, in pripeljali Pedro Abdalla, Bandeirin podiplomski študent, ki je nato k sodelovanju vključil svojega prijatelja Victorja Souzo. Abdalla in Souza sta začela urejati podrobnosti, a sta hitro naletela na ovire.

Zdelo se je, da je naključnost prišla z neizogibnimi težavami. Razen p je bil znatno večji od praga povezljivosti, je verjetno prišlo do divjih nihanj v številu robov, ki jih je imelo vsako vozlišče. Eden je lahko pritrjen na 100 robov; drugi morda ni povezan z nobenim. "Kot pri vsaki dobri težavi se tudi ta bori nazaj," je dejal Souza. Abdalla in Souza sta ugotovila, da pristop k problemu z vidika naključnih grafov ne bo deloval. Namesto tega bi uporabili dejstvo, da je večina Erdős-Rényijevih grafov ekspanderjev. "Po tej nedolžni spremembi se je veliko kosov sestavljanke začelo postavljati na svoje mesto," je dejal Souza. "Na koncu imamo rezultat, ki je veliko močnejši, kot smo pričakovali." Grafi imajo številko, imenovano razširitev, ki meri, kako težko jih je razrezati na dva dela, normalizirana na velikost grafa. Večje kot je to število, težje ga je razdeliti na dvoje z odstranitvijo vozlišč.

V naslednjih nekaj mesecih je ekipa izpolnila preostanek argumenta in oktobra objavila svoj članek na spletu. Njihov dokaz kaže, da se bo homogeni model Kuramoto vedno globalno sinhroniziral, če ima graf dovolj razširitve.

Dol po edini cesti

Ena od največjih preostalih skrivnosti v matematični študiji sinhronizacije zahteva le majhno prilagoditev modela v novem dokumentu: kaj se zgodi, če se nekateri pari oscilatorjev medsebojno potegnejo v sinhronizacijo, drugi pa se potisnejo iz nje? V tej situaciji "skoraj vse naše orodje takoj izgine," je dejal Souza. Če lahko raziskovalci napredujejo pri tej različici problema, bi tehnike Bandeiri verjetno pomagale pri reševanju težav z združevanjem podatkov, ki jih je nameraval rešiti, preden se je obrnil na sinhronizacijo.

Poleg tega obstajajo razredi grafov poleg razširiteljev, vzorcev, ki so bolj zapleteni od globalne sinhronizacije, in sinhronizacijskih modelov, ki ne predpostavljajo, da sta vsako vozlišče in rob enaka. Leta 2018 sta Saber Jafarpour in Francesco Bullo s kalifornijske univerze v Santa Barbari predlagal test za globalno sinhronizacijo, ki deluje, ko rotatorji nimajo enakih uteži in prednostnih frekvenc. Bianconijeva ekipa in drugi so delali z omrežji, katerih povezave vključujejo tri, štiri ali več vozlišč, ne le parov.

Bandeira in Abdalla že poskušata preseči Erdős-Rényi in d-regularnih modelov v druge, bolj realistične modele naključnih grafov. Avgusta lani so delil papir, v soavtorstvu s Claro Invernizzi, o sinhronizaciji v naključnih geometrijskih grafih. V naključnih geometrijskih grafih, ki so bili zasnovani leta 1961, so vozlišča naključno razpršena v prostoru, morda na površini, kot je krogla ali ravnina. Robovi so nameščeni med pari vozlišč, če so med seboj na določeni razdalji. Njihov izumitelj Edgar Gilbert je upal na model komunikacijskih omrežij, v katerih lahko sporočila potujejo le na kratke razdalje, ali širjenje nalezljivih patogenov, ki za prenos potrebujejo tesen stik. Naključni geometrijski modeli bi tudi bolje zajeli povezave med kresnicami v roju, ki se sinhronizirajo tako, da opazujejo svoje sosede, je dejal Bandeira.

Seveda je povezovanje matematičnih rezultatov z resničnim svetom zahtevno. "Mislim, da bi bilo malo neumno trditi, da to zahtevajo aplikacije," je dejal Strogatz, ki je tudi opozoril, da homogeni Kuramoto model nikoli ne more zajeti inherentne variacije v bioloških sistemih. Souza je dodal: »Obstaja veliko temeljnih vprašanj, ki jih še vedno ne vemo, kako rešiti. To je bolj kot raziskovanje džungle.”

Opomba urednika: Steven Strogatz gosti podcast “Joy of Why” za Quanta in je nekdanji član znanstvenega svetovalnega odbora revije. Bil je intervjuvan za ta članek, vendar sicer ni prispeval k njegovi produkciji.