Teorie perkolace - Percolation theory

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

v statistická fyzika a matematika, teorie perkolace popisuje chování sítě při odstraňování uzlů nebo odkazů. Jedná se o geometrický typ fázového přechodu, protože při kritickém zlomku odstranění se síť rozpadá na podstatně menší připojeno shluky. Aplikace teorie perkolace na věda o materiálech a v mnoha dalších oborech jsou diskutovány zde a v článcích teorie sítí a perkolace.

Úvod

Trojrozměrný graf perkolace stránek

Perkolace vazby ve čtvercové mřížce od p = 0,3 do p = 0,52

The Teorie Floryho-Stockmayera byla první teorie zkoumající perkolační procesy.^[1]

Reprezentativní otázka (a zdroj názvu) je následující. Předpokládejme, že na některé je nalita nějaká tekutina porézní materiál. Bude kapalina schopna dostat se z díry do díry a dosáhnout dna? Tato fyzická otázka je modelován matematicky jako a trojrozměrná síť z n × n × n vrcholy, obvykle nazývané "weby", ve kterých okraj nebo „vazby“ mezi každým dvěma sousedy mohou být otevřené (propouštějící kapalinu) s pravděpodobností str, nebo uzavřen s pravděpodobností 1 – stra předpokládá se, že jsou nezávislé. Proto za dané strJaká je pravděpodobnost, že otevřená cesta (tj. cesta, jejíž každý odkaz je „otevřenou“ vazbou) existuje shora dolů? Chování pro velkén je prvořadým zájmem. Tento problém se nazývá nyní perkolace dluhopisů, byl v matematické literatuře zaveden uživatelem Broadbent & Hammersley (1957),^[2] a od té doby ho intenzivně studovali matematici a fyzici.

V mírně odlišném matematickém modelu pro získání náhodného grafu je místo „obsazeno“ pravděpodobností str nebo „prázdný“ (v tom případě jsou jeho okraje odstraněny) s pravděpodobností 1 – str; volá se odpovídající problém perkolace webu. Otázka je stejná: pro daný strJaká je pravděpodobnost, že existuje cesta mezi horním a dolním okrajem? Podobně je možné se zeptat, vzhledem k připojenému grafu, v jakém zlomku 1 – str poruch se graf odpojí (žádná velká součást).

Stanovení perkolace sítě 3D trubice

Stejné otázky lze položit pro jakoukoli dimenzi mřížky. Jak je docela typické, je skutečně jednodušší zkoumat nekonečný sítí než jen velkých. V tomto případě odpovídá otázka: existuje nekonečný otevřený klastr? To znamená, existuje cesta propojených bodů nekonečné délky „skrz“ síť? Podle Kolmogorovův zákon nula jedna, pro všechny dané str, pravděpodobnost, že existuje nekonečný shluk, je buď nula, nebo jedna. Protože tato pravděpodobnost je rostoucí funkcí str (důkaz prostřednictvím spojka argument), musí existovat a kritický str (označenostr_C) pod kterou je pravděpodobnost vždy 0 a nad kterou je pravděpodobnost vždy 1. V praxi je tato kritičnost velmi snadno pozorovatelná. Dokonce pro n tak malé jako 100, pravděpodobnost otevřené cesty shora dolů se prudce zvyšuje z velmi blízké nule na velmi blízkou jedné v krátkém rozpětí hodnotstr.

Detail perkolace vazby na čtvercové mřížce ve dvou rozměrech s pravděpodobností perkolace str = 0.51

U většiny nekonečných mřížkových grafů str_C nelze v některých případech přesně vypočítat str_C existuje přesná hodnota. Například:

• pro čtvercová mříž ℤ² ve dvou rozměrech, str_C = 1/2 pro perkolaci dluhopisů, což je otázka, která byla otevřenou otázkou po více než 20 let a kterou nakonec vyřešil Harry Kesten na začátku 80. let^[3] vidět Kesten (1982) chyba harvtxt: více cílů (2 ×): CITEREFKesten1982 (Pomoc). U perkolace webu hodnota str_C není známa z analytické derivace, ale pouze prostřednictvím simulací velkých mřížek.^[4]  
• Mezní případ pro mříže ve vysokých rozměrech je dán Bethe mříž, jehož prahová hodnota je str_C = 1/z − 1 pro koordinační číslo  z. Jinými slovy: pro pravidelné strom stupně ${ displaystyle z}$, ${ displaystyle p_ {c}}$ je rovný ${ displaystyle 1 / (z-1)}$.

• Náhodně Sítě Erdős – Rényi průměrného stupně ${ displaystyle langle k rangle}$, str_C = 1/⟨K⟩.^[5][6][7]

Univerzálnost

The princip univerzálnosti uvádí, že číselná hodnota str_C je určována místní strukturou grafu, zatímco chování poblíž kritické prahové hodnoty, str_C, se vyznačuje univerzálním kritické exponenty. Například distribuce velikosti klastrů při kritičnosti se rozpadá jako zákon síly se stejným exponentem pro všechny 2D mřížky. Tato univerzálnost znamená, že pro danou dimenzi jsou různé kritické exponenty, fraktální dimenze klastrů v str_C je nezávislý na typu mřížky a typu perkolace (např. vazba nebo místo). Nedávno však proběhla perkolace na a vážená planární stochastická mříž (WPSL) a zjistili, že ačkoliv se rozměr WPSL shoduje s rozměrem prostoru, kde je zabudován, jeho třída univerzality se liší od třídy všech známých rovinných mřížek.^[8][9]

Fáze

Podkritické a superkritické

Hlavním faktem v subkritické fázi je „exponenciální úpadek“. To je, když str < str_C, pravděpodobnost, že konkrétní bod (například počátek) je obsažen v otevřené shluku (což znamená maximální spojenou množinu „otevřených“ okrajů grafu) o velikosti r rozpadá se na nulu exponenciálně vr. To bylo prokázáno pro perkolaci ve třech a více rozměrech Menshikov (1986) a nezávisle na Aizenman & Barsky (1987). Ve dvou dimenzích to bylo součástí Kestenova důkazu str_C = 1/2.^[10]

The duální graf čtvercové mřížky ℤ² je také čtvercová mříž. Z toho vyplývá, že ve dvou dimenzích je superkritická fáze dvojí vůči subkritickému procesu perkolace. To poskytuje v podstatě úplné informace o superkritickém modelu s d = 2. Hlavním výsledkem superkritické fáze ve třech a více dimenzích je to, že je dostatečně velkáN, tady je^{[je zapotřebí objasnění ]} nekonečná otevřená hvězdokupa v dvojrozměrné desce ℤ² × [0, N]^{d − 2}. To prokázal Grimmett & Marstrand (1990) chyba harvtxt: více cílů (2 ×): CITEREFGrimmettMarstrand1990 (Pomoc).^[11]

Ve dvou rozměrech s str < 1/2, existuje s největší pravděpodobností jeden jedinečný nekonečný uzavřený shluk (uzavřený shluk je maximální spojená sada „uzavřených“ okrajů grafu). Subkritickou fázi lze tedy popsat jako konečné otevřené ostrovy v nekonečném uzavřeném oceánu. Když str > 1/2 nastává pravý opak, s konečnými uzavřenými ostrovy v nekonečném otevřeném oceánu. Obrázek je složitější, když d ≥ 3 od té doby str_C < 1/2, a existuje soužití nekonečných otevřených a uzavřených klastrů pro str mezi str_C a1 − str_CPro charakter perkolace fázového přechodu viz Stauffer a Aharony^[12] a Bunde a Havlin^[13] . Pro perkolaci sítí viz Cohen a Havlin.^[14]

Kritičnost

Zvětšení kritického perkolačního clusteru (kliknutím animujete)

