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

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

Введение

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

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

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

История

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

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

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

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

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

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

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

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

для квадратной решетки $ℤ 2$ в двух измерениях $p c =.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2$ Что касается просачивания облигаций, факт, который оставался открытым более 20 лет и был окончательно решен Гарри Кестеном в начале 1980-х годов, ^[6] см. Kesten (1982). Для перколяции узлов на квадратной решетке значение $pc не известно из аналитического вывода, а только посредством$ $моделирования$ больших решеток, которое дает оценку $pc =$ 0,59274621 ± 0,00000013. ^[7]
Предельный случай для решеток больших размерностей представляет собой решетка Бете , порог которой находится при $p c = 1 / г - 1$ для координационного числа $z$ . Другими словами: для регулярного дерева степени равно . $z$ $p_{c}$ $1/(z-1)$

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

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

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

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

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

Фазы

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

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

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

В двух измерениях с $p < 1 / 2$ , с вероятностью единица существует единственный бесконечный замкнутый кластер (замкнутый кластер — это максимальное связное множество «замкнутых» ребер графа). Таким образом, докритическую фазу можно описать как конечные открытые острова в бесконечном замкнутом океане. Когда $р > 1 / 2$ происходит как раз обратное: ограниченное количество закрытых островов в бесконечном открытом океане. Картина усложняется, когда $d \geq 3,$ поскольку $p c < 1 / 2$ $,$ и существует сосуществование бесконечных открытых и закрытых кластеров для $p$ $между$ pc $и$ 1 $- pc$ .

Критичность

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

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

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

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

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

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

Приложения

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

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

В экологии

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

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

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

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

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