Теория перколяции

Математическая теория поведения связанных кластеров в случайном графе

В статистической физике и математике теория перколяции описывает поведение сети при добавлении узлов или связей. Это геометрический тип фазового перехода , поскольку при критической доле добавления сеть небольших разрозненных кластеров сливается в значительно более крупные связанные , так называемые охватывающие кластеры. Приложения теории перколяции к материаловедению и многим другим дисциплинам обсуждаются здесь и в статьях Теория сетей и Перколяция (когнитивная психология) .

Введение

Трехмерный граф перколяции сайта

Перколяция связей в квадратной решетке от p=0,3 до p=0,52

Представительный вопрос (и источник названия) выглядит следующим образом. Предположим, что некоторая жидкость налита поверх некоторого пористого материала. Сможет ли жидкость пройти из отверстия в отверстие и достичь дна? Этот физический вопрос математически моделируется как трехмерная сеть из n × n × n вершин , обычно называемых «сайтами», в которой ребро или «связи» между каждыми двумя соседями могут быть открытыми (пропускающими жидкость) с вероятностью p или закрытыми с вероятностью 1 – p , и они считаются независимыми. Следовательно, для заданного p , какова вероятность того, что открытый путь (имеется в виду путь, каждое из звеньев которого является «открытой» связью) существует сверху вниз? Поведение для больших  n представляет основной интерес. Эта проблема, называемая теперь просачиванием связей , была введена в математическую литературу Бродбентом и Хаммерсли (1957), ^[1] и с тех пор интенсивно изучается математиками и физиками.

В несколько иной математической модели для получения случайного графа сайт «занят» с вероятностью p или «пуст» (в этом случае его ребра удаляются) с вероятностью 1 – p ; соответствующая проблема называется просачиванием сайта . Вопрос тот же: для заданного p , какова вероятность того, что путь существует между вершиной и низом? Аналогично можно спросить, учитывая связный граф, при какой доле 1 – p отказов граф станет несвязным (без большого компонента).

Определение просачивания в трехмерной трубчатой ​​сети

Те же вопросы можно задать для любого размера решетки. Как это обычно бывает, на самом деле проще исследовать бесконечные сети, чем просто большие. В этом случае соответствующий вопрос: существует ли бесконечный открытый кластер? То есть, существует ли путь из связанных точек бесконечной длины «через» сеть? По закону Колмогорова «ноль-единица» для любого заданного p вероятность того, что существует бесконечный кластер, равна либо нулю, либо единице. Поскольку эта вероятность является возрастающей функцией p (доказательство с помощью аргумента о связи ), должно быть критическое p (обозначаемое как  p _c ), ниже которого вероятность всегда равна 0, а выше которого вероятность всегда равна 1. На практике эту критичность очень легко наблюдать. Даже для n, столь малого, как 100, вероятность открытого пути сверху вниз резко возрастает от очень близкого к нулю до очень близкого к единице за короткий промежуток значений  p .

Деталь перколяции связи на квадратной решетке в двух измерениях с вероятностью перколяции p = 0,51

История

Теория Флори–Стокмайера была первой теорией, исследующей процессы перколяции. ^[2]

История модели перколяции, какой мы ее знаем, берет свое начало в угольной промышленности. Со времен промышленной революции экономическая важность этого источника энергии способствовала проведению многих научных исследований с целью понять его состав и оптимизировать его использование. В 1930-х и 1940-х годах качественный анализ органической химии оставлял все больше места для более количественных исследований. ^[3]

В этом контексте в 1938 году была создана Британская ассоциация по исследованию использования угля (BCURA). Это исследовательская ассоциация, финансируемая владельцами угольных шахт. В 1942 году Розалинд Франклин , которая тогда недавно окончила химический факультет Кембриджского университета, присоединилась к BCURA. Она начала исследования плотности и пористости угля. Во время Второй мировой войны уголь был важным стратегическим ресурсом. Он использовался в качестве источника энергии, но также был основным компонентом противогазов.