Perkolace má a jedinečnost v kritickém bodě str = str_C a mnoho vlastností se chová jako zákon moci s ${ displaystyle p-p_ {c}}$, blízko ${ displaystyle p_ {c}}$. Teorie škálování předpovídá existenci kritické exponenty, v závislosti na počtu d dimenzí, které určují třídu singularity. Když d = 2 tyto předpovědi jsou podpořeny argumenty z teorie konformního pole a Evoluce Schramm – Loewner a zahrnují předpokládané číselné hodnoty pro exponenty. Hodnoty exponentů jsou uvedeny v.^[12][13] Většina z těchto předpovědí je domněnkových, kromě případů, kdy počet d rozměrů vyhovuje d = 2 nebo d ≥ 6. Obsahují:

• Neexistují žádné nekonečné klastry (otevřené nebo uzavřené)
• Pravděpodobnost, že existuje otevřená cesta z nějakého pevného bodu (řekněme počátek) do vzdálenosti r klesá polynomiálně, tj. je na objednávku r^α pro některéα
  • α nezávisí na konkrétní zvolené mřížce ani na jiných místních parametrech. Záleží jen na dimenzi d (toto je instance univerzálnost zásada).
  • α_d klesá od d = 2 dokud d = 6 a pak zůstane pevná.
  • α₂ = −5/48
  • α₆ = −1.
• Tvar velkého shluku ve dvou rozměrech je konformně invariantní.

Vidět Grimmett (1999) chyba harvtxt: více cílů (2 ×): CITEREFGrimmett1999 (Pomoc).^[15] V 11 nebo více dimenzích jsou tato fakta do značné míry prokázána pomocí techniky známé jako rozšíření krajky. Předpokládá se, že verze rozšíření krajky by měla být platná pro 7 nebo více rozměrů, snad s důsledky i pro prahovou hodnotu 6 rozměrů. Spojení perkolace s rozšířením krajky se nachází v Hara & Slade (1990) chyba harvtxt: více cílů (2 ×): CITEREFHaraSlade1990 (Pomoc).^[16]

Ve dvou dimenzích je první fakt („žádná perkolace v kritické fázi“) prokázán pro mnoho svazů pomocí duality. V domněnce o bylo dosaženo významného pokroku ve dvojrozměrné perkolaci Oded Schramm že limit škálování velkého klastru lze popsat pomocí a Evoluce Schramm – Loewner. Tuto domněnku prokázal Smirnov (2001) chyba harvtxt: více cílů (2 ×): CITEREFSmirnov2001 (Pomoc)^[17] ve zvláštním případě perkolace místa na trojúhelníkové mřížce.

Různé modely

• Řízená perkolace který modeluje účinek gravitační síly působící na kapalinu byl také představen v Broadbent & Hammersley (1957),^[2] a má spojení s kontaktní proces.
• Prvním studovaným modelem byla pernouce Bernoulli. V tomto modelu jsou všechny vazby nezávislé. Tento model se fyzikům nazývá perkolace vazby.
• Zobecnění bylo dále zavedeno jako Fortuin – Kasteleyn model náhodného klastru, který má mnoho spojení s Isingův model a další Pottsovy modely.
• Pernouce Bernoulliho (dluhopisů) kompletní grafy je příkladem a náhodný graf. Kritická pravděpodobnost jestr = 1/N, kde N je počet vrcholů (stránek) grafu.
• Perkolace bootstrapu odstraní aktivní buňky z klastrů, když mají příliš málo aktivních sousedů, a podívá se na konektivitu zbývajících buněk.^[18]
• První průchod perkolace.
• Invaze perkolace.
• Perkolaci se závislostními odkazy představili Parshani et al.^[19]
• Model perkolace a šíření názorů.^[20]
• Perkolaci pod lokalizovaným útokem zavedli Berezin et al.^[21] Viz také Shao et al.^[22]
• Perkolaci modulárních sítí studovali Shay et al.^[23] a Dong a kol.^[24]
• Perkolaci provozu ve městech zavedli Daqing Li a kol.^[25]
• Představujeme obnovu uzlů a odkazů v perkolaci.^[26]
• Perkolace ve 2d s charakteristickou délkou odkazu.^[27] Tato perkolace ukazuje nové jevy kritických protahovacích jevů poblíž kritické perkolace.^[28] 
• Zobecněný a decentralizovaný perkolační model, který zavádí zlomek zesílených uzlů v síti, které mohou fungovat a podporovat jejich sousedství, představil Yanqing Hu et al.^[29]

