Ef þú hefur einhvern tímann rekist á enska orðið percolation hefur það kannski verið í tengslum við kaffi. Þegar hellt er upp á kaffi með því að láta vatn renna í gegnum malaðar kaffibaunir viljum við jú að vatnið komist á endanum í gegn. Kornin þurfa því að vera nógu stór til að efnið sé gljúpt og vatnið nái að seytla (e. percolate) í gegn. Þessi grein fjallar ekki um kaffigerð, nema þú viljir verða mjög skapandi, en hafðu samt í huga að ómælt magn af koffíni kom við sögu þegar hún var skrifuð.
Hvers konar percolation ertu þá að tala um? Útskýrðu þetta eins og ég sé fimm ára.
Ímyndaðu þér að vinur þinn hafi verið að fá nýtt og glansandi leikfang. Hann sýnir þér það og þig langar í það. Þú biður foreldra þína um það en þau segja nei. Smám saman eignast fleiri vinir þínir leikfangið og þig langar enn í það. Foreldrar þínir segja áfram nei, en þau átta sig á að þetta yrði frábær gjöf og kaupa leikfangið handa þér í næstu afmælisgjöf.
Þú hefur sennilega þegar séð hvernig þetta litla dæmi tengist kaffiuppáhellingu. Ef ekki skal ég útskýra. Hugsaðu um sjálfan þig sem tómt hólf sem afmarkast af fínmöluðum kaffikornunum í kringum þig. Ef það er ekki of óþægileg tilhugsun geturðu hugsað um vini þína sem aðliggjandi hólf. Þegar einn vina þinna fékk nýtt leikfang fylltist hólfið hans af vatni, í þessari líkingu. Ef aðeins eitt aðliggjandi hólf er fullt af vatni nægir þrýstingurinn ekki til að vatnið komist inn í þitt hólf, en þegar nógu mörg aðliggjandi hólf hafa fyllst fyllist þitt líka.
Percolation hefur sem sagt eitthvað með það að gera hvernig upplýsingar dreifast um net. Önnur góð dæmi eru slúður og orðrómur, og líka auglýsingaherferðir: þar skiptir máli að vita hvaða einstaklingum í félagsneti borgar sig að greiða fyrir að auglýsa vöru til að ná til sem flestra mögulegra viðskiptavina (þú mátt alveg byrja að senda mér ókeypis vörur). Það er líka dýrmætt að vita hvort bankakerfi sé stöðugt og hversu margir þurfa að lenda í vanskilum með lánin sín til að kerfið hrynji [1]. Enn eitt gott dæmi er útbreiðsla sjúkdóma. Í hvert sinn sem maður hittir smitaðan einstakling aukast líkurnar á að smitast. Uppáhaldsdæmið mitt um bootstrap percolation (keðjuverkun þar sem hnútur virkjast þegar nógu margir nágrannar hans eru virkir) er hvernig taugafrumur í heilanum eiga samskipti. Taugafrumur tala saman með því að senda taugaboð til nágranna sinna. Ef taugafruma fær nokkur taugaboð sendir hún sjálf frá sér taugaboð og lætur þannig alla nágranna sína vita, sem er alveg magnað. Loks má lýsa percolation með frumusjálfvirkja (e. cellular automaton), en það var í því samhengi sem ferlið var fyrst rannsakað [6] (reyndar með eðlisfræði að leiðarljósi), og síðan þá hefur það verið rannsakað ítarlega á grindum í hversu mörgum víddum sem er [3].
Eins og þú hefur kannski áttað þig á er percolation bókstaflega allt í kringum okkur. Það kemur því ekki á óvart að áhuginn á fyrirbærinu hafi seytlað víða. Hér á eftir skilgreini ég ferlið nákvæmar. Þar fer þetta að verða örlítið tæknilegt. Ef þú vilt sleppa tæknilegu hlutunum geturðu bara skrunað neðst í greinina og leikið þér með JavaScript-hermunina.
Bootstrap percolation (líka þekkt sem iterative retrieval) er einfalt líkan af því hvernig virkni breiðist út í neti. Hnútarnir í ferlinu geta verið í tveimur ástöndum, annaðhvort virkir eða óvirkir. Hefðbundið er að ferlið gangi í umferðum. Látum K>0 vera þröskuld. Í hverri umferð verða allir óvirkir hnútar virkir sem hafa að minnsta kosti K virka nágranna frá fyrri umferðum. Þegar hnútur er orðinn virkur helst hann virkur það sem eftir er ferlisins. Orðið bootstrap vísar einfaldlega til upphafsmengisins, þ.e. hnútanna sem eru virkir í upphafi, og percolation til útbreiðslu virkninnar.
Þetta er algengasta skilgreiningin, en til eru ýmis afbrigði af ferlinu sem ég fer ekki út í hér. Þegar hnútur verður virkur í lýsingunni hér að ofan má hugsa sér að hann segi öllum nágrönnum sínum frá því, og að það taki þessi skilaboð eina umferð að berast.
Yfirleitt er ferlið rannsakað með formlegum hætti á tilteknum flokkum neta, og eins og ég nefndi hér að ofan voru grindur þær fyrstu sem urðu fyrir valinu. Ég hef verið svo heppinn að vinna með frábæru fólki að nokkrum verkefnum um bootstrap percolation [2], sem verða efni í seinni færslu. Kveikjan að rannsókn okkar voru niðurstöður Janson, Luczak, Turova og Vallier [4], sem greindu bootstrap percolation, ferlið hér að ofan, á Erdős–Rényi-slembinetinu. Slembinetið er frekar einfalt: hver leggur er til staðar, óháð hinum, með einhverjum líkum p, sem eru stiki líkansins. Með n hnúta er væntigildi fjölda nágranna því np. Janson og félagar uppgötvuðu að percolation hefur þröskuldseiginleika á slembinetinu. Ef upphafsmengið er undir þröskuldinum verða nær engir fleiri hnútar virkir. En ef það er yfir þröskuldinum breiðist virknin út, þ.e. nær allir hnútar verða virkir.
Hér fyrir neðan geturðu leikið þér með ferlið á slembinetinu. Þú velur stikana hér fyrir neðan og getur auk þess skipt hnútum milli þess að vera virkir og óvirkir með því að smella á þá. Hermunin var gerð með visjs og kóðinn er aðgengilegur á GitHub-síðunni minni. Athugaðu að eins og er vex keyrslutími kóðans með n í öðru veldi, svo hermun fyrir stór gildi á n verður hæg. Auk þess á uppröðun netsins erfitt með að ná stöðugu ástandi þegar hnútarnir eru margir og netið er ekki strjált.
Í næstu færslu skoða ég afbrigði af ferlinu sem gengur ekki í umferðum.
Þakkir
Ég þakka Guðmundi fyrir að lesa yfir drög að þessari færslu.