Теория перколяции - Percolation theory

Сетевая наука
Internet_map_1024.jpg
Типы сетей
Графики
Функции
Типы
Модели
Топология
Динамика
  • Списки
  • Категории
  • Категория: Теория сетей
  • Категория: Теория графов

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

Вступление

Трехмерный граф перколяции сайтов
Проникновение связи в квадратной решетке от p = 0,3 до p = 0,52

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

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

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

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

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

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

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

  • для квадратная решетка ℤ2 в двух измерениях, пc = 1/2 для просачивания облигаций, факт, который оставался открытым более 20 лет и наконец был разрешен Гарри Кестен в начале 1980-х,[3] видеть Кестен (1982). Для перколяции сайта значение пc неизвестно из аналитического вывода, а только через моделирование больших решеток.[4]  
  • Предельный случай для решеток больших размеров дается Решетка Бете, порог которой находится на пc = 1/z − 1 для координационный номер  z. Другими словами: для обычного дерево степени , равно .
Front de percolation.png

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

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

Фазы

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

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

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

В двух измерениях с п < 1/2, с вероятностью единица существует единственный бесконечный замкнутый кластер (замкнутый кластер - это максимальное связное множество «замкнутых» ребер графа). Таким образом, докритическую фазу можно описать как конечные открытые острова в бесконечном замкнутом океане. Когда п > 1/2 происходит прямо противоположное, с конечными замкнутыми островами в бесконечном открытом океане. Картина более сложная, когда d ≥ 3 поскольку пc < 1/2, и существует сосуществование бесконечных открытых и замкнутых кластеров при п между пc и1 − пcО характере фазового перехода перколяции см. Stauffer and Aharony.[12] и Бунде и Хэвлин[13] . По поводу просачивания сетей см. Cohen and Havlin.[14]

Критичность

Увеличьте критический кластер перколяции (щелкните для анимации)

Перколяция имеет необычность в критической точке п = пc и многие свойства ведут себя как степенной закон с , возле . Теория масштабирования предсказывает существование критические показатели, в зависимости от количества d размерностей, определяющих класс особенности. Когда d = 2 эти прогнозы подкрепляются аргументами из конформная теория поля и Эволюция Шрамма – Лёвнера, и включать прогнозируемые числовые значения для показателей. Значения показателей приведены в.[12][13] Большинство этих предсказаний являются предположениями, за исключением случаев, когда число d размеров удовлетворяет либо d = 2 или d ≥ 6. Они включают:

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

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

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

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

Приложения

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

Теория перколяции была использована для успешного прогнозирования фрагментации оболочек биологических вирусов (капсидов),[30] с порогом фрагментации Гепатит Б вирус капсид предсказано и обнаружено экспериментально.[31] Когда критическое количество субъединиц было случайным образом удалено из наноскопической оболочки, она фрагментируется, и эта фрагментация может быть обнаружена с помощью масс-спектроскопии с обнаружением заряда (CDMS) среди других методов одночастичных. Это молекулярный аналог обычной настольной игры. Дженга, и имеет отношение к разборке вирусов.

В экологии

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

Перколяция многослойных взаимозависимых сетей

Булдырев и др.[34] разработал структуру для изучения перколяции в многослойных сетях с зависимостями между слоями. Обнаружены новые физические явления, в том числе резкие переходы и каскадные отказы.[35] Когда сети встроены в пространство, они становятся чрезвычайно уязвимыми даже для очень небольшой части зависимых ссылок.[36] и для локальных атак на нулевую часть узлов.[37][38] Когда вводится восстановление узлов, обнаруживается богатая фазовая диаграмма, включающая многокритические точки, гистерезис и метастабильные режимы.[39][40]

В пробке

В недавних статьях теория перколяции применялась для изучения дорожного движения в городе. Качество глобального трафика в городе в данный момент времени можно охарактеризовать одним параметром - критическим порогом перколяции. Критический порог представляет собой скорость, ниже которой можно проехать значительную часть городской сети. Выше этого порога городская сеть разбивается на кластеры разных размеров, и можно перемещаться по относительно небольшим районам. Этот новый метод также позволяет определять узкие места повторяющегося трафика.[41] Критические показатели, характеризующие распределение хорошего трафика по размеру кластера, аналогичны показателям теории перколяции.[42] Также обнаружено, что в часы пик транспортная сеть может иметь несколько метастабильных состояний различных размеров сети и чередоваться между этими состояниями.[43] Эмпирическое исследование пространственно-временного распределения размеров пробок было проведено Zhang et al.[44] Они нашли примерный универсальный степенной закон распределения размеров пробок в разных городах. Серок и др. Разработали метод определения функциональных кластеров пространственно-временных улиц, которые представляют свободный транспортный поток в городе.[45]

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

