Graph-tool 논문6

Sylen·2025년 1월 4일

아래 내용은 1973년 Biometrika에 실린 Peter Clifford와 Aidan Sudbury의 논문
"A Model for Spatial Conflict"(Biometrika, Vol. 60, No. 3, 1973, pp. 581-588) 내용을 바탕으로,
1) 모델 개념과 수식, 2) 공간에서의 경쟁(“침투”와 “교환/스왑” 프로세스), 3) 주요 결과와 차원(d=1,2 vs. d≥3) 간의 차이,
4) 생물학적·물리학적 함의**를 최대한 자세히 풀어써 보겠습니다.

1. 연구 배경 및 동기

두 종(species)의 공간적 경쟁(spatial conflict): 공간 상에서 각 종(예: 흑/백 세포)이 서로 접하는 경계(frontier)에서, 한 종이 다른 종의 영역을 침투하거나 또는 서로 교환(swap)하는 과정을 생각.
본 논문은 이웃하는 두 종이 “상호 침투”를 통해 상대방의 점유지를 뺏는(invasion) 모델을 세운다. (만약 역으로 교환(swap)만 일어난다면 어떤 행동이 되는지도 비교.)
구체적으로 격자점(lattice) 위에 흑/백으로 표시된 세포(cell)가 있고, 특정 규칙(확률적 전이)으로 시간이 지남에 따라 흑/백 배치가 변화한다.
이때, 단일 지점(territory)이나 여러 지점이 특정 시점에 어느 종에 의해 점유될 확률을 구하고, 장기적으로(time→∞) 어떤 패턴이 형성되는지(혼합 vs. 전체 한 종화 vs. 지역구분) 등을 해석하려 한다.

핵심:

1차원(선형 격자), 2차원(평면 격자), 3차원(입방 격자) 등에서 모델이 달리 동작하는지,
“침투(invasion) 모델”과 “교환(swapping) 모델”이 확률적으로 어떤 상관관계를 갖는지,
1,2차원에서는 결국 “큰 덩어리”를 한 종이 장악하게 되는(또는 특정 조합으로 정렬) 현상이 발생하지만, 3차원 이상에서는 서로 뒤섞인 상태가 남게 되는지를 밝힌다.

2. 주요 모델 개념: “스왑(swapping)” vs. “침투(invasion)”

2.1. 스왑(Swapping) 프로세스

격자(1D,2D,...)에서 인접한 흑(Black)·백(White) 세포가 “서로의 위치를 교환(swap)”하는 과정을 확률적으로 진행.
표현:
- 1차원 예시: 정수 좌표에 흑/백 세포가 있고, 인접(i, i+1) 좌표에서 하나는 흑, 다른 하나는 백이면, 작은 시간 (\delta t) 동안 교환이 발생할 확률이 (r (\delta t)) 정도로 설정(단위율).
- 2차원/고차원 격자라면, “이웃”의 정의가 조금 다를 뿐(4-방향(2D) 또는 6-방향(3D) 등).
동등 표현(“무작위 점” 해석)
이들은 “시간–공간(또는 그래프의 간선 × 시간) 상에 난수 포인트를 뿌린 후, 이 점에 의해 교환 이벤트가 일어난다”라는 식으로도 볼 수 있다.
- 이때, 세포 색깔은 본질적으로 바뀌지 않고, 위치만 교환되므로, 특정 시간 t에 격자의 한 점 x를 점유하는 세포가 원래 어느 초기위치에서 출발했는지는 연속시간 랜덤 워크를 추적하면 된다는 것이다.
결론: Lemma 1과 Theorem 1
1) “서로 다른 초기 위치에서 출발한 세포가, 스왑 과정을 통해 t 시점에 (x,y,...) 위치로 올 확률은, (x,y,...)에서 역추적하는 연속시간 대칭 랜덤 워크(continuous-time symmetric random walk)에 의해 그 초기 위치를 방문했을 확률과 동일.”
2) 특히, 특정 “블록/구역 A”가 전부 흑이었다면, 시점 t에서 점 x가 흑일 확률은, “x에서 시작해 시간을 거슬러간 랜덤워크가 A 중 일부 점에 도달할(혹은 A와 연결) 확률”과 같다는 식.

2.2. 침투(Invasion) 프로세스

