Теорія протікання або теорія перколяції (англ. percolation theory) — математична теорія, яка описує властивості зв'язаних кластерів на випадковому графі. Теорія знайшла застосування в описі явища перколяції в статистичній фізиці та матеріалознавстві.
Вступ
Назва теорії, що відображає її мету, походить з такої задачі. Нехай в пористий матеріал заливається рідина. Чи просочиться вона через мережу пор аж до протилежного боку? Математично цю фізичну задачу моделюють тривимірною мережею на ґратці розмірністю n × n × n вузлів. Сусідні вузли сполучені між собою шляхами, які можуть з імовірністю p бути відкритими. Яка ймовірність того, що в системі існує наскрізний ланцюжок відкритих шляхів? Особливо цікава поведінка при великих n. Поставлена так задача, що отримала назву перколяції зв'язків, була сформульована Бродбентом та Гаммерслі в 1950-х, після чого почалося й продовжується її дослідження фізиками та математиками.
Дещо по іншому формулюється задача перколяції вузлів. Припускається, що вузол може бути з імовірністю p заповненим. В протилежному випадку він є порожнім. Питання не змінюється: яка імовірність існування наскрізного графу? Або по іншому: при якому p порожні вузли стануть незв'язаними?
Задачу можна розв'язувати для ґратки будь-яких розмірів. Насправді її легше розв'язати для нескінченної ґратки. У цьому випадку питання ставиться так: чи існує нескінченний відкритий кластер? За законом нуля і одиниці Колмогорова для заданого p імовірність існування нескінченного кластера може бути або нулем, або одиницею. Оскільки ймовірність монотонно зростає з ростом p, повинна існувати порогова, критична йомовірність pc, нижче якої імовірність існуння нескінченного кластера завжди нуль, а вище - одиниця. Цю критичність дуже легко спостерігати на практиці. Навіть для невеликого n = 100, ймовірність відкритого наскрізного шляху дуже різко зростає від майже нульових значень, до майже одиничних, у дуже невеличкому проміжку p.
У деяких випадках pc можна розрахувати точно. Наприклад, для двовимірної квадратної ґратки Z2 в задачі зв'язків pc = 1/2. Цей факт залишався недоведеним упродовж 20 років, доки на початку 1908-х роз'язок не знайшов . Граничний випадок ґраток із багатьма розмірностями дається ґраткою Бете, для якої поріг становить pc = 1/(z − 1), де z — координаційне число. Для більшості нескінченних графів точного значення pc знайти неможливо.
Універсальність
Принцип універсальності стверджує, що числове значення pc визначається локальною структурою графа, тоді як поведінка кластерів нижче і вище критичного значення не залежить від локальної структури, а тому в певному сенсі цю поведінку розглядати природніше, ніж саме pc. Універсальність означає також, що для заданої розмірності різні критичні індекси, фрактальна розмірність кластера при pc не залежать від типу ґратки (наприклад, від того чи розглядається задача зв'язків чи задача вузлів). Однако, недавні дослідження перколяції на зваженій планарній стохастичній ґратці показали, що попри те, що розмірність ґратки збігається з простором, на якому вона збудована, її клас універсальності відрізняється від класу універсальності всіх відомих планарних ґратках.
Фази
Підкритична та надкритична
Основною властивістю підкритичної фази є "експоненціальне згасання". Тобто, коли p < pc, імовірність того, що певний вузол належить відкритому кластеру розміру r за експоненційним законом. Це було доказано для трьох та більшого числа вимірів Меньшиковим 1986 року та незалежно Айзенманам і Барським у 1987. Для двох вимірів це твердження було частиною доказу Кестена, що pc = 1/2.
Двоїстий граф квадратної ґратки Z2 є також квадратною ґраткою. Наслідком цього є те, що в двох вимірах надкритична фаза є двоїстою до підритичної перколяції. Цей факт дає повну інформацію для надкритичної фази при d = 2. Головним результатом для надкритичної фази розмірності три і більше є те, що існує нескінчений відкритий кластер на двовимірному зрізі Z2 × [0, N]d−2, як довели Грімметт та Марстран у 1990.
У двох вимірах при p < 1/2 існує з імовірністю 1 нескінченний закритий кластер. Тому підкритичну фазу можна описати як скінченні відкритиі острови в нескінченному закритому океані. Коли p > 1/2 ситуація протилежна — закриті острови у відкритому океані. Картина складніша, коли d ≥ 3, оскільки pc < 1/2, і нескінченні закриті та відкриті кластери можуть співіснувати в проміжку p між pc та 1 − pc.
Критична
У критичній точці p = pc модель має сингулярність, що вважається степеневою. Теорія масштабування передбачає існування критичного показника, що залежить від розмірності системи d, і що визначає клас сингулярності. Коли d = 2, це припущення підтримується міркуваннями з конформної теорії поля та і дає гіпотетичні числові значення для критичних індексів. Більшість з цих припущень мають гіпотетичний характер, крім тих випадків, коли d задовольняє умови d = 2 або d ≥ 19. Серед них:
- Не існує нескінченних кластерів (ні відкритих, ні закритих)
- Імовірність існування відкритого шлаху між фіксованою точкою та іншим вузлом на відстані r спадає поліноміально, тобто пропорційна r α для деякого α
- Показник α не залежить від конкретного вибору ґратки чи від інших локальних параметрів. Він залежить тільки від розмірності d (це прояв принципу універсальності).
- αd зменшується від d = 2 до d = 6, а надалі залишається сталим.
- α2 = −5/48
- α6 = −1.
- Форма великого кластера в двовимірній системі конформаційно інваріантна.
Дивіться Grimmett, (1999)..
Для розмірності ≥ 19 ці факти доволяться в принципі за допомогою техніки, що називається мереживним розкладом. Вважається, що якась версія мереживного розкладу повинна існувати для розмірності понад 7 і вривати на порогову розмірність 6. Зв'язок між перколяцією та мережевним розкладом можна знайти в роботі Хари та Слейда.
Для розмірності 2, факт відсутності протікання в критичній фазі доведено для багатьох ґраток через двоїстість. Значний прогрес у вивченні двовимірної перколяції було зроблено завдяки припущенню Одеда Шрамма, що граничний масштаб для великого кластера можна описати, використовуючи еволюцію Шрамма-Левнера. Цю гіпотезу доказав 2001 року Смирнов для спеціального випадку вузлової перколяції на трикутній ґратці.
Моделі
- Першою вивченою моделлю була перколяція Бернуллі, в якій усі зв'язки незалежні. Фізики її називають перколяцією зв'язків.
- Узагальнення внесла модель випадкових кластерів Фортюена-Кастелена, що має численні зв'язки з моделлю Ізінга.
- Перколяція Бернуллі на повному графі є прикладом випадкового графу. Критична імовірність дорівнює p = 1/N, де N є числом вузлів на графі.
- Бутстреп-перколяція вилучає з кластерів активні вузли, що мають надто мало активних сусідів, а тоді досліджує зв'язність тих вузлів, що залишилисся.
- Направлена перколяція має відношення до вивчення процесів контакту в математиці.
- Перколяція першого проходу.
- Інвазивна перколяція.
- Перколяція зі зв'язками залежності.
- Перколяція в моделі поширення думок.
- Перколяція при локальній атаці, запропонована Березіним.
- Перколяція вуличного руху.
- Перколяція з відновленням вузлів та зв'язків.
Примітки
- Broadbent, S. R.; Hammersley, J. M. (2008). Percolation processes. Mathematical Proceedings of the Cambridge Philosophical Society. 53 (03): 629. Bibcode:1957PCPS...53..629B. doi:10.1017/S0305004100032680. ISSN 0305-0041.
- Bollobás, Béla; Riordan, Oliver (2006). Sharp thresholds and percolation in the plane. Random Structures and Algorithms. 29 (4): 524—548. doi:10.1002/rsa.20134. ISSN 1042-9832.
- Hassan, M. K.; Rahman, M. M. (2015). Percolation on a multifractal scale-free planar stochastic lattice and its universality class. Phys. Rev. E. 92: 040101. doi:10.1103/PhysRevE.92.040101.
- Hassan, M. K.; Rahman, M. M. (2016). Universality class of site and bond percolation on multi-multifractal scale-free planar stochastic lattice. Phys. Rev. E. 94: 042109. doi:10.1103/PhysRevE.94.042109.
- Menshikov, (1986)
- Aizenman та Barsky, (1987)
- Kesten, Harry (1982). Percolation Theory for Mathematicians. doi:10.1007/978-1-4899-2730-9.
- Grimmett, G. R.; Marstrand, J. M. (1990). The Supercritical Phase of Percolation is Well Behaved. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 430 (1879): 439—457. Bibcode:1990RSPSA.430..439G. doi:10.1098/rspa.1990.0100. ISSN 1364-5021.
- Grimmett, Geoffrey (1999). Percolation. 321. doi:10.1007/978-3-662-03981-6. ISSN 0072-7830.
- Hara, Takashi; Slade, Gordon (1990). Mean-field critical behaviour for percolation in high dimensions. Communications in Mathematical Physics. 128 (2): 333—391. Bibcode:1990CMaPh.128..333H. doi:10.1007/BF02108785. ISSN 0010-3616.
- Smirnov, Stanislav (2001). Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits. Comptes Rendus de l'Académie des Sciences - Series I - Mathematics. 333 (3): 239—244. Bibcode:2001CRASM.333..239S. doi:10.1016/S0764-4442(01)01991-7. ISSN 0764-4442.
- (1991), Bootstrap percolation, Physica A: Statistical Mechanics and its Applications, 171 (3): 453—470, doi:10.1016/0378-4371(91)90295-n.
- Parshani, R.; Buldyrev, S. V.; Havlin, S. (2010). Critical effect of dependency groups on the function of networks. Proceedings of the National Academy of Sciences. 108 (3): 1007—1010. arXiv:1010.4498. Bibcode:2011PNAS..108.1007P. doi:10.1073/pnas.1008404108. ISSN 0027-8424. PMC 3024657. PMID 21191103.
- Shao, Jia; Havlin, Shlomo; Stanley, H. Eugene (2009). Dynamic Opinion Model and Invasion Percolation. Physical Review Letters. 103 (1). Bibcode:2009PhRvL.103a8701S. doi:10.1103/PhysRevLett.103.018701. ISSN 0031-9007.
- Berezin, Yehiel; Bashan, Amir; Danziger, Michael M.; Li, Daqing; Havlin, Shlomo (2015). Localized attacks on spatially embedded networks with dependencies. Scientific Reports. 5 (1). doi:10.1038/srep08934. ISSN 2045-2322.
- Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (2015). Percolation transition in dynamical traffic network with evolving critical bottlenecks. Proceedings of the National Academy of Sciences. 112 (3): 669—672. doi:10.1073/pnas.1419185112. ISSN 0027-8424. PMC 4311803. PMID 25552558.
- Majdandzic, Antonio; Podobnik, Boris; Buldyrev, Sergey V.; Kenett, Dror Y.; Havlin, Shlomo; Eugene Stanley, H. (2013). Spontaneous recovery in dynamical networks. Nature Physics. 10 (1): 34—38. doi:10.1038/nphys2819. ISSN 1745-2473.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teoriya protikannya abo teoriya perkolyaciyi angl percolation theory matematichna teoriya yaka opisuye vlastivosti zv yazanih klasteriv na vipadkovomu grafi Teoriya znajshla zastosuvannya v opisi yavisha perkolyaciyi v statistichnij fizici ta materialoznavstvi Trivimirnij graf vuzliv VstupNazva teoriyi sho vidobrazhaye yiyi metu pohodit z takoyi zadachi Nehaj v poristij material zalivayetsya ridina Chi prosochitsya vona cherez merezhu por azh do protilezhnogo boku Matematichno cyu fizichnu zadachu modelyuyut trivimirnoyu merezheyu na gratci rozmirnistyu n n n vuzliv Susidni vuzli spolucheni mizh soboyu shlyahami yaki mozhut z imovirnistyu p buti vidkritimi Yaka jmovirnist togo sho v sistemi isnuye naskriznij lancyuzhok vidkritih shlyahiv Osoblivo cikava povedinka pri velikih n Postavlena tak zadacha sho otrimala nazvu perkolyaciyi zv yazkiv bula sformulovana Brodbentom ta Gammersli v 1950 h pislya chogo pochalosya j prodovzhuyetsya yiyi doslidzhennya fizikami ta matematikami Desho po inshomu formulyuyetsya zadacha perkolyaciyi vuzliv Pripuskayetsya sho vuzol mozhe buti z imovirnistyu p zapovnenim V protilezhnomu vipadku vin ye porozhnim Pitannya ne zminyuyetsya yaka imovirnist isnuvannya naskriznogo grafu Abo po inshomu pri yakomu p porozhni vuzli stanut nezv yazanimi Zadachu mozhna rozv yazuvati dlya gratki bud yakih rozmiriv Naspravdi yiyi legshe rozv yazati dlya neskinchennoyi gratki U comu vipadku pitannya stavitsya tak chi isnuye neskinchennij vidkritij klaster Za zakonom nulya i odinici Kolmogorova dlya zadanogo p imovirnist isnuvannya neskinchennogo klastera mozhe buti abo nulem abo odiniceyu Oskilki jmovirnist monotonno zrostaye z rostom p povinna isnuvati porogova kritichna jomovirnist pc nizhche yakoyi imovirnist isnunnya neskinchennogo klastera zavzhdi nul a vishe odinicya Cyu kritichnist duzhe legko sposterigati na praktici Navit dlya nevelikogo n 100 jmovirnist vidkritogo naskriznogo shlyahu duzhe rizko zrostaye vid majzhe nulovih znachen do majzhe odinichnih u duzhe nevelichkomu promizhku p Perkolyaciya zv yazkiv na dvovimirnij kvadratnij gratci pri jmovirnosti p 0 51 U deyakih vipadkah pc mozhna rozrahuvati tochno Napriklad dlya dvovimirnoyi kvadratnoyi gratki Z2 v zadachi zv yazkiv pc 1 2 Cej fakt zalishavsya nedovedenim uprodovzh 20 rokiv doki na pochatku 1908 h roz yazok ne znajshov Granichnij vipadok gratok iz bagatma rozmirnostyami dayetsya gratkoyu Bete dlya yakoyi porig stanovit pc 1 z 1 de z koordinacijne chislo Dlya bilshosti neskinchennih grafiv tochnogo znachennya pc znajti nemozhlivo UniversalnistPrincip universalnosti stverdzhuye sho chislove znachennya pc viznachayetsya lokalnoyu strukturoyu grafa todi yak povedinka klasteriv nizhche i vishe kritichnogo znachennya ne zalezhit vid lokalnoyi strukturi a tomu v pevnomu sensi cyu povedinku rozglyadati prirodnishe nizh same pc Universalnist oznachaye takozh sho dlya zadanoyi rozmirnosti rizni kritichni indeksi fraktalna rozmirnist klastera pri pc ne zalezhat vid tipu gratki napriklad vid togo chi rozglyadayetsya zadacha zv yazkiv chi zadacha vuzliv Odnako nedavni doslidzhennya perkolyaciyi na zvazhenij planarnij stohastichnij gratci pokazali sho popri te sho rozmirnist gratki zbigayetsya z prostorom na yakomu vona zbudovana yiyi klas universalnosti vidriznyayetsya vid klasu universalnosti vsih vidomih planarnih gratkah FaziPidkritichna ta nadkritichna Osnovnoyu vlastivistyu pidkritichnoyi fazi ye eksponencialne zgasannya Tobto koli p lt pc imovirnist togo sho pevnij vuzol nalezhit vidkritomu klasteru rozmiru r za eksponencijnim zakonom Ce bulo dokazano dlya troh ta bilshogo chisla vimiriv Menshikovim 1986 roku ta nezalezhno Ajzenmanam i Barskim u 1987 Dlya dvoh vimiriv ce tverdzhennya bulo chastinoyu dokazu Kestena sho pc 1 2 Dvoyistij graf kvadratnoyi gratki Z2 ye takozh kvadratnoyu gratkoyu Naslidkom cogo ye te sho v dvoh vimirah nadkritichna faza ye dvoyistoyu do pidritichnoyi perkolyaciyi Cej fakt daye povnu informaciyu dlya nadkritichnoyi fazi pri d 2 Golovnim rezultatom dlya nadkritichnoyi fazi rozmirnosti tri i bilshe ye te sho isnuye neskinchenij vidkritij klaster na dvovimirnomu zrizi Z2 0 N d 2 yak doveli Grimmett ta Marstran u 1990 U dvoh vimirah pri p lt 1 2 isnuye z imovirnistyu 1 neskinchennij zakritij klaster Tomu pidkritichnu fazu mozhna opisati yak skinchenni vidkritii ostrovi v neskinchennomu zakritomu okeani Koli p gt 1 2 situaciya protilezhna zakriti ostrovi u vidkritomu okeani Kartina skladnisha koli d 3 oskilki pc lt 1 2 i neskinchenni zakriti ta vidkriti klasteri mozhut spivisnuvati v promizhku p mizh pc ta 1 pc Kritichna U kritichnij tochci p pc model maye singulyarnist sho vvazhayetsya stepenevoyu Teoriya masshtabuvannya peredbachaye isnuvannya kritichnogo pokaznika sho zalezhit vid rozmirnosti sistemi d i sho viznachaye klas singulyarnosti Koli d 2 ce pripushennya pidtrimuyetsya mirkuvannyami z konformnoyi teoriyi polya ta i daye gipotetichni chislovi znachennya dlya kritichnih indeksiv Bilshist z cih pripushen mayut gipotetichnij harakter krim tih vipadkiv koli d zadovolnyaye umovi d 2 abo d 19 Sered nih Ne isnuye neskinchennih klasteriv ni vidkritih ni zakritih Imovirnist isnuvannya vidkritogo shlahu mizh fiksovanoyu tochkoyu ta inshim vuzlom na vidstani r spadaye polinomialno tobto proporcijna r a dlya deyakogo a Pokaznik a ne zalezhit vid konkretnogo viboru gratki chi vid inshih lokalnih parametriv Vin zalezhit tilki vid rozmirnosti d ce proyav principu universalnosti ad zmenshuyetsya vid d 2 do d 6 a nadali zalishayetsya stalim a2 5 48 a6 1 Forma velikogo klastera v dvovimirnij sistemi konformacijno invariantna Divitsya Grimmett 1999 Dlya rozmirnosti 19 ci fakti dovolyatsya v principi za dopomogoyu tehniki sho nazivayetsya merezhivnim rozkladom Vvazhayetsya sho yakas versiya merezhivnogo rozkladu povinna isnuvati dlya rozmirnosti ponad 7 i vrivati na porogovu rozmirnist 6 Zv yazok mizh perkolyaciyeyu ta merezhevnim rozkladom mozhna znajti v roboti Hari ta Slejda Dlya rozmirnosti 2 fakt vidsutnosti protikannya v kritichnij fazi dovedeno dlya bagatoh gratok cherez dvoyistist Znachnij progres u vivchenni dvovimirnoyi perkolyaciyi bulo zrobleno zavdyaki pripushennyu Odeda Shramma sho granichnij masshtab dlya velikogo klastera mozhna opisati vikoristovuyuchi evolyuciyu Shramma Levnera Cyu gipotezu dokazav 2001 roku Smirnov dlya specialnogo vipadku vuzlovoyi perkolyaciyi na trikutnij gratci ModeliPershoyu vivchenoyu modellyu bula perkolyaciya Bernulli v yakij usi zv yazki nezalezhni Fiziki yiyi nazivayut perkolyaciyeyu zv yazkiv Uzagalnennya vnesla model vipadkovih klasteriv Fortyuena Kastelena sho maye chislenni zv yazki z modellyu Izinga Perkolyaciya Bernulli na povnomu grafi ye prikladom vipadkovogo grafu Kritichna imovirnist dorivnyuye p 1 N de N ye chislom vuzliv na grafi Butstrep perkolyaciya viluchaye z klasteriv aktivni vuzli sho mayut nadto malo aktivnih susidiv a todi doslidzhuye zv yaznist tih vuzliv sho zalishilissya Napravlena perkolyaciya maye vidnoshennya do vivchennya procesiv kontaktu v matematici Perkolyaciya pershogo prohodu Invazivna perkolyaciya Perkolyaciya zi zv yazkami zalezhnosti Perkolyaciya v modeli poshirennya dumok Perkolyaciya pri lokalnij ataci zaproponovana Berezinim Perkolyaciya vulichnogo ruhu Perkolyaciya z vidnovlennyam vuzliv ta zv yazkiv PrimitkiBroadbent S R Hammersley J M 2008 Percolation processes Mathematical Proceedings of the Cambridge Philosophical Society 53 03 629 Bibcode 1957PCPS 53 629B doi 10 1017 S0305004100032680 ISSN 0305 0041 Bollobas Bela Riordan Oliver 2006 Sharp thresholds and percolation in the plane Random Structures and Algorithms 29 4 524 548 doi 10 1002 rsa 20134 ISSN 1042 9832 Hassan M K Rahman M M 2015 Percolation on a multifractal scale free planar stochastic lattice and its universality class Phys Rev E 92 040101 doi 10 1103 PhysRevE 92 040101 Hassan M K Rahman M M 2016 Universality class of site and bond percolation on multi multifractal scale free planar stochastic lattice Phys Rev E 94 042109 doi 10 1103 PhysRevE 94 042109 Menshikov 1986 Aizenman ta Barsky 1987 Kesten Harry 1982 Percolation Theory for Mathematicians doi 10 1007 978 1 4899 2730 9 Grimmett G R Marstrand J M 1990 The Supercritical Phase of Percolation is Well Behaved Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences 430 1879 439 457 Bibcode 1990RSPSA 430 439G doi 10 1098 rspa 1990 0100 ISSN 1364 5021 Grimmett Geoffrey 1999 Percolation 321 doi 10 1007 978 3 662 03981 6 ISSN 0072 7830 Hara Takashi Slade Gordon 1990 Mean field critical behaviour for percolation in high dimensions Communications in Mathematical Physics 128 2 333 391 Bibcode 1990CMaPh 128 333H doi 10 1007 BF02108785 ISSN 0010 3616 Smirnov Stanislav 2001 Critical percolation in the plane conformal invariance Cardy s formula scaling limits Comptes Rendus de l Academie des Sciences Series I Mathematics 333 3 239 244 Bibcode 2001CRASM 333 239S doi 10 1016 S0764 4442 01 01991 7 ISSN 0764 4442 1991 Bootstrap percolation Physica A Statistical Mechanics and its Applications 171 3 453 470 doi 10 1016 0378 4371 91 90295 n Parshani R Buldyrev S V Havlin S 2010 Critical effect of dependency groups on the function of networks Proceedings of the National Academy of Sciences 108 3 1007 1010 arXiv 1010 4498 Bibcode 2011PNAS 108 1007P doi 10 1073 pnas 1008404108 ISSN 0027 8424 PMC 3024657 PMID 21191103 Shao Jia Havlin Shlomo Stanley H Eugene 2009 Dynamic Opinion Model and Invasion Percolation Physical Review Letters 103 1 Bibcode 2009PhRvL 103a8701S doi 10 1103 PhysRevLett 103 018701 ISSN 0031 9007 Berezin Yehiel Bashan Amir Danziger Michael M Li Daqing Havlin Shlomo 2015 Localized attacks on spatially embedded networks with dependencies Scientific Reports 5 1 doi 10 1038 srep08934 ISSN 2045 2322 Li Daqing Fu Bowen Wang Yunpeng Lu Guangquan Berezin Yehiel Stanley H Eugene Havlin Shlomo 2015 Percolation transition in dynamical traffic network with evolving critical bottlenecks Proceedings of the National Academy of Sciences 112 3 669 672 doi 10 1073 pnas 1419185112 ISSN 0027 8424 PMC 4311803 PMID 25552558 Majdandzic Antonio Podobnik Boris Buldyrev Sergey V Kenett Dror Y Havlin Shlomo Eugene Stanley H 2013 Spontaneous recovery in dynamical networks Nature Physics 10 1 34 38 doi 10 1038 nphys2819 ISSN 1745 2473