퍼콜레이션

1. 개요[편집]

퍼콜레이션(percolation, 침투)은 격자의 각 자리 또는 각 결합을 서로 독립하게 확률 $p$로 “열어” 놓았을 때, 열린 것들이 이루는 연결 덩어리(클러스터)가 언제 계 전체를 가로지르는가를 다루는 확률 모형이다. 해밀토니안도 없고 온도도 없고 스핀 사이의 상호작용도 없다. 그냥 동전을 격자 칸 수만큼 던질 뿐인데, 그럼에도 불구하고 어떤 임계 확률 $p_c$ 에서 완벽한 2차 상전이가 튀어나온다. 그래서 퍼콜레이션은 “상호작용 없는 임계현상”이라는 별명을 얻었고, 상전이 이론을 배울 때 이징 모형 다음으로 반드시 거쳐가는 관문이 됐다.

물리적 직관은 커피 필터다. 원두 가루 사이의 빈틈이 충분히 이어져야 물이 아래로 “침투”한다. 빈틈 비율이 조금 모자라면 물은 중간에서 막히고, 조금 넘어서면 갑자기 콸콸 흐른다. 이 “조금”의 경계가 $p_c$ 이고, 그 근처에서 계는 모든 길이 척도에서 자기 자신을 닮은 프랙탈이 된다.¹

2. 사이트, 본드, 그리고 임계 확률[편집]

퍼콜레이션은 무엇을 여느냐에 따라 두 종류로 갈린다.

• 사이트 퍼콜레이션(site percolation): 격자의 각 자리를 확률 $p$ 로 점유시킨다. 이웃한 점유 자리끼리 연결된 것으로 본다. 다공성 고체, 픽셀 이미지, 산불 번짐 모형이 여기에 해당.
• 본드 퍼콜레이션(bond percolation): 자리는 다 있고, 각 결합을 확률 $p$ 로 연결한다. 저항 네트워크, 배관망, 전염 경로가 여기에 해당.

두 모형은 같은 보편성 부류에 속하지만 임계값은 다르다. 어떤 격자에서는 대칭성 덕분에 $p_c$ 의 정확해가 알려져 있다.

격자 / 종류	$p_c$	비고
정사각 사이트	$0.5927462\ldots$	수치해만 알려짐
정사각 본드	$1/2$	자기쌍대성으로 정확
삼각 사이트	$1/2$	자기쌍대성으로 정확
삼각 본드	$2\sin(\pi/18)\approx 0.3473$	성-삼각 변환
벌집 본드	$1-2\sin(\pi/18)\approx 0.6527$	삼각 본드와 쌍대
단순입방 사이트 (3D)	$0.3116\ldots$	수치해

정사각 본드 $p_c=1/2$ 는 격자와 그 쌍대 격자가 합동이라는 사실에서 나온다. 열린 본드가 가로로 가로지르지 못하면 닫힌 본드가 세로로 가로지른다는 배타적 사건 구조 때문에, 확률이 $1/2$ 에서 딱 맞아떨어진다. 삼각 사이트의 $1/2$ 도 비슷한 삼각형 자기쌍대 논증이다. 반면 정사각 사이트 $p_c$ 는 아직 닫힌 형태가 없어서, 40년 넘게 몬테카를로로 소수점 자릿수만 늘려오고 있다.²

무한 차원 극한인 베테 격자(Cayley tree)에서는 배위수 $z$ 에 대해 $p_c = 1/(z-1)$ 로 딱 떨어진다. 여기서 계산한 임계지수가 곧 평균장 값이고, 실제로 차원 $d \ge 6$ 이면 평균장이 정확해진다.

3. 임계 지수와 프랙탈 클러스터[편집]

$p_c$ 근처에서 세 가지 양이 멱법칙으로 발산하거나 사라진다. 무한(스패닝) 클러스터에 속할 확률 $P(p)$ 가 오더 파라미터 역할을 한다.

$$P(p) \sim (p-p_c)^{\beta}\ (p>p_c), \qquad \xi \sim |p-p_c|^{-\nu}, \qquad S \sim |p-p_c|^{-\gamma}$$

