Перколяция

Открывайте ячейки наугад и найдите критическую вероятность, при которой кластеры соединяются и вода начинает протекать.

  • Blocked
  • Open, one color per cluster
  • Cluster joining top and bottom
  • Water
100%

Each cell is open with chance p. Just above a critical chance, open clusters suddenly join into one that spans the board and water poured in at the top gets through. Drag across the board to open or close cells and try to block or connect the flow; Rerun keeps your changes.

Setup
Lattice
120 × 120 cells
Model
0.593
View
60 cells per second

Как вам Перколяция?

О генераторе Перколяция

Первая публикация
Broadbent and Hammersley, 1957
Квадратные узлы
Порог около 0.592746
Квадратные связи и треугольные узлы
Порог строго равен 1/2
Размер решетки
Вплоть до 200 × 200 ячеек

Теория перколяции изучает прохождение сигналов или потоков через случайные среды: просачивание воды сквозь слой молотого кофе или пористую породу, распространение огня по фрагментированному лесу или движение эпидемии по контактам в обществе. Базовая модель предельно проста: каждая ячейка сетки открыта с вероятностью p и заблокирована с вероятностью 1 − p. Соседние открытые ячейки формируют связанные кластеры, а главный вопрос заключается в том, соединит ли хотя бы один кластер верхний край решетки с нижним. Simon Broadbent и John Hammersley описали перколяцию в 1957 году, и с тех пор она служит фундаментом для изучения геометрических фазовых переходов.

Плавно увеличивайте вероятность p и наблюдайте за метаморфозой. Ниже критического порога открытые ячейки образуют лишь небольшие изолированные группы, и пущенная сверху вода моментально застревает. Но стоит перейти критическую точку, как островки внезапно срастаются в единый бесконечный стягивающий кластер, подсвеченный золотым, сквозь который жидкость беспрепятственно протекает вниз. Для задачи узлов на квадратной решетке порог составляет около 0.5927 (значение, детально рассчитанное Mark Newman и Robert Ziff в 2000 году), а для связей на квадратной решетке и узлов на треугольной сетке он равен строго 1/2, что Harry Kesten строго доказал для связей в 1980 году. Кластеры нумеруются и окрашиваются эффективным алгоритмом Хошена-Копельмана.

График наглядно демонстрирует поразительную резкость фазового перехода. В фоновом режиме симулятор просчитывает сотни независимых случайных решеток такого же размера, открывая ячейки по одной в случайном порядке по методу Newman-Ziff, и фиксирует точное значение p, при котором кластер впервые соединяет противоположные края. Доля проводящих решеток формирует плавную S-образную сигмоиду, которая резко крутеет вокруг критического порога и превращается в вертикальную ступеньку по мере роста размера поля. Рисуйте курсором, чтобы вручную открывать или перекрывать ячейки, сравнивайте геометрию разных решеток и экспортируйте статистику перколяции в CSV.

Как пользоваться Перколяция

  1. Задайте вероятность. Перемещайте ползунок Chance open (p), чтобы регулировать долю открытых ячеек. Генератор сохраняет псевдослучайные числа, поэтому рост p лишь добавляет новые ячейки, а кнопка у порога позволяет сразу перейти к критической точке.
  2. Пустите воду. Включите переключатель Pour water, и вода начнет литься через верхний ряд, пошагово растекаясь по смежным открытым ячейкам. Счетчик сообщит, дошел ли поток до дна, а Flow speed отрегулирует скорость течения.
  3. Ориентируйтесь по цветам. Каждый изолированный кластер связных ячеек получает индивидуальный оттенок, закрытые блоки остаются темными, а сквозной гигантский кластер, соединяющий верх и низ, выделяется золотым цветом.
  4. Сравнивайте решетки. Меню Lattice переключает тип сетки: квадратные узлы Square sites, квадратные связи Square bonds (все узлы на месте, а открываются перемычки между соседями) или треугольные узлы Triangular sites.
  5. Редактируйте поле вручную. Ведите курсор по полю Board, чтобы открывать или блокировать узлы (или связи в случае перколяции связей): попробуйте разорвать сквозной кластер или объединить два кластера. Rerun снова пускает воду с t = 0 по отредактированному полю; Restart сбрасывает ваши изменения и генерирует поле заново; Reset также возвращает все настройки к значениям по умолчанию.
  6. Изучайте график. Кривая отображает процент случайных полей текущего разрешения, через которые может протечь поток при каждом значении p (рассчитано по выборке до 400 решеток); маркер показывает ваше текущее p.
  7. Экспортируйте результаты. Сохраняйте снимок в PNG, анимацию в видео или GIF, либо экспортируйте вероятности протекания в CSV-файл. При включенной опции Pour water кнопка Record full run заново пускает поток сверху и ведет запись до тех пор, пока вода не остановится; без нее Record 30 s from the start сохраняет первые 30 секунд процесса.

