Теория просачивания в случайных графах

Введение

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

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

Введение

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

A representative question (and the source of the name) is as follows. Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three dimensional network of n × n × n vertices, usually called "sites", in which the edge or "bonds" between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path (meaning a path, each of whose links is an "open" bond) exists from the top to the bottom? The behavior for large n is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by , and has been studied intensively by mathematicians and physicists since then. In a slightly different mathematical model for obtaining a random graph, a site is "occupied" with probability p or "empty" (in which case its edges are removed) with probability 1 – p; the corresponding problem is called site percolation. The question is the same: for a given p, what is the probability that a path exists between top and bottom? Similarly, one can ask, given a connected graph at what fraction 1 – p of failures the graph will become disconnected (no large component). The same questions can be asked for any lattice dimension. As is quite typical, it is actually easier to examine infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By Kolmogorov's zero–one law, for any given p, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of p (proof via coupling argument), there must be a critical p (denoted by pc) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for n as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of p.

История

Теория Флори–Стокмайера была первой теорией, исследующей процессы перколяции. История модели перколяции, в том виде, в котором мы её знаем, берет начало в угольной промышленности. С момента промышленной революции экономическая важность этого источника энергии стимулировала множество научных исследований, направленных на понимание его состава и оптимизацию использования. В 1930-е и 1940-е годы качественный анализ, проводимый органической химией, все больше уступал место более количественным исследованиям. В этом контексте в 1938 году была создана Британская ассоциация исследований использования угля (BCURA) – исследовательское объединение, финансируемое владельцами угольных шахт. В 1942 году Розалинда Франклин, недавно окончившая Кембриджский университет по специальности химия, присоединилась к BCURA. Она начала исследования плотности и пористости угля. Во время Второй мировой войны уголь был важным стратегическим ресурсом, используемым как источник энергии, а также в качестве основного компонента противогазов. Уголь представляет собой пористую среду. Для измерения его «истинной» плотности его необходимо было погрузить в жидкость или газ, молекулы которого достаточно малы, чтобы заполнить микроскопические поры. Пытаясь измерить плотность угля с помощью различных газов (гелия, метанола, гексана, бензола), и обнаружив различные значения в зависимости от используемого газа, Розалинда Франклин показала, что поры угля состоят из микроструктур различной длины, которые действуют как микроскопическое сито, разделяющее газы. Она также обнаружила, что размер этих структур зависит от температуры карбонизации в процессе производства угля. Благодаря этим исследованиям она получила степень доктора философии и покинула BCURA в 1946 году. В середине 1950-х годов Саймон Бродбент работал в BCURA в качестве статистика. Среди прочего, он изучал использование угля в противогазах. Один из вопросов заключался в понимании того, как жидкость может диффундировать в угольных порах, которые моделируются как случайный лабиринт открытых или закрытых туннелей. В 1954 году, во время симпозиума по методам Монте-Карло, он обратился к Джону Хаммерсли с вопросами об использовании численных методов для анализа этой модели. В своей статье 1957 года Бродбент и Хаммерсли представили математическую модель для описания этого явления, то есть перколяции.

The Flory–Stockmayer theory was the first theory investigating percolation processes. The history of the percolation model as we know it has its root in the coal industry. Since the industrial revolution, the economical importance of this source of energy fostered many scientific studies to understand its composition and optimize its use. During the 30' and 40', the qualitative analysis by organic chemistry left more and more room to more quantitative studies. In this context, the British Coal Utilisation Research Association (BCURA) was created in 1938. It is a research association funded by the coal mines owners. In 1942, Rosalind Franklin, who then recently graduated in chemistry from the university of Cambridge, joined the BCURA. She started research on the density and porosity of coal. During the Second World War, coal was an important strategic resource. It was used as a source of energy, but also was the main constituent of gas masks. Coal is a porous medium. To measure its 'real' density, one was to sink it in a liquid or a gas whose molecules are small enough to fill its microscopic pores. While trying to measure the density of coal using several gases (helium, methanol, hexane, benzene), and as she found different values depending on the gas used, Rosalind Franklin showed that the pores of coal are made of microstructures of various lengths that act as a microscopic sieve to discriminate the gases. She also discovered that the size of these structures depends on the temperature of carbonation during the coal production. With this research, she obtained a PhD degree and left the BCURA in 1946. In the mid fifties, Simon Broadbent worked in the BCURA as a statistician. Among other interests, he studied the use of coal in gas masks. One question is to understand how a fluid can diffuse in the coal pores, modeled as a random maze of open or closed tunnels. In 1954, during a symposium on Monte Carlo methods, he asks questions to John Hammersley on the use of numerical methods to analyze this model. Broadbent and Hammersley introduced in their article of 1957 a mathematical model to model this phenomenon, that is percolation.

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

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

Субкритические и сверхкритические

Главный факт в субкритической фазе — «экспоненциальный спад». То есть, когда p < pc, вероятность того, что конкретная точка (например, начало координат) содержится в открытом кластере (то есть максимальном связном множестве «открытых» рёбер графа) размера r, экспоненциально стремится к нулю при r, стремящемся к бесконечности. Это было доказано для перколяции в трёх и более измерениях и независимо в двух измерениях, и вошло в доказательство Кестена того, что двойственный граф квадратной решётки ℤ² также является квадратной решёткой. Отсюда следует, что в двух измерениях сверхкритическая фаза двойственна субкритическому процессу перколяции. Это даёт практически полную информацию о сверхкритической модели. Основной результат для сверхкритической фазы в трёх и более измерениях заключается в том, что для достаточно большого N существует бесконечный открытый кластер в двухмерной полосе ℤ² × [0, N]^(d − 2). Это было доказано. В двух измерениях при p > pc с вероятностью один существует единственный бесконечный закрытый кластер (закрытый кластер — это максимальное связное множество «закрытых» рёбер графа). Таким образом, субкритическую фазу можно описать как конечные открытые острова в бесконечном закрытом океане, а сверхкритическую — как конечные закрытые острова в бесконечном открытом океане. Картина становится более сложной при d ≥ 3, поскольку происходит сосуществование бесконечных открытых и закрытых кластеров для p, находящегося между pc и 1 − pc.

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

Теория перколяции успешно применялась для прогнозирования фрагментации биологических вирусных оболочек (капсидов), при этом порог фрагментации капсида вируса гепатита B был предсказан и экспериментально подтвержден. Когда критическое число субъединиц случайно удаляется из наноскопической оболочки, она распадается на фрагменты, что может быть обнаружено с помощью масс-спектроскопии обнаружения заряда (CDMS) и других методов анализа отдельных частиц. Это молекулярный аналог популярной настольной игры Jenga и имеет значение для более широкого изучения дезассемблирования вирусов. Интересно, что более стабильные вирусные частицы (структуры с более высоким порогом фрагментации) встречаются в природе в большем количестве, а также в моделях распространения бактерии чумы Yersinia pestis.