무작위 그래프

1. 개요[편집]

무작위 그래프 Random graph
표준 모형	$G(n,p)$ (길버트) · $G(n,M)$ (에르되시-레니)
차수 분포	이항 $\mathrm{Bin}(n-1,p)$ → 푸아송 $\mathrm{Poi}(c)$
거대 성분 출현	평균 차수 $c = np = 1$
연결성 문턱	$p = \ln n / n$
임계창	$p = (1 + \lambda n^{-1/3})/n$, 최대 성분 $\Theta(n^{2/3})$
지름	$\approx \ln n / \ln c$ (거대 성분 안)
실제 망과의 차이	군집 계수 $\to 0$, 꼬리 없음

무작위 그래프(random graph)는 간선의 존재 여부를 확률 규칙에 따라 정한 그래프, 또는 그런 그래프들 위의 확률분포다. 하나의 그래프가 아니라 앙상블이라는 점이 핵심이며, 그래서 묻는 질문도 “이 그래프가 연결돼 있나”가 아니라 ”$n \to \infty$ 에서 연결돼 있을 확률이 얼마인가”가 된다.

이 대상이 통계물리와 알고리즘 양쪽에서 사랑받는 이유는 두 가지다. 첫째, 거의 모든 흥미로운 성질이 문턱을 갖는다. 간선 밀도를 서서히 올리면 성질 A 가 거의 확실히 없던 상태에서 거의 확실히 있는 상태로 좁은 구간 안에서 넘어간다. 이게 상전이와 문자 그대로 같은 현상이라, 조합론과 통계역학이 같은 언어로 말하는 몇 안 되는 무대가 된다. 둘째, 널 모형(null model)으로서의 쓸모다. “실제 데이터에서 관측한 이 구조가 우연히 나올 법한가”를 판정하려면 우연의 기준선이 필요하고, 그 기준선을 제공하는 것이 무작위 그래프다.

2. 두 모형[편집]

• $G(n,M)$ — 정점 $n$ 개짜리 그래프 중 간선이 정확히 $M$ 개인 것을 균등하게 하나 고른다. 에르되시와 레니가 1959년에 쓴 것이 이쪽이다.
• $G(n,p)$ — 가능한 $\binom{n}{2}$ 개의 정점 쌍 각각을 독립적으로 확률 $p$ 로 연결한다. 같은 해에 길버트가 제안했다.

관례상 둘 다 “에르되시-레니 모형”이라 부르지만 원 논문 기준으로는 $G(n,p)$ 는 길버트 몫이다.¹ $M \approx p\binom{n}{2}$ 로 두면 두 모형은 대부분의 단조 성질에 대해 사실상 같은 답을 준다. 계산과 증명이 훨씬 쉬운 쪽은 독립성이 있는 $G(n,p)$ 이고, 그래서 이론이든 코드든 기본값은 $G(n,p)$ 다.

관심 있는 영역은 대개 평균 차수를 상수로 유지하는 스케일링이다.

$$p = \frac{c}{n}, \qquad \mathbb{E}[\deg v] = (n-1)p \to c$$

이 스케일링에서 그래프는 희소하다 — 간선 수가 $\Theta(n)$ 이라 희소행렬로 다뤄야 하는 그 영역이다.

3. 거대 성분의 출현[편집]

에르되시-레니 이론의 대표 결과이자, 이 주제가 물리와 만나는 지점이다. $p = c/n$ 에서 최대 연결 성분의 크기가 $c = 1$ 을 경계로 질적으로 달라진다.

• $c < 1$ (아임계) — 최대 성분 크기 $O(\ln n)$. 그래프는 작은 조각들로 산산이 흩어져 있다.
• $c = 1$ (임계) — 최대 성분 크기 $\Theta(n^{2/3})$.
• $c > 1$ (초임계) — 크기 $\theta n$ 인 유일한 거대 성분이 하나 존재하고, 나머지 성분은 전부 $O(\ln n)$ 이다. 여기서 $\theta$ 는

$$\theta \;=\; 1 - e^{-c\theta}$$

의 유일한 양의 해다.

