defwin's profile image

defwin

December 31, 2025 00:00

0. Introduction

상전이(phase transition)는 물리학에서 나온 개념으로, 어떤 임계점을 기준으로 양쪽에서 행동이 달라지는 것을 말합니다. 물리학을 공부하는 경우 이러한 현상을 학습하게 되는데요, 대표적인 예시로 2차원 이징 모델이나 란다우 긴즈버그 모델 등이 있습니다. 놀랍게도 어떤 랜덤하게 구성한 네트워크들에 대해서도 이와 비슷한 상전이 현상이 일어남이 알려져 있습니다. 본 글에서는 그 중에서도 가장 간단한 모델인 Erdős–Rényi 모델에서 일어나는 상전이에 대해 공부해보려 합니다.

본 글은 KIAS-SNU Physics Winter Camp 2025 중 고등과학원 계산과학부 이덕선 교수님의 “Phase Transitions in Networks” 강의 및 group project 참여 중 공부한 내용을 바탕으로 함을 알립니다.

1. Erdős–Rényi Model

Erdős–Rényi 모델(ER 모델)은 가능한 모든 가능한 엣지가 동등한 확률 $p$로 연결되어있는 네트워크를 의미합니다. 사실 이 모델에는 엣지 수를 고정하는 $G(n,m)$ 모델과 확률을 고정하는 $G(n,p)$ 모델 두 종류가 있는데, 엣지 수를 고정하면 수학적으로 어려워져 $G(n,p)$ 모델을 주로 고려합니다. 가장 간단하게 생각할 수 있는 랜덤 네트워크로, 수학적으로 다루기가 편하다는 장점이 있습니다.

여기서 “확률”이라는 요소가 굉장히 이상하게 느껴질 수 있는데요, 이를 이해하기 위해서는 통계물리학에서 중요한 개념인 앙상블(Ensemble)에 대한 간략한 이해가 필요합니다. 실제 네트워크에서는 두 노드가 연결되어 있거나 연결되어있지 않은 두 상태만 가능하지만, 만약 같은 “규칙”으로 생성된 무수히 많은 네트워크들을 고려한다면 그 중에 특정 두 노드가 연결되어있는 비율로 확률을 정의할 수 있게 됩니다. 이와 같이 같은 “규칙”으로 생성된 무수히 많은 동일한 복제들을 앙상블이라고 부릅니다. 앞으로의 논의에서는 대부분 이 앙상블의 개념을 포함하고 있다고 생각할 것입니다.

여담으로 통계물리학에서는 앙상블을 같은 macroscopic한 상태를 가진 복제로 이해하고, 앙상블 평균과 시간 평균이 평형상태에서 동일한 시스템을 ergodic하다고 합니다. 이는 곧 상태의 등분배로 이어져, 평형통계물리의 가장 근본적인 가정으로도 볼 수 있습니다.

그럼 본격적으로 ER 모델의 상전이를 공부하기 전에, ER 그래프의 몇 가지 특징을 알아봅시다. 먼저 각 노드의 차수 $k$의 분포에 대해 살펴봅시다. 평균은 쉽게 알 수 있습니다. 이를 $c$라 하겠습니다.

\[\langle k \rangle = (n-1)p = c\]

이제 차수가 $k$인 노드의 비율, 즉 임의의 노드를 골랐을 때 이 노드의 차수가 $k$일 확률을 $p_k$라고 합시다. 전체 노드 수를 $n$이라 할 때 $p_k$는 다음과 같습니다.

\[p_k={n-1 \choose k} p^k (1-p)^{n-k-1}\]

통계적으로 네트워크를 분석하려는 이유는, 보통 $n$이 큰 경우 정량적으로 네트워크의 성질을 알기 어렵기 때문입니다. 때문에 관심 있는 차수 $k$보다 $n$이 매우 크다는 근사를 할 것입니다. 이를 적용하면

\[(1-p)^{n-1-k} = (1-\frac{c}{n-1})^{n-1-k} \approx e^{-c}\] \[{n-1 \choose k} = \frac{(n-1)!}{k!(n-1-k)!} \approx \frac{(n-1)^k}{k!}\]