이웃한 흑/백 한 쌍(b,w)이 만나면, 그중 한 쪽이 다른 쪽을 침투하여, 두 칸이 모두 (흑,흑) 또는 (백,백)이 된다.
본 논문은 “공정(fair)한 경쟁” 전제로, b–w가 만났을 때 b->w가 될 수도, w->b가 될 수도, 각각 동일(단위 Poisson율)이라 가정.
결정적 차이: 스왑은 (b,w)->(w,b) 형태의 자리바꿈, 침투는 (b,w)->(b,b) or (w,w).
(역추적) 해석: 그래프의 간선 × 시간 공간에 무작위점(밀도=2 등)을 뿌리고, 점이 “간선 중간보다 어느 쪽에 가깝냐”에 따라 침투가 발생.
하지만 “침투”에서도, 개별 위치에 대한 ‘시점 t에서 색깔이 흑일 확률’은 “스왑” 케이스와 같음 (Theorem 2), 왜냐하면 근본적으로 단일 지점만 보면, (침투 vs. 스왑) 모두 “역추적 랜덤워크”의 분포가 같기 때문.
- 침투 경우, 한 시점에 “이웃한 두 점이 하나로 합쳐진다(한 세포의 조상ancestor를 공유하게 된다)”는 의미가 있지만, 단일 지점 색깔 확률에는 큰 차이가 없다.

3. 다수 지점(“joint colouring”)에서의 확률

3.1. 침투 프로세스 (1D,2D)

침투에서, “한 영역이 하나의 색으로 모두 뒤덮이는” 현상:
- 1,2차원에서는 임의의 유한 집합(지점들의 집합)이 모두 같은 색깔이 될 확률이 시점이 커질수록 1에 수렴한다(Theorem 3).
- 직관: “1D,2D에서 랜덤워크는 거의 확실히 서로 만나므로(재방문 확률=1), 결국 같은 조상(ancestor)을 공유하기 때문.”
- 즉, 1차원이나 2차원 격자에서는 침투 과정이 오래되면, 임의로 작은 지점들을 보면 전부 같은 종(흑 또는 백)일 확률이 거의 1. => 큰 “제국(Empire)”이 형성된다.
하지만, 전체적으로 한 종이 전부 점령하는(글로벌 승리) 현상은 아니다:
- 예) “왼쪽은 전부 흑, 오른쪽은 전부 백”이 처음이었다 하면, 무한 원거리 한쪽은 영원히 백을 유지할 수도 있고, 그 반대편도 흑을 유지.
- 게다가 특정 점이 “결국 백이 될 확률도 1, 결국 흑이 될 확률도 1”이라는 식으로 모호… (결국 외곽에서 흑이 침투 가능성도 살아있고, 반대로 백이 재침투 가능성도 있음).

3.2. 침투 프로세스 (3D 이상)

3차원(또는 그 이상)에서는 두 랜덤워크가 서로 만날 확률이 1이 아님(3D 이상에서는 단순대칭랜덤워크가 무한 시간에도 만나지 않을 확률 양의 값).
따라서 3차원 이상에서는, 인접 두 지점이 결국 같아질(=조상 통합) 확률 < 1.
- 논문 예시로 3D에서 (1,0,0) 차이인 두 점이 같아질 확률이 ~0.34 라고 언급(Spitzer 1964 결과).
- 그 결과: 3D에서 “유한 지점이 전부 같은 색이 될 확률”이 1로 가는 일은 없다. 즉, 큰 제국이 확실히 형성되는 일은 없어지고, 어느 정도 섞인 구역이 유지된다.

4. 스왑(swapping) 프로세스: 다수 지점에서의 결과

스왑에서는 “각 지점별 흑 확률”만 보면 침투와 같았으나, 여러 지점을 동시에 볼 때는 전혀 다른 상관구조가 나타난다.
스왑은 사실 가역(time-reversible) 프로세스이고, 총 흑 수, 백 수는 보존(정확히 말하면 각 개별 세포는 안 변하고 위치만 바뀐다).
- 실제로 장시간 후에는 보다 ‘무질서(entropy↑)’ 상태로 보이기 쉬움.
구체적 정리(Theorem 4): “스왑”의 경우, 1차원이든 2차원이든 d차원이든, 만약 처음에 특정 큰 스케일 독립 구역(예: 한 반구는 흑)이라면, 시간이 커질수록 임의의 유한 지점에서의 색 분포가 독립(independent)에 가까워진다(즉, 상호 의존성이 사라지고, 완전한 랜덤 혼합 패턴으로 감).
- 결론: 스왑은 시간이 지날수록 “서서히 랜덤화되어, 국소부에서의 색상들이 독립에 가까워지는” 경향.

5. “Alternation(교대)” 프로세스