직관은 분기 과정이다. 아무 정점에서 출발해 이웃을 훑어 나가면(=너비 우선 탐색), 매 단계 새로 발견되는 정점 수가 근사적으로 평균 $c$ 인 푸아송 분포를 따른다. 자손 수 평균이 1 을 넘는 분기 과정만이 양의 확률로 영원히 살아남고, 그 생존 확률이 정확히 위 식의 $\theta$ 다. “평균 자식 수 1”이라는 문턱이 곧 거대 성분의 문턱인 것이다. 위 방정식은 $c \le 1$ 이면 $\theta = 0$ 만을, $c > 1$ 이면 양의 해를 갖는데, 이는 상전이 문서의 란다우식 자기무모순 방정식과 형태가 똑같고 임계 지수도 평균장 값($\theta \sim 2(c-1)$, 즉 $\beta = 1$)이 나온다.

전이가 일어나는 폭까지 정밀하게 알려져 있다. $p = (1+\lambda n^{-1/3})/n$ 으로 두면 $\lambda$ 를 상수로 잡은 구간에서 최대 성분들이 $n^{2/3}$ 스케일로 요동치며, 이 폭 $n^{-1/3}$ 짜리 임계창은 유한 크기 스케일링 이론이 예측하는 것과 정확히 대응한다.²

4. 연결성 문턱[편집]

거대 성분이 생겼다고 그래프가 연결된 것은 아니다. $c > 1$ 이어도 고립 정점이 상수 비율로 남아 있다. 전체가 하나로 이어지려면 훨씬 촘촘해야 한다.

$$p \;=\; \frac{\ln n + c_0}{n} \quad\Longrightarrow\quad \Pr[\text{연결}] \to e^{-e^{-c_0}}$$

즉 문턱은 $p_c = \ln n / n$ 이다. $\ln n$ 이 튀어나오는 이유는 소박하다. 연결성을 막는 마지막 장애물이 고립 정점이기 때문이다. 정점 하나가 고립될 확률은 $(1-p)^{n-1} \approx e^{-np}$ 이므로 고립 정점의 기대 개수는 $n e^{-np}$ 이고, 이것이 $\Theta(1)$ 이 되는 지점이 $np = \ln n$ 이다. 위 극한 분포가 이중지수(굼벨) 꼴인 것도 고립 정점 개수가 푸아송으로 수렴하기 때문이다. 쿠폰 수집가 문제에서 $\ln n$ 이 나오는 것과 같은 종류의 계산이다.

문턱이 두 개 — $1/n$ 과 $\ln n/n$ — 라는 것은 실무적으로 중요하다. 무작위로 뿌린 통신망·센서망은 “대부분이 이어지는” 밀도와 “전부가 이어지는” 밀도 사이에 $\ln n$ 배의 간격이 있다. 마지막 한 노드까지 붙이는 비용이 나머지 전부를 붙이는 비용보다 크다는 이야기이고, 그래서 실제 설계는 대개 완전 연결을 포기하고 거대 성분만 노린다.

5. 차수 분포와 실제 망의 배신[편집]

$G(n,p)$ 의 차수는 이항분포 $\mathrm{Bin}(n-1,p)$ 이고, $p = c/n$ 에서 푸아송 $\mathrm{Poi}(c)$ 로 수렴한다. 푸아송 분포의 꼬리는 지수보다도 빠르게 죽으므로 평균보다 훨씬 큰 차수를 가진 정점은 사실상 존재하지 않는다. 평균 차수가 6 인 무작위 그래프에서 차수 600 짜리 정점이 나올 확률은 0 이라고 봐도 무방하다.

문제는 현실이 그렇지 않다는 것이다.

성질	$G(n,p)$, $p=c/n$	실제 망(웹·인용·단백질 상호작용)
차수 분포	푸아송, 꼬리 없음	두꺼운 꼬리, 종종 근사적 멱법칙
군집 계수	$p = c/n \to 0$	상수 수준으로 큼
평균 거리	$\approx \ln n / \ln c$	비슷하게 짧음
차수 상관	없음	있음(동류·이류 혼합)

짧은 거리 하나만 맞고 나머지는 다 틀린다. 특히 군집 계수 — 내 이웃 둘이 서로 이웃일 확률 — 가 $G(n,p)$ 에서는 $p$ 그 자체라 $n$ 이 커지면 0 으로 죽는데, 사회망에서는 “친구의 친구는 친구”라는 이유로 상수 수준을 유지한다. 무작위 그래프가 국소 구조가 없는 모형이라는 것이 이 실패의 근원이다.

그래서 나온 후속 모형들이 각각 하나씩을 고친다.