즉 $p_k$는 다음과 유사해집니다.

\[p_k=\frac{(n-1)^k}{k!}p^ke^{-c} = \frac{c^k}{k!}e^{-c}\]

이는 정확히 평균이 $c$인 푸아송 분포입니다. 즉 ER 모델은 $n$이 큰 극한에서 차수 분포가 푸아송 분포를 따름을 알 수 있습니다.

ER 모델에는 몇 가지 문제점이 있는데요, 이를 간단하게 짚고 넘어가려고 합니다. 먼저 실재하는 네트워크들, 가령 친구 관계나 인터넷 페이지 연결 등은 차수 분포가 푸아송 분포를 따르지 않습니다. 실제 네트워크들은 많은 경우 큰 차수에서 $k^{-\gamma}$ 꼴의 멱분포를 따르는 분포와 유사함이 알려져 있습니다. 이외에도 노드의 두 이웃이 이웃일 확률인 클러스터링 계수가 $c/(n-1)$로 쉽게 계산되는데, 이 값이 0으로 수렴한다는 문제가 있습니다. 실제 세계에서는 보통 두 친구가 서로 친구일 확률이 0이 아니기 때문에, 이 또한 실제 네트워크들과 맞지 않는 부분들이라고 볼 수 있습니다. 그럼에도 불구하고 ER 모델에서 앞으로 살펴볼 상전이라는 현상을 매우 쉽게 볼 수 있기 때문에 중요한 토이모델로 생각할 수 있습니다.

2. Giant Connected Components and Phase Transitions

네트워크의 상전이에 대해 공부해보겠다고 하고, 아직까지 이 상전이가 무엇을 의미하는지 한 번도 이야기하지 않았습니다. 이에 대해 본격적으로 이야기하고, 상전이를 직접적으로 들여다봅시다.

2.1. Formation of Giant Connect Components

거대 연결 요소(Giant Connected Component, GCC)를 정의하겠습니다. 네트워크에서 가장 큰 연결 요소를 생각해봅시다. 저희는 네트워크 노드의 개수와 무관한 성질을 보고 싶기 때문에 이 연결 요소의 크기를 $S$라 할 때 $n$이 매우 큰 극한에서 이 연결요소에 속한 노드의 비율 $m=\left\langle\frac{S}{n}\right\rangle$이 0보다 큰지 궁금합니다. 0보다 큰 경우, 즉 전체 노드 수에 비례하는 연결 요소가 존재할 때 그 연결 요소를 GCC로 정의합니다. GCC의 크기가 평균 차수 $c$에 따라 어떻게 변하는지 확인해봅시다.

번외로, 이 GCC의 비율을 $m$으로 표기하는 것이 통상적인 엣지 개수 표현과 겹쳐 불편하게 느껴질 수 있습니다만, 이 비율을 $m$으로 표기하는 것에는 이유가 있습니다. 이징 모델의 변형인 Potts 모델에서 특정한 극한을 취하면 이 ER 모델과 동등해지는데, 이 모델에서의 자성에 해당하는 양이 정확히 GCC의 비율과 일치하게 되기 때문입니다.

이제 직접 GCC의 크기를 구해봅시다. 여러 유도 방법이 있을 수 있지만, 여기서는 GCC에 속하지 않는 노드의 연결성을 이용하여 GCC에 속하지 않을 확률의 재귀성을 이용할 것입니다. $u=1-m$을 GCC에 속하지 않은 노드의 비율, 즉 임의의 노드를 골랐을 때 GCC에 속하지 않을 확률이라 합시다. 이 노드가 GCC에 속하지 않으려면, 다른 임의의 노드들과의 관계를 하나씩 볼 때, 그 노드와 연결되어있지 않거나(확률 $(1-p)$) 그 노드와 연결되어있지만 그 노드가 GCC에 연결되어있으면 안 됩니다(확률 $pu$). 그리고 이를 종합한 확률이 정확히 $u$가 되어야 합니다. 식으로 표현하면

\[(1-p+pu)^{n-1}=\left[1-\frac{c}{n-1}(1-u)\right]^{n-1}=u\]