앞서 말한 “침투”는 (b,w)->(b,b) or (w,w)이었음.
만약 반대로, 인접 흑/흑 혹은 백/백이 만나면 “(b,b)->(b,w) or (w,b)”로 바뀌는 과정을 생각해볼 수 있음. => 서로 다른 색이 이웃하는 편이 이득인 생태, 예: 식물 뿌리가 옆에 같은 종이 있으면 서로 자원 경쟁, 차라리 다른 종이 인접이 유리.
논문에선 이를 “alternation process”라 부름. 인접 동일색이면 교대(=한쪽 바뀜)하며, (b,b)->(b,w) or (w,b).
이것도 “침투”와 밀접한 연관
- 1D 예: (정수 좌표 중 짝수 위치는 색 유지, 홀수 위치는 반대색) 식으로 초기조건을 변환해보면, alternation이 사실상 invasion 형태로 해석 가능하다. => 이로부터 (1D,2D)에서의 alternation도 결국 “장기적으로 인접 위치들이 서로 다른 색이 될 확률→1”, 즉 (b,w,b,w,...)로 전부 교대로 정렬되는 현상 발생(Theorem 6).
- 3D에서는 전부 교대되는 패턴이 확률 1로 형성되진 않고, 인접 색이 다른 확률이 어느 상수(약 0.67)로 수렴.

6. 결론 및 시사점

1D,2D vs. 3D 차이
- 1D와 2D에선, (침투 모델) 시간이 오래 지나면 유한 구역을 보면 거의 같은 색으로 점령됨 => 일종의 제국(모든 점이 동일 조상을 가진다).
- 3D 이상에선, 랜덤워크가 만날 확률<1이므로, 점령이 완전히 통합되지 않고, 섞임이 어느 정도 남는다.
  - 침투일 때 인접 둘이 같아질 확률 ~ 0.67, 반대로 alternation 모델은 인접 둘이 달라질 확률 0.67.
생태·물리 해석
- “침투”는 “공격적 경쟁 종” 개념: 시간이 갈수록 국소적으로 한 종이 다 먹는 식(1D,2D에선 큰 덩어리).
- “스왑”은 보존적·가역적인 현상: 시간이 지날수록 무질서가 증가(열역학적 관점).
- “교대(alternation)”는 서로 다른 종이 이웃하는 것이 유리(반자기체계·반교대성), 1D/2D에서는 장기적으로 거의 (b,w,b,w,...) 식 패턴으로 고착.
초기조건에 따른 유한 시점의 확률 계산
- 논문에서는 (b,w) 쌍만 본다면, 두 점이 시간이 t일 때 모두 b(또는 w)일 확률 등을, 랜덤워크 충돌 관점에서 유도 가능.
- 실험적으로, “종 간 경계선이 얼마나 들어갔나” 혹은 “인접 둘 중 몇 %가 동일/다름?” 을 관찰해서 시계추정 가능성도 언급.
생물학 vs 물리학 차이
- 물리학적 ‘엔트로피 증가’(무질서 증가)와 달리, 생물학적 침투는 한 종이 질서를 형성(=영역 확대)하는 형태.
- 본 모델에서 “침투 vs. 교환”은 그 예시를 수학적 확률모델로 제시.

부록: 간단 정리

침투(Invasion) 모델:
- 인접(b,w) -> (b,b) 또는 (w,w), 균등 확률.
- 1D,2D: 유한 구역은 장기적으로 단일 종이 장악(확률=1).
- 3D: 인접 같아질 확률 ~ 0.67, 섞임이 남음.
스왑(Swapping) 모델:
- 인접(b,w) -> (w,b).
- 각 지점별 흑색 확률은 침투 모델과 동일하나, 다수 지점의 상관구조 다름.
- 시간이 갈수록 전반적으로 랜덤화.
교대(Alternation) 모델:
- 인접(b,b) -> (b,w) 또는 (w,b).
- 1D,2D: 장기적으로 인접이 모두 서로 다른 색으로 정렬(확률=1).
- 3D: 교대 완전 정렬 안 됨, 인접 다를 확률 ~ 0.67.

이상으로, Clifford & Sudbury (1973) 논문의 주요 개념과 결과를 요약했습니다. 이 논문은 “공간적으로 분포된 생물 종(혹은 물리적 스핀)들이 서로 경쟁하는 경우, 단일 지점·다중 지점에서의 색 분포를 어떻게 확률적으로 추정하고, 장기 패턴이 어떻게 달라지는지”를 처음으로 체계적으로 제시했다는 의의가 큽니다. 특히 1,2차원 vs. 3차원 이상의 결정적 차이(랜덤워크 만남 확률)와, 침투 vs. 교환 vs. 교대 프로세스의 비교가 핵심 포인트입니다.