Aplikace

V biologii, biochemii a fyzické virologii

Teorie perkolace byla použita k úspěšné předpovědi fragmentace skořápek biologických virů (kapsidů),^[30] s prahovou hodnotou fragmentace Žloutenka typu B virus kapsid předpovězeno a zjištěno experimentálně.^[31] Když byl z nanoskopického pláště náhodně odstraněn kritický počet podjednotek, dojde k jeho fragmentaci a tato fragmentace může být detekována pomocí metody hromadné detekce náboje (CDMS) mezi jinými technikami s jednou částicemi. Toto je molekulární analogie běžné deskové hry Jenga a má význam pro demontáž viru.

V ekologii

Teorie perkolace byla použita ke studiu vlivu fragmentace prostředí na stanoviště zvířat^[32] a modely bakterie moru Yersinia pestis spready.^[33]

Perkolace vícevrstvých vzájemně závislých sítí

Buldyrev a kol.^[34] vyvinul rámec pro studium perkolace ve vícevrstvých sítích se závislostními odkazy mezi vrstvami. Byly nalezeny nové fyzikální jevy, včetně náhlých přechodů a kaskádových poruch.^[35] Když jsou sítě zabudovány do vesmíru, stávají se extrémně zranitelnými i pro velmi malý zlomek závislostních odkazů^[36] a pro lokalizované útoky na nulový zlomek uzlů.^[37][38] Když je zavedena obnova uzlů, je nalezen bohatý fázový diagram, který zahrnuje multikritické body, hysterezi a metastabilní režimy.^[39][40]

V provozu

V nedávných článcích byla teorie perkolace použita ke studiu dopravy ve městě. Kvalitu globálního provozu ve městě v daném čase lze charakterizovat jediným parametrem, perkolační kritickou hranicí. Kritický práh představuje rychlost, pod kterou lze cestovat ve velké části městské sítě. Nad touto hranicí se městská síť rozpadá na shluky mnoha velikostí a lze cestovat v relativně malých čtvrtích. Tato nová metoda je také schopna identifikovat opakovaná úzká místa v provozu.^[41] Kritické exponenty charakterizující distribuci velikosti shluků dobrého provozu jsou podobné těm z teorie perkolace.^[42] Rovněž se zjistilo, že během dopravní špičky může mít dopravní síť několik metastabilních stavů různých velikostí sítě a střídavě mezi těmito stavy.^[43] Zhang et al. Provedli empirickou studii týkající se prostoroprostorové distribuce velikosti dopravní zácpy.^[44] Zjistili přibližný univerzální zákon o moci pro distribuci velikostí jam v různých městech. Metodu k identifikaci funkčních klastrů časoprostorových ulic, které představují plynulý dopravní tok ve městě, vyvinuli Serok et al.^[45]

Viz také

Reference

Další čtení

externí odkazy

• PercoVIS: a Mac OS X program pro vizualizaci perkolace v sítích v reálném čase
• Interaktivní perkolace
• Kesten, Harry (květen 2006), „Co je ... perkolace?“ (PDF), Oznámení Americké matematické společnosti, 53 (5): 572–573, ISSN  1088-9477
• Austin, David (červenec 2008), Perkolace: Proklouznutí trhlinami, Americká matematická společnost
• Online kurz Nanohub Teorie perkolace
• Úvod do teorie perkolace: krátký kurz Shloma Havlina