Уголь является пористой средой. Чтобы измерить его «реальную» плотность, нужно было погрузить его в жидкость или газ, молекулы которого достаточно малы, чтобы заполнить его микроскопические поры. Пытаясь измерить плотность угля с использованием нескольких газов (гелий, метанол, гексан, бензол), и обнаружив различные значения в зависимости от используемого газа, Розалинд Франклин показала, что поры угля состоят из микроструктур различной длины, которые действуют как микроскопическое сито для разделения газов. Она также обнаружила, что размер этих структур зависит от температуры карбонизации во время добычи угля. Благодаря этому исследованию она получила степень доктора философии и покинула BCURA в 1946 году. ^[4]

В середине пятидесятых Саймон Бродбент работал в BCURA статистиком. Среди прочих интересов он изучал использование угля в противогазах. Один из вопросов заключается в том, чтобы понять, как жидкость может диффундировать в угольных порах, смоделированных как случайный лабиринт открытых или закрытых туннелей. В 1954 году во время симпозиума по методам Монте-Карло он задает вопросы Джону Хаммерсли об использовании численных методов для анализа этой модели. ^[5]

Бродбент и Хаммерсли в своей статье 1957 года представили математическую модель для моделирования этого явления — перколяции.

Расчет критического параметра

Для большинства бесконечных решетчатых графов p _c не может быть вычислен точно, хотя в некоторых случаях p _c имеет точное значение. Например:

• для квадратной решетки ℤ ² в двух измерениях, p _c = ⁠1/2⁠ для перколяции связей, факт, который был открытым вопросом в течение более 20 лет и был окончательно решен Гарри Кестеном в начале 1980-х годов, ^[6] см. Kesten (1982). Для перколяции узлов на квадратной решетке значение p _c неизвестно из аналитического вывода, а только через моделирование больших решеток, которое дает оценку p _c = 0,59274621 ± 0,00000013. ^[7]  
• Предельный случай для решеток в больших размерностях задается решеткой Бете , порог которой находится при p _c = ⁠1/z − 1⁠ для координационного числа  z . Другими словами: для регулярного дерева степени,равно. ${\displaystyle z}$ ${\displaystyle p_{c}}$ ${\displaystyle 1/(z-1)}$

Фронт просачивания