Рекомендации

  1. ^ Sahini, M .; Сахими, М. (13 июля 2003 г.). Приложения теории перколяции. CRC Press. ISBN  978-0-203-22153-2.
  2. ^ а б Broadbent, S. R .; Хаммерсли, Дж. М. (2008). «Перколяционные процессы». Математические труды Кембриджского философского общества. 53 (3): 629. Bibcode:1957PCPS ... 53..629B. Дои:10.1017 / S0305004100032680. ISSN  0305-0041.
  3. ^ Боллобаш, Бела; Риордан, Оливер (2006). «Острые пороги и просачивание в самолет». Случайные структуры и алгоритмы. 29 (4): 524–548. arXiv:математика / 0412510. Дои:10.1002 / rsa.20134. ISSN  1042-9832. S2CID  7342807.
  4. ^ MEJ Newman; Р. М. Зифф (2000). «Эффективный алгоритм Монте-Карло и высокоточные результаты перколяции». Письма с физическими проверками. 85 (19): 4104–4107. arXiv:cond-mat / 0005264. Дои:10.1103 / Physrevlett.85.4104. PMID  11056635. S2CID  747665.
  5. ^ Эрдёш П. и Реньи А. (1959). «О случайных графах И.». Publ. Математика. (6): 290–297.
  6. ^ Эрдёш П. и Реньи А. (1960). «Эволюция случайных графов». Publ. Математика. Inst. Подвешенный. Акад. Sci. (5): 17–61.
  7. ^ Боллоба Б. (1985). «Случайные графы». Академический.
  8. ^ Hassan, M. K .; Рахман, М. М. (2015). «Перколяция на мультифрактальной безмасштабной плоской стохастической решетке и ее класс универсальности». Phys. Ред. E. 92 (4): 040101. arXiv:1504.06389. Bibcode:2015PhRvE..92d0101H. Дои:10.1103 / PhysRevE.92.040101. PMID  26565145. S2CID  119112286.
  9. ^ Hassan, M. K .; Рахман, М. М. (2016). «Класс универсальности перколяции узлов и связей на мультифрактальной безмасштабной плоской стохастической решетке». Phys. Ред. E. 94 (4): 042109. arXiv:1604.08699. Bibcode:2016PhRvE..94d2109H. Дои:10.1103 / PhysRevE.94.042109. PMID  27841467. S2CID  22593028.
  10. ^ Кестен, Гарри (1982). Теория перколяции для математиков. Дои:10.1007/978-1-4899-2730-9. ISBN  978-0-8176-3107-9.
  11. ^ Grimmett, G.R .; Марстранд, Дж. М. (1990). «Надкритическая фаза просачивания проходит хорошо». Труды Королевского общества A: математические, физические и инженерные науки. 430 (1879): 439–457. Bibcode:1990RSPSA.430..439G. Дои:10.1098 / rspa.1990.0100. ISSN  1364-5021. S2CID  122534964.
  12. ^ а б Штауфер, Дитрих; Ахарони, Энтони (1944). «Введение в теорию перколяции». Publ. Математика. (6): 290–297. ISBN  978-0-7484-0253-3.
  13. ^ а б Бунде А. и Хавлин С. (1966). «Фракталы и неупорядоченные системы». Springer.
  14. ^ Коэн Р. и Хэвлин С. (2010). «Сложные сети: структура, надежность и функции». Издательство Кембриджского университета.
  15. ^ Гриммет, Джеффри (1999). Перколяция. Grundlehren der Mathematischen Wissenschaften. 321. Дои:10.1007/978-3-662-03981-6. ISBN  978-3-642-08442-3. ISSN  0072-7830.
  16. ^ Хара, Такаши; Слэйд, Гордон (1990). «Критическое поведение среднего поля для перколяции в больших измерениях». Коммуникации по математической физике. 128 (2): 333–391. Bibcode:1990CMaPh.128..333H. Дои:10.1007 / BF02108785. ISSN  0010-3616. S2CID  119875060.
  17. ^ Смирнов, Станислав (2001). «Критическая перколяция на плоскости: конформная инвариантность, формула Карди, пределы масштабирования». Comptes Rendus de l'Académie des Sciences, Série I. 333 (3): 239–244. arXiv:0909.4499. Bibcode:2001CRASM.333..239S. CiteSeerX  10.1.1.246.2739. Дои:10.1016 / S0764-4442 (01) 01991-7. ISSN  0764-4442.
  18. ^ Адлер, Жанна (1991), "Перколяция бутстрапа", Physica A: Статистическая механика и ее приложения, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, Дои:10.1016 / 0378-4371 (91) 90295-н.
  19. ^ Паршани, Р .; Булдырев, С. В .; Хавлин, С. (2010). «Критическое влияние групп зависимостей на работу сетей». Труды Национальной академии наук. 108 (3): 1007–1010. arXiv:1010.4498. Bibcode:2011ПНАС..108.1007П. Дои:10.1073 / pnas.1008404108. ISSN  0027-8424. ЧВК  3024657. PMID  21191103.
  20. ^ Шао, Цзя; Хавлин, Шломо; Стэнли, Х. Юджин (2009). «Динамическая модель мнения и распространение вторжений». Письма с физическими проверками. 103 (1): 018701. Bibcode:2009PhRvL.103a8701S. Дои:10.1103 / PhysRevLett.103.018701. ISSN  0031-9007. PMID  19659181.
  21. ^ Березин, Йехиель; Башан, Амир; Данцигер, Майкл М .; Ли, Дацин; Хавлин, Шломо (2015). «Локализованные атаки на пространственно встроенные сети с зависимостями». Научные отчеты. 5 (1): 8934. Bibcode:2015НатСР ... 5Э8934Б. Дои:10.1038 / srep08934. ISSN  2045-2322. ЧВК  4355725. PMID  25757572.
  22. ^ Shao, S .; Хуанг, X .; Stanley, H.E .; Хавлин, С. (2015). «Распространение локальных атак на сложные сети». Новый J. Phys. 17 (2): 023049. arXiv:1412.3124. Bibcode:2015NJPh ... 17b3049S. Дои:10.1088/1367-2630/17/2/023049. S2CID  7165448.
  23. ^ Шай, S; Kenett, D.Y; Kenett, Y.N; Фауст, М; Добсон, S; Хавлин, С. (2015). ""Критический переломный момент в разделении двух типов переходов в модульных сетевых структурах"". Phys. Ред. E. 92: 062805.
  24. ^ Донг, Гаогао; Фань, Цзинфан; Шехтман, Луи М; Шай, Сарай; Ду, Жуйджин; Тиан, Лисинь; Чен, Сяосун; Стэнли, Х. Юджин; Хавлин, Шломо (2018). ""Устойчивость сетей со структурой сообщества ведет себя так, как если бы они находились во внешнем поле"". Труды Национальной академии наук. 115 (27): 6911–6915.
  25. ^ Ли, Дацин; Фу, Боуэн; Ван, Юньпэн; Лу, Гуанцюань; Березин, Йехиель; Стэнли, Х. Юджин; Хавлин, Шломо (2015). «Перколяционный переход в динамической сети трафика с развивающимися критическими узкими местами». Труды Национальной академии наук. 112 (3): 669–672. Bibcode:2015ПНАС..112..669Л. Дои:10.1073 / pnas.1419185112. ISSN  0027-8424. ЧВК  4311803. PMID  25552558.
  26. ^ Майдандзич, Антонио; Подобник, Борис; Булдырев, Сергей В .; Kenett, Dror Y .; Хавлин, Шломо; Юджин Стэнли, Х. (2013). «Самопроизвольное восстановление в динамических сетях». Природа Физика. 10 (1): 34–38. Bibcode:2014НатФ..10 ... 34М. Дои:10.1038 / nphys2819. ISSN  1745-2473.
  27. ^ Данцигер, Майкл М .; Шехтман, Луи М .; Березин, Йехиель; Хавлин, Шломо (2016). «Влияние пространственности на мультиплексные сети». EPL (Еврофизические письма). 115 (3): 36002. arXiv:1505.01688. Bibcode:2016EL .... 11536002D. Дои:10.1209/0295-5075/115/36002. ISSN  0295-5075.
  28. ^ Иван Бонамасса; Бная Гросс; Майкл М. Данцигер; Шломо Хавлин (2019). «Критическое растяжение режимов среднего поля в пространственных сетях». Phys. Rev. Lett. 123 (8): 088301. Дои:10.1103 / PhysRevLett.123.088301. PMID  31491213.
  29. ^ Юань, Синь; Ху, Яньцин; Стэнли, Х. Юджин; Хавлин, Шломо (28 марта 2017). «Искоренение катастрофического коллапса во взаимозависимых сетях с помощью усиленных узлов». Труды Национальной академии наук. 114 (13): 3311–3315. arXiv:1605.04217. Bibcode:2017ПНАС..114.3311Y. Дои:10.1073 / pnas.1621369114. ISSN  0027-8424. ЧВК  5380073. PMID  28289204.
  30. ^ Brunk, N.E .; Ли, Л. С .; Glazier, J. A .; Butske, W .; Злотник, А. (2018). «Молекулярная Дженга: перколяционный фазовый переход (коллапс) в вирусных капсидах». Физическая биология. 15 (5): 056005. Дои:10.1088 / 1478-3975 / aac194. ЧВК  6004236. PMID  29714713.
  31. ^ Ли, Л. С .; Brunk, N .; Haywood, D. G .; Кейфер, Д .; Pierson, E .; Кондилис, П .; Злотник, А. (2017). «Молекулярный макет: удаление и замена субъединиц в капсиде вируса гепатита В». Белковая наука. 26 (11): 2170–2180. Дои:10.1002 / pro.3265. ЧВК  5654856. PMID  28795465.
  32. ^ Boswell, G.P .; Britton, N.F .; Фрэнкс, Н. Р. (1998-10-22). «Фрагментация среды обитания, теория просачивания и сохранение ключевого вида». Труды Лондонского королевского общества B: биологические науки. 265 (1409): 1921–1925. Дои:10.1098 / rspb.1998.0521. ISSN  0962-8452. ЧВК  1689475.
  33. ^ Davis, S .; Trapman, P .; Leirs, H .; Бегон, М .; Heesterbeek, J. a. П. (31.07.2008). «Порог численности чумы как критического явления просачивания». Природа. 454 (7204): 634–637. Дои:10.1038 / природа07053. HDL:1874/29683. ISSN  1476-4687. PMID  18668107. S2CID  4425203.
  34. ^ Булдырев, С.В .; Паршани, Р .; Paul, G .; Stanley, H.E .; Хавлин, С. (2010). ""Катастрофический каскад отказов во взаимозависимых сетях"". Природа. 464 (08932).
  35. ^ Gao, J .; Булдырев, С.В .; Stanley, H.E .; Хавлин, С. (2012). ""Сети, образованные из взаимозависимых сетей"". Природа Физика. 8 (1): 40–48.
  36. ^ Bashan, A .; Березин, Ю .; Булдырев, С.В .; Хавлин, С. (2013). ""Крайняя уязвимость взаимозависимых пространственно встроенных сетей"". Природа Физика. 9 (10): 667.
  37. ^ Березин, Ю .; Bashan, A .; Danziger, M.M .; Li, D .; Хавлин, С. (2015). «Локальные атаки на пространственно встроенные сети с зависимостями». Научные отчеты. 5: 8934.
  38. ^ Д Вакнин; М. М. Данцигер; С. Хавлин (2017). ""Распространение локализованных атак в пространственных мультиплексных сетях"". Новый J. Phys. 19: 073037.
  39. ^ Майдандзич, Антонио; Подобник, Борис; Булдырев, Сергей В .; Kenett, Dror Y .; Хавлин, Шломо; Юджин Стэнли, Х. (2013). ""Самопроизвольное восстановление в динамических сетях"". Природа Физика. 10 (1): 34–38.
  40. ^ Майдандзич, Антонио; Браунштейн, Лидия А .; Курм, Честер; Воденская, Ирена; Леви-Карсьенте, Сари; Юджин Стэнли, H .; Хавлин, Шломо (2016). ""Множество переломных моментов и оптимальный ремонт во взаимодействующих сетях"". Nature Communications. 7: 10850.
  41. ^ Д. Ли; Б. Фу; Ю. Ван; Г. Лу; Ю. Березин; ОН. Стэнли; С. Хавлин (2015). «Перколяционный переход в динамической сети трафика с развивающимися критическими узкими местами». PNAS. 112: 669.
  42. ^ G Zeng; D Li; S Guo; L Gao; Z Gao; Его Превосходительство Стэнли; С. Хавлин (2019). «Переключение критических режимов перколяции в динамике городского движения». Труды Национальной академии наук. 116 (1): 23–28.
  43. ^ G Zeng; Дж. Гао; Л. Шехтман; S Guo; W Lv; J Wu; H Лю; О Леви! Ди Ли (2020). ""Множественные метастабильные состояния сети в городском трафике"". Труды Национальной академии наук. 117 (30): 17528–17534.
  44. ^ Лимиао Чжан; Гуанвен Цзэн; Дацин Ли; Хай-Цзюнь Хуан; H Юджин Стэнли; Шломо Хавлин (2019). ""Безмассовая устойчивость к настоящим пробкам"". Труды Национальной академии наук. 116 (18): 8673–8678.
  45. ^ Нимрод Серок; Орр Леви; Шломо Хавлин; Эфрат Блюменфельд-Либерталь (2019). ""Выявление взаимосвязей между сетью городских улиц и их динамическими транспортными потоками: значение для планирования"". Публикации SAGE. 46 (7): 1362.

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

внешняя ссылка