Часто задаваемые вопросы

Что изучает теория перколяции?

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

Что такое порог перколяции?

Это критическое значение вероятности, при котором на бесконечно большой решетке впервые скачком возникает макроскопический сквозной кластер. Для задачи узлов на квадратной сетке порог равен примерно 0.592746, а для задачи связей на квадратной решетке и задачи узлов на треугольной сетке он составляет строго 1/2. Ниже порога вероятность сквозного пути на большом поле стремится к нулю, выше порога — практически равна единице.

Почему фазовый переход происходит так внезапно?

Потому что это непрерывный геометрический фазовый переход второго рода. На бесконечной плоскости вероятность протекания в критической точке скачкообразно взмывает от нуля до единицы, подобно замерзанию чистой воды при 0 °C. На конечных решетках скачок сглаживается в крутую S-образную кривую, которая становится тем круче, чем больше размер моделируемого поля.

Почему для связей и треугольной решетки порог равен точно 1/2?

Благодаря геометрической двойственности и симметрии. На квадратной решетке со связями сквозной проводящий путь сверху вниз существует тогда и только тогда, когда в двойственной решетке нет непрерывной цепочки заблокированных связей слева направо. Двойственная сетка для квадратной — тоже квадратная. При p = 1/2 условия для открытых и закрытых путей абсолютно симметричны, что взаимно уравновешивает шансы на пересечение.

Как перколяция связана с лесными пожарами и эпидемиями?

Если каждое горящее дерево способно с некоторой вероятностью поджечь соседа, а заболевший человек — передать инфекцию при контакте, распространение процесса подчиняется законам перколяции. Если плотность контактов или восприимчивость ниже порога перколяции, вспышка быстро угасает локально. Если выше — охватывает всю систему. Именно поэтому даже небольшое снижение вероятности передачи способно полностью предотвратить пандемию.

Как строится график вероятности протекания?

Программа в фоновом режиме генерирует сотни пустых полей и открывает в них ячейки строго по одной в случайном порядке. Быстрый алгоритм непересекающихся множеств (union-find) отслеживает слияние кластеров и регистрирует точный момент первого соединения противоположных краев. Подсчет доли полей, ставших сквозными при каждой вероятности p, дает гладкую сигмоиду по эффективному методу Newman-Ziff (2000).

Научные источники

  1. Broadbent, S. R., & Hammersley, J. M. (1957). Percolation processes: I. Crystals and mazes. Mathematical Proceedings of the Cambridge Philosophical Society 53(3), 629–641.
  2. Hoshen, J., & Kopelman, R. (1976). Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm. Physical Review B 14(8), 3438–3445.
  3. Newman, M. E. J., & Ziff, R. M. (2000). Efficient Monte Carlo algorithm and high-precision results for percolation. Physical Review Letters 85(19), 4104–4107.
  4. Stauffer, D., & Aharony, A. (1994). Introduction to Percolation Theory (2nd ed.). London: Taylor & Francis.