위에서처럼 다시 $n$을 키우는 극한을 생각해보면 다음과 같이 됩니다.

\[u=e^{-c(1-u)}\]

$m=1-u$임을 기억하면 다음과 같이 식을 바꿀 수 있습니다.

\[m=1-e^{-cm}\]

이 방정식은 $c<1$에서 $m=0$인 해만 가지고, $c>1$이면 $m=0$이 아닌 해를 하나 더 가집니다. 그리고 이 것이 실제 해가 됨을 이해할 수 있습니다만, 일단은 뒤로 미루고 생각하겠습니다. 이렇게 평균 차수 $c$에 대해 GCC의 크기를 보면, $c=1$을 기준으로 양단에서 행동이 급격하게 달라짐을 확인할 수 있습니다. $c$가 1보다 작을 때는 GCC가 없다가, 1을 초과하기 시작할 때 GCC가 형성됩니다. 즉, 네트워크에서의 상전이 현상을 발견한 것입니다!

2.2. Understanding the Critical Point

이 $c=1$ 임계조건을 다른 방식으로 이해해 봅시다. 논의는 ER 모델이 아닌 임의의 모델에서 차수 분포 $p_k$만 주어져 있다면 적용할 수 있는 논의입니다.

어떤 노드의 2번째 이웃의 기댓값을 구해봅시다. 먼저, 임계점 근처에서는 노드들이 강하게 연결되기 전이므로, 대부분의 그래프가 트리 형태임을 기대할 수 있습니다. 이를 가정하고 생각합시다. 노드를 하나 고정하고, 그 노드에 연결된 노드의 차수가 $k$일 확률은 $kp_k$에 비례함을 알 수 있습니다. 차수가 $k$라면 그 노드의 엣지가 $k$개이므로 $k$에 비례하게 됩니다. 정규화를 하면 확률은 $kp_k/\langle k \rangle$이 됩니다. 다만 여기서는 원래 노드를 제외한 차수를 세야 하므로 2번째 이웃 수의 확률분포는 $(k+1)p_{k+1}/\langle k \rangle$가 됩니다. 이를 활용하여 2번째 이웃 숫자의 평균을 구해보면

\[\sum_k k \cdot \frac{(k+1)p_{k+1}}{\langle k \rangle} = \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle} = \frac{c_2}{c_1}\]

여기서 $c_2=\langle k^2 \rangle - \langle k \rangle$는 전체 2번째 이웃 수의 평균으로 생각할 수 있고, $c_1=\langle k \rangle$는 첫 번째 이웃 수의 평균입니다. 이 논의를 일반화하면, $d$번째 이웃의 수 $c_d=(c_2/c_1)^{d-1} \cdot c_1$임을 알 수 있습니다.

만약 $c_2/c_1$이 1보다 작다면, 임의의 노드로부터 시작한 연결요소의 크기는 $n$과 무관하게 수렴할 것으로 기대할 수 있습니다. 즉, GCC가 형성되지 않을 것입니다. 따라서 GCC가 형성되기 위해서는 $c_2/c_1>1 \Leftrightarrow \langle k^2 \rangle > 2\langle k \rangle$ 이어야 합니다. 정성적인 설명으로는, 두 번째 이웃 수의 기댓값이 첫 번때 이웃 수의 기댓값보다 커야 $n$에 비례하는만큼 컴포넌트가 커질 수 있어야 함으로 이해할 수 있습니다.

ER 모델에서 $p_k$가 푸아송 분포를 따름을 알고 있으므로, $c_1=\langle k \rangle = c$이고, $c_2 = \langle k^2 - k \rangle = \langle k \rangle^2$로, $c_1/c_2 = \langle k \rangle = c$입니다. 이를 통해 임계점이 $c=1$임을 알 수 있고, 이는 위에서 구한 결과와 정확히 일치합니다.

2.3. 2nd GCC is Unlikely to Exist

3. Small Components