여기서 $\xi$ 는 유한 클러스터의 평균 반경, 즉 상관길이이고 $S$ 는 (무한 클러스터를 뺀) 평균 클러스터 크기다. 2차원 값은 놀랍게도 전부 유리수로 알려져 있다.³

$$\beta = \frac{5}{36}, \qquad \nu = \frac{4}{3}, \qquad \gamma = \frac{43}{18}, \qquad \tau = \frac{187}{91}$$

$\beta = 5/36 \approx 0.139$ 는 아주 작은 값이라, $P(p)$ 가 $p_c$ 를 넘자마자 거의 수직으로 솟는다. 시뮬레이션에서 “임계점을 지나니까 갑자기 다 연결되던데요”라는 인상은 이 작은 지수 탓이다.

정확히 $p=p_c$ 에서는 클러스터 크기 분포가 척도를 잃고 순수 멱법칙이 된다.

$$n_s \sim s^{-\tau}, \qquad \tau = 1 + \frac{d}{D}$$

그리고 임계 클러스터는 프랙탈이다. 반경 $R$ 안에 들어 있는 질량이 $M \sim R^{D}$ 로 자라는데, 2D에서

$$D = \frac{91}{48} \approx 1.8958$$

이다.⁴ 2보다 작으니 임계 클러스터는 계를 가로지르면서도 밀도가 0으로 수렴한다. 무한히 크지만 무한히 성긴, “구멍이 모든 척도에 있는” 스펀지다. $p$ 를 $p_c$ 보다 조금만 올리면 $\xi$ 이하 척도에서는 프랙탈, $\xi$ 이상 척도에서는 균질한 3차원(또는 2차원) 물체로 보인다. 이 교차 척도가 곧 상관길이다.

4. 유한 격자에서 $p_c$ 잡기, 그리고 포츠 모형과의 혈연[편집]

실제 시뮬레이션은 유한한 $L \times L$ 격자에서 돌기 때문에 진짜 발산은 일어나지 않는다. $\xi$ 가 $L$ 에 부딪히는 순간 모든 양이 잘린다. 이때 쓰는 표준 도구가 유한 크기 스케일링(finite-size scaling)이다. 스패닝 확률 $\Pi_L(p)$ 는

$$\Pi_L(p) = f\!\left[(p-p_c) L^{1/\nu}\right]$$

형태로 붕괴(collapse)한다. 여러 $L$ 에 대해 $\Pi_L$ 을 그리면 모든 곡선이 $p_c$ 한 점에서 교차하고, 가로축을 $(p-p_c)L^{1/\nu}$ 로 바꾸면 한 곡선으로 겹친다. 격자 수렴 지수를 뽑을 때 쓰는 리처드슨 외삽법과 발상은 같다 — 유한 해상도의 계통 오차를 척도 법칙으로 지워버리는 것.

퍼콜레이션이 진짜 상전이라는 증거는 포츠(Potts) 모형과의 대응에서 나온다. $q$-상태 포츠 모형의 분배함수를 파소프-포르투인-카스텔레인(FK) 전개로 클러스터 합으로 다시 쓰면, $q \to 1$ 극한에서 정확히 본드 퍼콜레이션이 된다. 즉 퍼콜레이션은 “상태 수 1개짜리 포츠 모형”이고, 자유에너지의 $q$ 미분이 클러스터 통계에 대응한다. 덕분에 재규격화군 계산이 그대로 적용되고, 위의 유리수 지수들도 공형장론(2D)에서 유도된다.

5. 클러스터를 세는 알고리즘[편집]

$10^6$ 개 사이트에서 클러스터를 라벨링하는 데 순진하게 BFS를 반복하면 금방 느려진다. 표준 무기는 두 개다.

• 호센-코프만(Hoshen-Kopelman) 알고리즘: 격자를 한 번만 훑으면서 왼쪽·위 이웃의 라벨을 보고 새 라벨을 주거나 물려받는다. 서로 다른 라벨이 나중에 같은 클러스터로 밝혀지면 “라벨의 라벨”을 가리키는 배열로 병합한다. 사실상 union-find(서로소 집합)의 격자 특화판이고, 메모리는 한 줄 분량만 있으면 된다.
• 뉴먼-지프(Newman-Ziff) 알고리즘: 사이트를 무작위 순서로 하나씩 추가하면서 union-find로 병합해 나가면, 한 번 훑는 것만으로 모든 $p$ 에 대한 관측량을 정준 앙상블 변환으로 얻는다. $p$ 값마다 따로 시뮬레이션을 돌리는 낭비가 사라진다.

