Ósamstillt bootstrap percolation

Í síðustu færslu fjölluðum við um bootstrap percolation, keðjuverkun þar sem hnútur í neti virkjast þegar nógu margir nágrannar hans eru virkir. Ferlið lýsir því hvernig upplýsingar dreifast um net. Í þessari færslu skoðum við lítið afbrigði af því. Hefðbundin skilgreining á percolation gerir ráð fyrir að ferlið gangi í umferðum. Í raunveruleikanum eru ferli á borð við útbreiðslu orðróms, smit sjúkdóma og taugaboð hins vegar yfirleitt ekki samstillt. Það leiðir okkur að ósamstilltri útgáfu af ferlinu (skrunaðu niður ef þú getur ekki beðið eftir að sjá hermunina).

Eins og áður má hugsa sér að þegar hnútur verður virkur sendi hann skilaboð til allra nágranna sinna um nýja ástandið sitt (eða smiti þá af einhverjum sjúkdómi). Skilaboðin berast ekki samstundis. Í samstillta ferlinu þurftum við að bíða í eina umferð eftir þeim, sem samsvarar töf upp á 1. Í ósamstillta ferlinu geta tafirnar verið hvað sem er. Í [2] skoðuðum við til dæmis tilvikið þar sem töf hvers leggjar er dregin úr veldisdreifingu með væntigildi 1. Munum að eins og í [4] rannsökuðum við ferlið á $G_{n,p}$, sem er Erdős–Rényi-slembinetið. Í ljós kom að þessi litla breyting hafði áhugaverð megindleg áhrif á ferlið. Virknin breiddist miklu hraðar út!

Við sýndum að þegar netið stækkar er væntur tími þar til allir hnútar eru orðnir virkir aðeins fasti, á meðan samstillta ferlið getur þurft allt að $\sim\log\log(np)$ umferðir að jafnaði. Hraðinn skýrist af því að þegar nógu mörg skilaboð eru á leiðinni er nánast öruggt að einhver þeirra verði mjög hröð, og það knýr ferlið enn frekar áfram. Það má hugsa sér ferlið í þremur fösum: ræsingarfasanum, sem ræður því hvort virknin lifir af eða ekki, sprengifasanum, þar sem nær allir hnútar verða virkir (og sem skýrir að mestu tvöfaldan veldisvöxt ferlisins sem gengur í umferðum), og loks frágangsfasanum, þar sem síðustu hnútarnir verða virkir. Í okkar líkani gerist sprengifasinn samstundis. Formlega tekur það tíma $o(1)$ (minna en fasta) að virkja nær alla hnútana, eftir fyrstu hindrunina, sem er að koma ferlinu af stað.

Hér fyrir neðan er útfærsla á ósamstilltu útgáfunni af bootstrap percolation þar sem vænt töf skilaboða er í upphafi stillt á fimm sekúndur (þú getur leikið þér með stikana í reitunum hér fyrir neðan, en of margir hnútar geta hægt verulega á öllu). Ef þú velur stikana vel sérðu að hægu skilaboðin eru yfirleitt of sein til að skipta nokkru máli. Hermunin var gerð með d3js. Þar sem JavaScript er ósamstillt hentar það fullkomlega í svona hermanir.

Í næstu færslu bæti ég hamlandi hnútum við ferlið.