작은 컴포넌트들의 크기는 임계점 근처에서 어떻게 변하는지 살펴봅시다. 어떤 차수가 $k$이고 GCC에 속하지 않은 노드가 연결된 연결 요소의 크기를 $s$라 합시다. 이전에도 언급했듯이 임계점 근처에서 이 노드가 연결된 연결요소를 트리로 가정할 수 있습니다. 노드 하나를 제거한다면 서브트리들이 생기고, 각각의 크기를 $t_1,\cdots t_k$라 합시다. 이 때 $s$의 평균을 내보면

\[\langle s \rangle _k = 1 + \sum_{i=1}^k \langle t_i \rangle = 1 + k \langle t \rangle\]

여기서 $\langle s \rangle _k$의 의미는 차수가 $k$인 경우에 대해서만 평균을 냈다는 의미이고, $\langle t \rangle$은 한 노드와 연결된 서브트리의 평균 크기를 의미합니다. 이제 다시 $k$에 대해 $\langle s \rangle _k$를 평균내면 다음과 같이 됩니다.

\[\langle s \rangle = 1 + \langle k \rangle _{\text{small}} \langle t \rangle\]

$\langle k \rangle _{\text{small}}$은 GCC에 속하지 않은 노드에 대한 차수 평균입니다.

이제 $\langle k \rangle _{\text{small}}$과 $\langle t \rangle$에 대해 살펴봅시다. 어떤 노드가 GCC에 속하지 않은 경우 이웃의 노드들이 모두 GCC에 속하지 않아야 합니다. 그리고 GCC에 속하지 않는 노드의 개수는 $(1-m)n$입니다. 따라서 $\langle k \rangle _{\text{small}}$는 다음과 같이 구할 수 있습니다.

\[\langle k \rangle _{\text{small}} = [(1-m)n-1]p \approx (1-m)c\]

그리고 ER 모델에서는 모든 노드가 동등하기 때문에, $\langle t \rangle = \langle s \rangle$로 생각할 수 있습니다. 모든 것을 종합하면 다음을 얻습니다.

\[\langle s \rangle = \frac{1}{1 - c + cm}\]

$m$이 $c=1$에서 $0$임을 기억하면, 이 식은 $c=1$에서 발산함을 알 수 있습니다. 즉, $\langle s \rangle$은 $c=1$에서 발산하며, 이 임계점을 기준으로 $\langle s \rangle$의 행동 또한 바뀜을 알 수 있습니다. 이를 통해 상전이 현상을 다른 측면에서도 확인할 수 있습니다.

여담으로 자성을 설명하는 다른 모델들에서도 이와 비슷한 물리량이 있는데요, 바로 자화율입니다.

4. Outro

본 글에서는 노드가 연결될 확률이 동일하게 주어진 ER 모델 네트워크에 대해 거대 연결 요소(GCC)의 생성에 대한 상전이 현상을 살펴보았습니다. 재귀적인 논의를 통해 GCC의 크기를 직접 구하며 임계점을 살펴보았고, 보다 일반적으로 차수 분포가 주어진 경우에서의 논의를 통해 임계점을 교차검증하였습니다.

다만 본 글에서 다룬 논의만으로는 임의의 차수 분포가 주어졌을 때 GCC의 구체적인 크기는 구할 수 없습니다. 때문에 임의의 차수 분포에 대해 GCC 크기를 구하는 것은 다른 방법을 활용하는 것이 좋고, 다음 글에서 이에 대해 구체적으로 다룰 예정입니다. 간략하게 미리 언급하자면, 차수 분포와 2번째 이웃 분포로 생성된 생성함수를 이용하여 계산하고 싶은 대부분의 양들을 계산해낼 수 있게 됩니다.

또 본 글에서는 GCC가 하나임을 가정하고 논리를 전개하였는데요, 자연스럽게 GCC가 두 개 이상일 수도 있지 않을까 생각이 들 수 있습니다. 답을 말씀드리자면 이렇게 될 확률은 매우 작음을 보일 수 있습니다만, 큰 흐름에서는 중요하지 않다고 생각하여 구체적인 계산은 생략하였습니다.

References

KIAS-SNU Physics Winter Camp 2025 - Phase Transitions in Networks

M. Newman, Networks, (Oxford university press, 2018)