경로 압축 + 랭크 병합을 쓴 union-find의 비용은 사실상 상수(역아커만 함수)라, 100만 사이트 라벨링이 눈 깜짝할 사이에 끝난다.⁵ 위 임베드도 이 방식으로 매 프레임 실제 라벨을 다시 계산한다.

6. 어디에 쓰이나[편집]

• 다공성 매질 유동: 공극률이 $p_c$ 아래면 투과도가 0이다. 다르시 투과도가 $p$ 의 매끄러운 함수가 아니라 임계점에서 멱법칙으로 죽는다는 사실이 유전 공학·지하수 모델의 출발점이다.
• 복합재 전도 임계: 절연 고분자에 탄소나노튜브를 섞을 때, 부피 분율이 어떤 값을 넘는 순간 전도도가 수십 자릿수 뛴다. 복합재 해석에서 필러 함량 설계는 결국 퍼콜레이션 임계 설계다. 막대 모양 필러는 종횡비가 클수록 $p_c$ 가 낮아진다.
• 산불·전염 모형: 나무 밀도 $p$ 인 숲에서 불이 반대편까지 번지는지가 그대로 스패닝 문제다. SIR 전염 모형의 최종 감염 규모도 본드 퍼콜레이션과 사상(mapping)된다.
• 네트워크 견고성: 노드를 무작위로 제거할 때 거대 연결 성분이 언제 부서지는지가 임의 그래프 위 사이트 퍼콜레이션이다. 척도 없는(scale-free) 네트워크는 $p_c \to 0$ 이라 무작위 고장에는 강하지만 표적 공격에는 취약하다는, 그 유명한 결론이 여기서 나온다.
• 셀룰러 오토마타·이미지 처리: 셀룰러 오토마타의 연결 성분 분석, 이진화 이미지의 라벨링은 전부 같은 union-find를 쓴다.

7. 관련 문서[편집]

• 상전이 · 이징 모형 · 스핀글라스
• 재규격화군 · 프랙탈
• 몬테카를로 방법 · 셀룰러 오토마타
• 다공성 매질 유동 · 복합재 해석
• 자기조직화 · 통계 · 계산물리

8. Footnotes[편집]

1. 이름 자체가 커피에서 왔다. 1957년 브로드벤트와 해머슬리가 방독면 필터(활성탄 입자 사이로 기체가 통과하는 문제)를 풀다가 정식화한 모형인데, “percolate”라는 단어를 고른 건 해머슬리였다고 한다. 방독면에서 시작해서 노벨상급 임계현상 이론으로 끝난 케이스. ↩

2. 2008년 이후 보고된 값은 $p_c = 0.59274605079210(2)$ 수준. 소수점 14자리를 갱신하려고 학계가 슈퍼컴을 갈아넣는다. 이 값이 유리수도 대수적 수도 아닐 것이라는 게 중론이지만, 증명은 없다. ↩

3. 3D는 사정이 다르다. $\beta \approx 0.4181$, $\nu \approx 0.8762$ 처럼 예쁜 유리수가 아니다. 2D의 유리수 잔치는 공형장론이라는 특수 사정 덕분이고, 3D는 여전히 수치·수치·수치다. ↩

4. 프랙탈 차원 $91/48$ 을 처음 보면 “왜 하필”이라는 반응이 나오는데, 이건 2D 임계 퍼콜레이션이 공형 불변(conformally invariant)이라는 사실에서 슈람-뢰브너 전개(SLE$_6$)로 유도된다. 이 업적으로 베르너가 2006년 필즈상을 받았다. 동전 던지기가 필즈상이 됐다. ↩

5. 라벨 병합을 게을리하면(경로 압축 없이) union-find가 $O(\log N)$ 으로 느려지는데, 128×80 정도에서는 체감이 안 된다. 반면 $4096^2$ 격자에서는 그 로그가 실제로 커피 한 잔 값이다. ↩