• 작은 세상 네트워크(와츠-스트로가츠, 1998) — 고리 격자에서 출발해 간선을 확률 $q$ 로 무작위 재배선한다. $q$ 가 아주 작아도 평균 거리는 급격히 $\ln n$ 스케일로 떨어지는데 군집 계수는 격자 값 근처에 남는다. “높은 군집 + 짧은 거리”를 동시에 내는 최소한의 장치.
• 무척도 네트워크와 바라바시-알베르트 모형(1999) — 정점을 하나씩 추가하며 기존 정점에 차수에 비례하는 확률로 붙인다(선호적 연결). 성장 + 선호적 연결이 함께 있으면 차수 분포가 지수 3 의 멱법칙으로 수렴한다. 아이디어 자체는 율(1925)과 프라이스(1976)의 누적 이득 모형이 먼저였고, BA 가 한 일은 그것을 네트워크 언어로 재발견하고 대중화한 것이다. 실제 망의 꼬리가 정말 멱법칙인지는 통계적으로 여전히 논쟁 중이라는 점도 함께 기억해 둘 만하다.
• 구성 모형(configuration model) — 차수열 $\{k_i\}$ 를 먼저 지정하고 그 차수를 가진 그래프를 균등하게 뽑는다. 정점마다 반쪽 간선(stub)을 $k_i$ 개 달고 무작위로 짝지으면 된다. 차수 분포를 원하는 대로 넣으면서 그 외에는 최대한 무작위이므로, **“차수만 보존한 널 모형”**으로 가장 널리 쓰인다. 거대 성분 조건도 깔끔하다 — 멀로이-리드 기준에 따르면 거대 성분이 존재할 조건은

$$\frac{\langle k^2 \rangle}{\langle k \rangle} > 2$$

이며, $\langle k^2\rangle$ 이 발산하는 멱법칙 망($\gamma \le 3$)에서는 이 조건이 항상 성립한다.

6. 퍼콜레이션과 견고성[편집]

무작위 그래프와 퍼콜레이션의 관계는 유비가 아니라 정의상 같은 것이다. 완전그래프 $K_n$ 의 각 간선을 독립적으로 확률 $p$ 로 열어 두는 본드 퍼콜레이션이 곧 $G(n,p)$ 다. 거대 성분 = 무한 클러스터, $c=1$ = 임계점, $\theta$ = 무한 클러스터 밀도로 용어가 일대일 대응한다. 격자 퍼콜레이션과 다른 점은 차원이 없다는 것이고, 그래서 무작위 그래프의 임계 지수는 항상 평균장 값이다(격자에서는 6차원 이상에서 같은 값이 나온다).

이 대응이 실무에서 쓰이는 자리가 네트워크 견고성이다. 노드나 간선을 확률 $1-p$ 로 무작위 제거한 뒤 거대 성분이 남는지 묻는 것이 사이트/본드 퍼콜레이션 그 자체다. 구성 모형에서 무작위 제거에 대한 문턱은

$$p_c \;=\; \frac{\langle k \rangle}{\langle k^2 \rangle - \langle k \rangle}$$

인데, 멱법칙 지수 $2 < \gamma < 3$ 이면 $\langle k^2 \rangle$ 이 발산해 $p_c \to 0$ 이다. 무작위 고장으로는 이 망을 못 부순다는 뜻이고, 반대로 차수 큰 정점부터 노리면 순식간에 무너진다. 인터넷의 견고성/취약성 이중성으로 유명한 그 결과다.

7. 널 모형과 벤치마크로서의 무작위 그래프[편집]

시뮬레이션·알고리즘 쪽에서 무작위 그래프를 만나는 방식은 대개 도구로서다.