• Для случайной древовидной сети без корреляции степень-степень можно показать, что такая сеть может иметь гигантский компонент , а порог перколяции (вероятность передачи) определяется как , где — производящая функция, соответствующая избыточному распределению степеней . Таким образом, для случайных сетей Эрдёша–Реньи средней степени , p _c = ⁠ ${\displaystyle p_{c}={\frac {1}{g_{1}'(1)}}}$ ${\displaystyle g_{1}(z)}$ ${\displaystyle \langle k\rangle }$1/⟨к⟩⁠ . ^{[8] [9] [10]}
• В сетях с низкой кластеризацией критическая точка масштабируется таким образом: ${\displaystyle 0<C\ll 1}$ ${\displaystyle (1-C)^{-1}}$

${\displaystyle p_{c}={\frac {1}{1-C}}{\frac {1}{g_{1}'(1)}}.}$^[11]

Это указывает на то, что для заданного распределения степени кластеризация приводит к большему порогу перколяции, в основном потому, что для фиксированного числа связей структура кластеризации усиливает ядро ​​сети ценой разбавления глобальных связей. Для сетей с высокой кластеризацией сильная кластеризация может вызвать структуру ядро-периферия, в которой ядро ​​и периферия могут просачиваться в разных критических точках, и приведенная выше приблизительная обработка неприменима. ^[12]

Универсальность

Принцип универсальности гласит, что численное значение p _c определяется локальной структурой графа, тогда как поведение вблизи критического порога, p _c , характеризуется универсальными критическими показателями . Например, распределение размера кластеров при критичности затухает как степенной закон с тем же показателем для всех 2d решеток. Эта универсальность означает, что для заданного измерения, различных критических показателей, фрактальная размерность кластеров при p _c не зависит от типа решетки и типа перколяции (например, связь или узел). Однако недавно перколяция была выполнена на взвешенной плоской стохастической решетке (WPSL) и обнаружено, что хотя размерность WPSL совпадает с размерностью пространства, в которое она встроена, ее класс универсальности отличается от класса всех известных плоских решеток. ^{[13] [14]}

Фазы

Докритические и сверхкритические

Основным фактом в докритической фазе является «экспоненциальный распад». То есть, когда p < p _c , вероятность того, что конкретная точка (например, начало координат) содержится в открытом кластере (имеется в виду максимальное связное множество «открытых» ребер графа) размера r , экспоненциально убывает до нуля по  r . Это было доказано для перколяции в трех и более измерениях Меньшиковым (1986) и независимо Айзенманом и Барским (1987). В двух измерениях это стало частью доказательства Кестена, что p _c = ⁠1/2⁠ . ^[15]

Дуальный граф квадратной решетки ℤ ² также является квадратной решеткой. Из этого следует, что в двух измерениях сверхкритическая фаза дуальна субкритическому процессу перколяции. Это дает по существу полную информацию о сверхкритической модели с d = 2. Главный результат для сверхкритической фазы в трех и более измерениях состоит в том, что для достаточно большого  N почти наверняка существует бесконечный открытый кластер в двумерной пластине ℤ ² × [0, N ] ^{d − 2} . Это было доказано Гримметтом и Марстрандом (1990). ^[16]

В двух измерениях с p < ⁠1/2⁠ , с вероятностью существует один единственный бесконечный замкнутый кластер (замкнутый кластер — это максимальное связное множество «замкнутых» ребер графа). Таким образом, субкритическую фазу можно описать как конечные открытые острова в бесконечном замкнутом океане. Когда p > ⁠1/2⁠ происходит как раз обратное, с конечными закрытыми островами в бесконечном открытом океане. Картина становится сложнее, когда d ≥ 3 , поскольку p _c < ⁠1/2⁠ , и существует сосуществование бесконечных открытых и закрытых кластеров для p между p _c и  1 − p _c .

Критичность

Увеличьте масштаб критического перколяционного кластера (нажмите для анимации)

Перколяция имеет сингулярность в критической точке p = p _c и многие свойства ведут себя как степенной закон с , вблизи . Теория масштабирования предсказывает существование критических показателей , зависящих от числа d измерений, которые определяют класс сингулярности. Когда d = 2 , эти предсказания подкреплены аргументами из конформной теории поля и эволюции Шрамма-Лёвнера и включают предсказанные числовые значения для показателей. Большинство этих предсказаний являются предположительными, за исключением случаев, когда число d измерений удовлетворяет либо d = 2 , либо d ≥ 6. Они включают: ${\displaystyle p-p_{c}}$ ${\displaystyle p_{c}}$

• Не существует бесконечных кластеров (открытых или закрытых)
• Вероятность того, что существует открытый путь из некоторой фиксированной точки (например, начала координат) на расстояние r , убывает полиномиально , т.е. имеет порядок r ^α для некоторого  α.
  • α не зависит от конкретной выбранной решетки или других локальных параметров. Он зависит только от размерности d (это пример принципа универсальности ).
  • α _d уменьшается от d = 2 до d = 6 , а затем остается фиксированным.
  • α ₂ = − ⁠5/48⁠
  • α ₆ = −1 .
• Форма большого кластера в двух измерениях конформно инвариантна .

См. Grimmett (1999). ^[17] В 11 или более измерениях эти факты в значительной степени доказаны с помощью техники, известной как кружевное расширение. Считается, что версия кружевного расширения должна быть действительна для 7 или более измерений, возможно, с последствиями также для порогового случая 6 измерений. Связь перколяции с кружевным расширением найдена в Hara & Slade (1990). ^[18]

В двух измерениях первый факт («отсутствие перколяции в критической фазе») доказан для многих решеток с использованием дуальности. Существенный прогресс был достигнут в двумерной перколяции благодаря гипотезе Одеда Шрамма о том, что предел масштабирования большого кластера может быть описан в терминах эволюции Шрамма–Лёвнера . Эта гипотеза была доказана Смирновым (2001) ^[19] в частном случае перколяции узлов на треугольной решетке.

Разные модели

• Направленная перколяция , моделирующая эффект гравитационных сил, действующих на жидкость, была также введена в работе Бродбента и Хаммерсли (1957) ^[1] и связана с контактным процессом .
• Первой изученной моделью была перколяция Бернулли. В этой модели все связи независимы. Физики называют эту модель перколяцией связей.
• Затем было введено обобщение в виде модели случайных кластеров Фортуина–Кастелейна , которая имеет много связей с моделью Изинга и другими моделями Поттса .
• Перколяция Бернулли (бонда) на полных графах является примером случайного графа . Критическая вероятность равна  p = ⁠1/Н⁠ , где N — количество вершин (узлов) графа.
• Перколяция Bootstrap удаляет активные ячейки из кластеров, когда у них слишком мало активных соседей, и проверяет связность оставшихся ячеек. ^[20]
• Перколяция первого прохода .
• Просачивание вторжения .

Приложения

В биологии, биохимии и физической вирусологии

Теория перколяции была использована для успешного предсказания фрагментации биологических вирусных оболочек (капсидов) ^{[21] [22]} с порогом фрагментации капсида вируса гепатита В, предсказанным и обнаруженным экспериментально. ^[23] Когда критическое количество субъединиц было случайным образом удалено из наноскопической оболочки, она фрагментируется, и эта фрагментация может быть обнаружена с помощью масс-спектроскопии с обнаружением заряда (CDMS) среди других методов одиночных частиц. Это молекулярный аналог распространенной настольной игры Дженга , и он имеет отношение к более широкому изучению разборки вирусов. Интересно, что более стабильные вирусные частицы (плитки с большими порогами фрагментации) встречаются в большем количестве в природе. ^[21]

В экологии

Теория перколяции применялась к исследованиям того, как фрагментация окружающей среды влияет на среду обитания животных ^[24] , а также к моделям распространения чумной бактерии Yersinia pestis . ^[25]

Смотрите также

• Теория непрерывной перколяции
• Критический показатель  – параметр, описывающий физику вблизи критических точек.
• Направленная перколяция  – Физические модели фильтрации под действием таких сил, как гравитация.
• Модель Эрдеша – Реньи  - две тесно связанные модели для создания случайных графов.
• Фрактал  – бесконечно подробная математическая структура
• Гигантский компонент  – большой связный компонент случайного графа.
• Теория графов  – Раздел дискретной математики
• Взаимозависимые сети  – Подотрасль сетевой науки
• Просачивание вторжения
• Гипотеза Кана–Калаи  – Математическое утверждение
• Теория сетей  – изучение графов как представления отношений между дискретными объектами.
• Сетевая наука  – академическая область
• Порог перколяции  – Порог моделей теории перколяции
• Критические показатели перколяции  – математический параметр в теории перколяции
• Безмасштабная сеть  – сеть, распределение степеней которой подчиняется степенному закону.
• Задача о кратчайшем пути  – Вычислительная задача теории графов
• Гипотеза о двухъярусной кровати  – Гипотеза в вероятностной комбинаторике

Ссылки

1. Broadbent, Simon; Hammersley, John (1957). «Процессы просачивания I. Кристаллы и лабиринты». Математические труды Кембриджского философского общества . 53 (3): 629–641. Bibcode :1957PCPS...53..629B. doi :10.1017/S0305004100032680. ISSN  0305-0041. S2CID  84176793.
2. Сахини, М.; Сахими, М. (2003-07-13). Приложения теории перколяции. CRC Press. ISBN 978-0-203-22153-2. Архивировано из оригинала 2023-02-04 . Получено 2020-10-27 .
3. Ван Кревелен, Дирк В. (1982). «Развитие исследований угля — обзор». Fuel . 61 (9): 786–790. doi :10.1016/0016-2361(82)90304-0.
4. Документы Розалинд Франклин — дыры в угле: исследования в BCURA и в Париже, 1942-1951. https://profiles.nlm.nih.gov/spotlight/kr/feature/coal Архивировано 07.07.2022 на Wayback Machine . Дата обращения: 17.01.2022.
5. Хаммерсли, Дж. М.; Уэлш, Д. Дж. А. (1980). «Теория перколяции и ее разветвления». Contemporary Physics . 21 (6): 593–605. Bibcode : 1980ConPh..21..593H. doi : 10.1080/00107518008210661.
6. Боллобас, Бела; Риордан, Оливер (2006). «Острые пороги и просачивание на плоскости». Случайные структуры и алгоритмы . 29 (4): 524–548. arXiv : math/0412510 . doi :10.1002/rsa.20134. ISSN  1042-9832. S2CID  7342807.
7. MEJ Newman; RM Ziff (2000). «Эффективный алгоритм Монте-Карло и высокоточные результаты для перколяции». Physical Review Letters . 85 (19): 4104–4107. arXiv : cond-mat/0005264 . Bibcode : 2000PhRvL..85.4104N. doi : 10.1103/physrevlett.85.4104. PMID  11056635. S2CID  747665.
8. Эрдеш, П. и Реньи, А. (1959). «О случайных графах И.». Опубл. Математика. (6): 290–297.
9. Эрдеш, П. и Реньи, А. (1960). «Эволюция случайных графов». Опубл. Математика. Инст. Хунг. акад. наук. (5): 17–61.
10. Боллоба, Б. (1985). «Случайные графы». Академический .
11. Берченко, Якир; Арци-Рандруп, Яэль; Тейхер, Мина; Стоун, Льюи (2009-03-30). "Возникновение и размер гигантской компоненты в кластеризованных случайных графах с заданным распределением степеней". Physical Review Letters . 102 (13): 138701. Bibcode : 2009PhRvL.102m8701B. doi : 10.1103/PhysRevLett.102.138701. ISSN  0031-9007. PMID  19392410. Архивировано из оригинала 2023-02-04 . Получено 2022-02-24 .
12. Ли, Мин; Лю, Рунь-Ран; Люй, Линьюань; Ху, Мао-Бинь; Сюй, Шуци; Чжан, И-Чэн (2021-04-25). «Перколяция в сложных сетях: теория и применение». Physics Reports . Перколяция в сложных сетях: теория и применение. 907 : 1–68. arXiv : 2101.11761 . Bibcode :2021PhR...907....1L. doi :10.1016/j.physrep.2020.12.003. ISSN  0370-1573. S2CID  231719831.
13. Хассан, МК; Рахман, ММ (2015). «Перколяция на мультифрактальной безмасштабной плоской стохастической решетке и ее класс универсальности». Phys. Rev. E. 92 ( 4): 040101. arXiv : 1504.06389 . Bibcode : 2015PhRvE..92d0101H. doi : 10.1103/PhysRevE.92.040101. PMID  26565145. S2CID  119112286.
14. Хассан, МК; Рахман, ММ (2016). «Универсальный класс перколяции узлов и связей на мультимультифрактальной безмасштабной плоской стохастической решетке». Phys. Rev. E. 94 ( 4): 042109. arXiv : 1604.08699 . Bibcode : 2016PhRvE..94d2109H. doi : 10.1103/PhysRevE.94.042109. PMID  27841467. S2CID  22593028.
15. Кестен, Гарри (1982). Теория перколяции для математиков . Биркхаузер. doi :10.1007/978-1-4899-2730-9. ISBN 978-0-8176-3107-9.
16. Гримметт, Джеффри ; Марстранд, Джон (1990). «Сверхкритическая фаза перколяции ведет себя хорошо». Труды Королевского общества A: Математические, физические и инженерные науки . 430 (1879): 439–457. Bibcode : 1990RSPSA.430..439G. doi : 10.1098/rspa.1990.0100. ISSN  1364-5021. S2CID  122534964.
17. Гриммет, Джеффри (1999). Перколяция. Grundlehren der mathematischen Wissenschaften. Том. 321. Берлин: Шпрингер. дои : 10.1007/978-3-662-03981-6. ISBN 978-3-642-08442-3. ISSN  0072-7830. Архивировано из оригинала 2020-02-23 . Получено 2009-04-18 .
18. Хара, Такаши; Слэйд, Гордон (1990). «Критическое поведение среднего поля для перколяции в высоких размерностях». Communications in Mathematical Physics . 128 (2): 333–391. Bibcode : 1990CMaPh.128..333H. doi : 10.1007/BF02108785. ISSN  0010-3616. S2CID  119875060. Архивировано из оригинала 24.02.2021 . Получено 30.10.2022 .
19. Смирнов, Станислав (2001). «Критическая перколяция на плоскости: конформная инвариантность, формула Карди, масштабные пределы». Comptes Rendus de l'Académie des Sciences . I. 333 (3): 239–244. arXiv : 0909.4499 . Bibcode : 2001CRASM.333..239S. CiteSeerX 10.1.1.246.2739 . doi : 10.1016/S0764-4442(01)01991-7. ISSN  0764-4442. 
20. Адлер, Джоан (1991), «Бутстреп-перколяция», Physica A: Статистическая механика и ее приложения , 171 (3): 453–470, Bibcode : 1991PhyA..171..453A, doi : 10.1016/0378-4371(91)90295-n.
21. Brunk, Nicholas E.; Twarock, Reidun (2021). «Теория перколяции раскрывает биофизические свойства вирусоподобных частиц». ACS Nano . 15 (8). Американское химическое общество (ACS): 12988–12995. doi : 10.1021/acsnano.1c01882 . ISSN  1936-0851. PMC 8397427. PMID 34296852  . 
22. Brunk, NE; Lee, LS; Glazier, JA; Butske, W.; Zlotnick, A. (2018). «Молекулярная дженга: фазовый переход перколяции (коллапс) в вирусных капсидах». Physical Biology . 15 (5): 056005. Bibcode :2018PhBio..15e6005B. doi :10.1088/1478-3975/aac194. PMC 6004236 . PMID  29714713. 
23. Ли, Л. С.; Бранк, Н.; Хейвуд, Д. Г.; Кейфер, Д.; Пирсон, Э.; Кондилис, П.; Злотник, А. (2017). «Молекулярный макет: удаление и замена субъединиц в капсиде вируса гепатита В». Protein Science . 26 (11): 2170–2180. doi :10.1002/pro.3265. PMC 5654856 . PMID  28795465. 
24. Босвелл, ГП; Бриттон, НФ; Фрэнкс, НР (1998-10-22). «Фрагментация среды обитания, теория перколяции и сохранение ключевых видов». Труды Лондонского королевского общества B: Биологические науки . 265 (1409): 1921–1925. doi :10.1098/rspb.1998.0521. ISSN  0962-8452. PMC 1689475 . 
25. Дэвис, С.; Трапман, П.; Лейрс, Х.; Бегон, М.; Хестербек, Дж. а. П. (2008-07-31). «Порог обилия чумы как критическое явление просачивания». Nature . 454 (7204): 634–637. Bibcode :2008Natur.454..634D. doi :10.1038/nature07053. hdl : 1874/29683 . ISSN  1476-4687. PMID  18668107. S2CID  4425203.

• Айзенман, Майкл ; Барски, Дэвид (1987), «Резкость фазового перехода в моделях перколяции», Communications in Mathematical Physics , 108 (3): 489–526, Bibcode : 1987CMaPh.108..489A, doi : 10.1007/BF01212322, S2CID  35592821
• Меньшиков, Михаил (1986), «Совпадение критических точек в задачах перколяции», Советская математика - Доклады АН , 33 : 856–859

Дальнейшее чтение

• Остин, Дэвид (июль 2008 г.). «Перколяция: проскальзывание сквозь трещины». Американское математическое общество. Архивировано из оригинала 13.11.2009 . Получено 28.04.2021 .
• Bollobás, Béla ; Riordan, Oliver (2006). Перколяция. Cambridge University Press. ISBN 978-0521872324. Архивировано из оригинала 2015-09-23 . Получено 2008-06-26 .
• Kesten, Harry (май 2006 г.). «Что такое ... просачивание?» (PDF) . Notices of the American Mathematical Society . 53 (5): 572–573. ISSN  1088-9477. Архивировано (PDF) из оригинала 2021-05-02 . Получено 2021-04-28 .

Внешние ссылки

• PercoVIS: программа для Mac OS X для визуализации просачивания в сетях в реальном времени
• Интерактивная перколяция
• Онлайн-курс Nanohub по теории перколяции