Перколяция бутстрапа - Bootstrap percolation

В статистическая механика, бутстраповая перколяция это просачивание процесс, в котором случайная начальная конфигурация активных ячеек выбирается из решетка или другое пространство, а затем ячейки с несколькими активными соседями последовательно удаляются из активного набора, пока система не стабилизируется. Порядок, в котором происходит это удаление, не влияет на окончательное стабильное состояние.[1][2]

Когда порог активных соседей, необходимых для выживания активной ячейки, достаточно высок (в зависимости от решетки), единственными стабильными состояниями являются состояния без активных ячеек или состояния, в которых каждый кластер активных ячеек бесконечно велик. Например, на квадратная решетка с район фон Неймана, существуют конечные кластеры, по крайней мере, с двумя активными соседями на ячейку кластера, но когда требуются три или четыре активных соседа, любой стабильный кластер должен быть бесконечным.[1] С тремя активными соседями, необходимыми для того, чтобы оставаться активными, бесконечный кластер должен бесконечно растягиваться в трех или четырех возможных основных направлениях, и любые конечные дыры, которые он содержит, обязательно будут прямоугольными. В этом случае критическая вероятность равно 1, что означает, что когда вероятность того, что каждая ячейка будет активной в начальном состоянии, меньше 1, тогда почти наверняка нет бесконечного кластера.[3] Если начальное состояние активно везде, кроме п × п квадрат, в котором одна ячейка в каждой строке и столбце неактивна, то эти пустоты с одной ячейкой объединятся, образуя пустоту, которая покрывает весь квадрат, если и только если неактивные ячейки имеют образец отделимая перестановка.[4] В любом более высоком измерении, для любого порога существует аналогичная критическая вероятность, ниже которой все ячейки почти наверняка становятся неактивными, а выше которой некоторые кластеры почти наверняка выживают.[5]

Перколяцию бутстрапа можно интерпретировать как клеточный автомат, напоминающий Игра жизни Конвея, при котором живые клетки погибают, когда у них слишком мало живых соседей. Однако, в отличие от «Жизни Конвея», мертвые клетки больше никогда не оживают.[6][7] Его также можно рассматривать как модель эпидемии в которых неактивные клетки считаются инфицированными, а активные клетки со слишком большим количеством инфицированных соседей сами заражаются.[5] Наименьший порог, который позволяет некоторым ячейкам исходного кластера выжить, - это вырождение его графа смежности, и остаток кластера, который выживает с порогом k это k-ядро этого графика.[8]

Одно из применений бутстраповской перколяции возникает при изучении Отказоустойчивость для распределенных вычислений. Если некоторые процессоры в большой сетке процессоров выходят из строя (становятся неактивными), то может также потребоваться деактивировать другие процессоры со слишком небольшим количеством активных соседей, чтобы сохранить высокую связность оставшейся сети. Анализ перколяции начальной загрузки может использоваться для определения вероятности отказа, которую может выдержать система.[9]

использованная литература

  1. ^ а б Chalupa, J .; Leath, P. L .; Райх, Г. Р. (1979), "Перколяция бутстрапа на решетке Бете", Журнал физики C: Физика твердого тела, 12 (1): L31 – L35, Bibcode:1979JPhC ... 12L..31C, Дои:10.1088/0022-3719/12/1/008.
  2. ^ Адлер, Жанна (1991), "Перколяция бутстрапа", Physica A: Статистическая механика и ее приложения, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, Дои:10.1016 / 0378-4371 (91) 90295-н.
  3. ^ van Enter, Aernout C. D. (1987), "Доказательство аргумента Стрэйли в пользу перколяции бутстрапа", Журнал статистической физики, 48 (3–4): 943–945, Bibcode:1987JSP .... 48..943В, Дои:10.1007 / BF01019705, Г-Н  0914911.
  4. ^ Шапиро, Луи; Стивенс, Артур Б. (1991), "Перколяция бутстрапа, числа Шредера и N-проблема королей ", Журнал SIAM по дискретной математике, 4 (2): 275–280, Дои:10.1137/0404025, Г-Н  1093199.
  5. ^ а б Балог, Йожеф; Боллобаш, Бела; Думинил-Копен, Гюго; Моррис, Роберт (2012), «Острый порог бутстраповской перколяции во всех измерениях», Труды Американского математического общества, 364 (5): 2667–2701, arXiv:1010.3326, Дои:10.1090 / S0002-9947-2011-05552-2, Г-Н  2888224.
  6. ^ Aizenman, M .; Лебовиц, Дж. Л. (1988), "Эффекты метастабильности при бутстраповской перколяции", Журнал физики A: математические и общие, 21 (19): 3801–3813, Bibcode:1988JPhA ... 21.3801A, Дои:10.1088/0305-4470/21/19/017.
  7. ^ Шонманн, Роберто Х. (1992), "О поведении некоторых клеточных автоматов, связанных с бутстраповской перколяцией", Анналы вероятности, 20 (1): 174–193, Дои:10.1214 / aop / 1176989923, JSTOR  2244552, Г-Н  1143417.
  8. ^ Готчау, Маринус (2016), Перколяция бутстрапа на вырожденных графах, arXiv:1605.07002, Bibcode:2016arXiv160507002G.
  9. ^ Киркпатрик, Скотт; Wilcke, Winfried W .; Гарнер, Роберт Б .; Хуэлс, Харальд (2002), "Перколяция в плотных массивах хранения", Physica A: Статистическая механика и ее приложения, 314 (1–4): 220–229, Bibcode:2002PhyA..314..220K, Дои:10.1016 / S0378-4371 (02) 01153-6, Г-Н  1961703.