パーコレーション

ランダムにセルを開き、クラスターが連結して水が通り抜ける臨界確率(パーコレーション閾値)を探ります。

  • 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およびHammersley(1957年)
正方サイト(Square sites)
閾値は約0.592746
正方ボンドおよび三角サイト
閾値は厳密に1/2
盤面サイズ
最大200 × 200セル

パーコレーションは、ランダムな迷路を通り抜ける現象を扱う数学です。コーヒーの粉や多孔質の岩石を浸透する水、まばらな森林を広がる火災、集団内を伝播する感染症などがこれに該当します。モデルの仕組みは単純です。盤面の各セルは確率pで開かれ、それ以外はブロックされます。接触している開いたセル同士がクラスターを形成し、いずれかのクラスターが盤面の上端から下端までをつなぐかどうかが問題となります。Simon BroadbentとJohn Hammersleyが1957年にパーコレーション理論を導入して以来、ひとつの物理量のわずかな変化が全体の挙動を劇的に変える相転移の標準モデルとして広く研究されています。

pの値を少しずつ上げて観察してみてください。臨界確率を下回る領域では、開いたセルは小さく孤立したクラスターにとどまり、上部から注いだ水は途中で止まります。しかし臨界確率をわずかに超えた瞬間、クラスター同士が結合して盤面全体を縦断する巨大なクラスター(金色で表示)が現れ、水が下端まで通り抜けます。正方格子のサイトパーコレーションにおける臨界確率は約0.5927であり、2000年にMark NewmanとRobert Ziffが高精度に算出しました。一方、正方格子のボンドパーコレーションや三角格子のサイトパーコレーションでは厳密に1/2となり、ボンドについては1980年にHarry Kestenが証明しています。クラスターの色分けにはHoshen-Kopelman法が用いられています。

グラフはこの変化がいかに急激であるかを示しています。バックグラウンドでは、NewmanとZiffの手法に沿って同じサイズの空の盤面を数百枚生成し、セルをランダムな順序でひとつずつ開きながら、各盤面が初めて浸透する確率を記録しています。各pにおいて浸透している盤面の割合をプロットすると、臨界確率の周辺で急激に立ち上がるS字カーブが描かれ、盤面サイズが大きくなるほどその傾斜は険しくなります。盤面をドラッグしてセルを開閉したり、3種類の格子を比較したり、浸透確率のデータをCSVとしてエクスポートしたりすることが可能です。

パーコレーションの使い方

  1. 確率を設定する. Chance open (p)を動かして開くセルの割合を変更します。乱数のシードは保持されるため、pを上げると既存の配置を崩さず新しいセルだけが開きます。Jump to the thresholdを押すと臨界確率へ直接移動できます。
  2. 水を流す. Pour water(水を流す)をオンにすると、上端の行から水が浸入し、開いたセルを1ステップごとに1層ずつ広がります。カウンターで下端への到達を確認でき、Flow speed(流速)で広がる速度を調整できます。
  3. 色を確認する. 連結した開いたセルの各クラスターはそれぞれ固有の色で表示され、塞がったセルは暗く描かれます。上端から下端まで貫通したクラスターは金色で強調されます。
  4. 格子を比較する. Lattice(格子)を切り替えることで、Square sites(正方サイト)、Square bonds(正方ボンド:すべてのセルが存在し隣接部間の結合が確率pで開く)、Triangular sites(三角サイト:各セルが6つの隣接セルを持つレンガ状配置)を選択できます。
  5. 盤面を編集する. 盤面(Board)上をドラッグして、通過したセル(結合モデルの場合はリンク)を通行可能にしたり塞いだりできます。クラスターを分断したり、2つのクラスターを繋げたりしてみてください。Rerunを押すと、編集した盤面上でt = 0から再び水(Water)を流します。Restartは編集内容を破棄して盤面を最初からやり直します。Resetはすべての設定も初期値に戻します。
  6. グラフを読み取る. 曲線は、最大400枚のランダムな盤面をもとに算出した、そのサイズにおいて各確率で浸透が生じる盤面の割合を示しています。丸印は現在選択されているpの位置を表します。
  7. エクスポートする. 水が流れる様子をPNG画像、動画、GIFとして保存したり、浸透確率データをCSVファイルとして書き出せます。Pour waterがオンの場合、Record full runは上部から再度水を流し、水が止まるまでを記録します。オフの場合はRecord 30 s from the startで最初の30秒間を記録します。

よくある質問

パーコレーションとは何ですか?

ランダムな構造における連結性を探る研究です。セル(または結合)が確率pでランダムに開き、開いた部分が連結して一方の端から反対側の端へと続く経路を形成するかどうかを調べます。多孔質材料中の流体の浸透、火災や感染症の拡大、混合物における電気伝導などのモデルとして用いられます。

パーコレーション閾値とは何ですか?

十分に大きな盤面において、端から端まで貫通するクラスターが初めて出現する臨界確率のことです。正方格子のサイトパーコレーションでは約0.592746、正方格子のボンドパーコレーションおよび三角格子のサイトパーコレーションでは厳密に1/2となります。大きな盤面では、閾値を下回ると貫通経路はほぼ存在せず、閾値を超えるとほぼ確実に存在します。

なぜこれほど変化が急激なのですか?

相転移現象であるためです。無限大の盤面においては、温度変化で水が凍るように、貫通クラスターが存在する確率が閾値を境に0から1へと一気に跳躍します。有限の盤面ではその跳躍が緩和されてグラフのような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.