• 기대 성능 분석 — 최악의 경우가 절망적인 알고리즘도 무작위 입력에서는 멀쩡한 경우가 많다. 그래프 동형 판정이 대표적이다. $G(n,1/2)$ 에서 거의 모든 그래프는 이웃 차수 정보 몇 번만 정제해도 정점이 전부 구별되므로, “거의 모든 그래프”에 대해 선형 시간에 표준형이 나온다. 이론적으로 어려운 문제가 무작위 입력에서 쉬운 이 현상은 SAT 풀이기에서와 정반대 방향의 교훈을 준다 — 어떤 문제는 무작위가 쉽고, 어떤 문제는 무작위가 가장 어렵다.
• 조합적 존재 증명 — $G(n,1/2)$ 에서 큰 단색 클리크가 없을 확률이 양수임을 보이는 것만으로 램지 수의 하한 $R(k,k) > 2^{k/2}$ 이 나온다. 에르되시의 확률론적 방법이며, 구체적인 예시 하나 없이 존재만 증명하는 이 스타일이 조합론의 표준 무기가 됐다.
• 군집 탐지의 기준선 — 모듈러리티 $Q$ 는 “같은 커뮤니티 안의 간선 비율”에서 “구성 모형이 예측하는 기대값 $k_ik_j/2m$“을 뺀 값이다. 즉 커뮤니티 탐지의 목적함수 자체에 무작위 그래프가 기준선으로 박혀 있다. 네트워크 모티프 검출도 차수를 보존한 무작위화 앙상블과 비교해서 유의성을 잰다.
• 확장성과 스펙트럼 — 무작위 정규 그래프는 거의 확실히 좋은 확장 그래프(expander)라, 인터커넥트 토폴로지·부호 이론·스펙트럴 군집화 이론의 표준 예시로 쓰인다. 반대로 그래프 분할을 시험할 때 무작위 그래프를 쓰면 좋은 분할 자체가 존재하지 않아 벤치마크로서 의미가 없다.

마지막 항목은 강조할 만하다. 무작위 그래프는 유한요소 메시의 널 모형으로는 최악이다. 메시 그래프는 차수가 유계이고 거의 평면적이며 지름이 $n^{1/d}$ 스케일이라 $\ln n$ 이 아니다. 분리자 크기도 $O(n^{(d-1)/d})$ 로 작아서 중첩 분할이 먹히는데, $G(n,c/n)$ 은 그런 구조가 전혀 없다. 희소 직접 솔버의 채우기 성능이나 METIS 계열 분할기를 무작위 그래프로 벤치마크하면 실제 성능과 무관한 숫자가 나온다. 널 모형이 유용한 것은 “실제와 다르다”는 사실을 정량화해 줄 때이지, 실제를 대신할 때가 아니다.³

8. 관련 문서[편집]

• 퍼콜레이션 · 상전이 · 이징 모형 · 재규격화군
• 멱법칙 · 무척도 네트워크 · 작은 세상 네트워크 · 구성 모형
• 깊이 우선 탐색 · 너비 우선 탐색 · 강한 연결 요소 · 최소 신장 트리
• 2-SAT · SAT 풀이기 · NP-완전 · 최대 클리크
• 그래프 분할 · METIS · 희소행렬 · 스펙트럴 군집화
• 몬테카를로 방법 · 마르코프 연쇄 몬테카를로 · 중심극한정리

9. Footnotes[편집]

1. Erdős, P. & Rényi, A. (1959). “On random graphs I”. Publ. Math. Debrecen 6, 290–297 이 $G(n,M)$ 을, Gilbert, E. N. (1959). “Random graphs”. Ann. Math. Statist. 30(4), 1141–1144 가 $G(n,p)$ 를 다뤘다. 세상 모두가 $G(n,p)$ 를 “에르되시-레니 그래프”라 부르는 통에 길버트는 이름을 뺏긴 셈인데, 정작 논문을 뜯어 보면 오늘날 우리가 쓰는 모형은 길버트 쪽이다. 억울한 명명은 과학사의 국룰(스티글러의 법칙)이다. ↩

2. 임계창의 정밀 구조는 Bollobás (1984)와 Łuczak (1990)이 확립했고, 최대 성분들의 극한이 브라운 운동 관련 확률 과정으로 기술된다는 것은 Aldous (1997)의 결과다. 동전 던지기에서 시작해 브라운 운동으로 끝나는 전개가 퍼콜레이션 쪽 사정과 판박이인데, 우연이 아니라 둘이 같은 대상이기 때문이다. ↩

3. 그래서 “우리 데이터가 무작위 그래프와 유의미하게 다르다”는 주장은 사실상 아무 정보도 없다. 실제 망 중에 $G(n,p)$ 를 닮은 것은 하나도 없기 때문이다. 널 모형을 고를 때는 무엇을 보존하고 무엇을 무작위화하는가를 먼저 정해야 하고, 차수열까지 보존한 구성 모형과 비교했을 때도 남는 차이라야 비로소 할 말이 생긴다. 논문 심사에서 이 지적을 받아 본 사람이 한둘이 아니다. ↩