복잡계 네트워크의 모든 것: 쾨니히스베르크 다리에서 팬데믹 추적까지

들어가며: 연결이 곧 구조다

우리는 네트워크의 시대에 살고 있다. 소셜 미디어의 친구 관계, 뇌 속 뉴런의 시냅스, 항공 노선, 단백질 상호작용, 금융기관 간 대출 — 이 모든 것의 공통점은 노드(node)와 엣지(edge)로 이루어진 네트워크라는 것이다.

놀라운 발견은 이것이다: 이 전혀 다른 영역의 네트워크들이 동일한 수학적 법칙을 따른다. 인터넷의 구조와 세포 내 대사 네트워크가 같은 멱법칙(power law)을 보이고, 할리우드 배우 네트워크와 예쁜꼬마선충의 신경망이 같은 "좁은 세상" 속성을 가진다.

이 글에서는 1736년 오일러의 쾨니히스베르크 다리 문제에서 시작해, 에르되시-레니의 랜덤 그래프, 밀그램의 6단계 분리, 와츠-스트로가츠의 좁은 세상 모델, 바라바시-앨버트의 척도 없는 네트워크까지 — 복잡계 네트워크 과학의 완전한 역사를 추적한다. 그리고 이 이론이 전염병 확산, 금융 위기, 뇌 과학, 테러 네트워크 분석에 어떻게 적용되는지를 특집으로 다룬다.

---

1부: 수학적 기원 — 그래프 이론의 탄생

오일러와 쾨니히스베르크 다리 문제 (1736년)

모든 것은 하나의 질문에서 시작되었다.

프로이센의 쾨니히스베르크(현 러시아 칼리닌그라드)는 프레겔 강 위에 두 개의 섬이 있었고, 이 섬들과 양쪽 육지를 7개의 다리가 연결하고 있었다. 시민들의 질문: "모든 다리를 정확히 한 번씩만 건너며 산책할 수 있는가?"

레온하르트 오일러(Leonhard Euler) 는 1735년 8월 26일 상트페테르부르크 학술원에 이 문제의 해법을 발표했다 (논문은 1741년 출간). 그의 접근은 혁명적이었다 — 육지를 꼭짓점(vertex) 으로, 다리를 변(edge) 으로 추상화한 것이다.

이 논문은 그래프 이론의 최초의 정리(theorem) 이자, 네트워크 이론의 최초의 증명으로 간주된다. 오일러는 자신이 새로운 수학 분야를 창시하고 있다는 것을 알고 있었다 — 그는 이를 "위치의 기하학(geometria situs)"이라 불렀다.

그래프 이론의 발전

오일러 이후 그래프 이론은 여러 갈래로 발전했다:

• 1845년: 키르히호프(Gustav Kirchhoff) 가 전기 회로를 그래프의 신장 트리(spanning tree)로 표현하며 회로 법칙을 정립
• 1852년: 프랜시스 거스리(Francis Guthrie) 가 4색 문제를 제기 — 이 문제는 124년 뒤인 1976년에야 컴퓨터 보조 증명으로 해결됨
• 1878년: 실베스터(James Joseph Sylvester) 가 Nature에 발표한 논문에서 "그래프(graph)" 라는 용어를 처음 사용
• 1930~40년대: 프랭크 램지(Frank Ramsey) 와 폴 투란(Paul Turán) 이 극단 그래프 이론(extremal graph theory) 기초 확립

에르되시-레니 랜덤 그래프 모델 (1959~1960년)

현대 네트워크 과학의 출발점은 헝가리 수학자 폴 에르되시(Paul Erdős) 와 알프레드 레니(Alfréd Rényi) 의 두 편의 논문이다.

• 1959년: "On Random Graphs I" — n개의 꼭짓점에 M개의 변을 균일 확률로 배치하는 G(n,M) 모델 제안
• 1960년: "On the Evolution of Random Graphs" — 랜덤 그래프에 변을 점진적으로 추가할 때 일어나는 구조적 변화를 상세히 분석

에르되시-레니 모델은 아름다운 수학이었다. 그러나 40년 뒤, 현실 네트워크를 측정해 보니 완전히 틀렸다는 것이 밝혀진다.

---

2부: 좁은 세상 — 여섯 다리만 건너면

카린티의 직관 (1929년)

헝가리 작가 프리제시 카린티(Frigyes Karinthy) 는 1929년 단편 "사슬 고리(Láncszemek)"에서 하나의 게임을 제안했다. 당시 세계 인구 18억 명 중 아무나 한 명을 골라, 5명 이하의 중간자를 거쳐 연결해 보라는 것이었다. 이것이 "6단계 분리(six degrees of separation)" 개념의 최초 등장이다.

밀그램의 좁은 세상 실험 (1967년)

스탠리 밀그램(Stanley Milgram) 은 1967년 Psychology Today에 발표한 "좁은 세상 문제(The Small World Problem)"로 카린티의 직관을 실험적으로 검증했다.

케빈 베이컨의 6단계

1994년 1월, 올브라이트 칼리지 학생 크레이그 파스, 브라이언 터틀, 마이크 지넬리는 케빈 베이컨의 영화 두 편을 연속으로 본 뒤, 어떤 배우든 공동 출연작을 통해 베이컨과 연결할 수 있다는 게임을 고안했다. Premiere 매거진 인터뷰에서 베이컨 본인이 "할리우드의 모든 사람과 작업했거나, 그런 사람과 작업한 사람"이라고 말한 것이 영감이었다.

이 유머러스한 게임은 네트워크 과학을 대중에게 알리는 데 결정적 역할을 했다.

와츠-스트로가츠 모델: 좁은 세상의 수학 (1998년)

1998년 6월, 던컨 와츠(Duncan Watts) 와 스티븐 스트로가츠(Steven Strogatz) 가 Nature에 발표한 논문 "Collective dynamics of 'small-world' networks"는 네트워크 과학의 역사를 바꿨다.

핵심 질문은 이것이었다: 규칙적 격자(lattice)는 높은 클러스터링을 갖지만 경로가 길고, 랜덤 그래프는 경로가 짧지만 클러스터링이 낮다. 둘 다 높은 네트워크가 존재할 수 있는가?

답은 예스였다. 규칙적 격자에서 아주 적은 비율의 변만 무작위로 다시 연결해도, 평균 경로 길이는 급격히 줄어들면서 높은 클러스터링은 유지된다. 이것이 좁은 세상 네트워크(small-world network) 다.

와츠와 스트로가츠는 세 가지 실제 네트워크에서 이를 검증했다:

세 네트워크 모두 랜덤 그래프에 가까운 짧은 경로와 랜덤 그래프보다 훨씬 높은 클러스터링 계수를 보였다 — 좁은 세상 속성의 보편성을 입증한 것이다.

---

3부: 척도 없는 네트워크 — 허브가 세상을 지배한다

바라바시-앨버트 모델 (1999년)

와츠-스트로가츠 논문이 나온 지 불과 16개월 뒤, 앨버트-라슬로 바라바시(Albert-László Barabási) 와 레카 앨버트(Réka Albert) 가 Science에 발표한 논문 "Emergence of Scaling in Random Networks"가 또 한 번 패러다임을 전환했다.

바라바시와 앨버트는 노터데임 대학교(nd.edu) 도메인의 웹 페이지 약 325,000개를 매핑했다. 에르되시-레니 모델이 예측하는 포아송 분포와는 전혀 다른 결과가 나왔다 — 차수 분포가 멱법칙(power law) 을 따른 것이다:

P(k) ~ k^(-γ)

대부분의 노드는 소수의 연결만 갖지만, 극소수의 노드는 엄청난 수의 연결(허브) 을 갖는다. 이 분포에는 특징적인 척도(scale)가 없기 때문에 "척도 없는 네트워크(scale-free network)"라 불린다.

두 가지 메커니즘

바라바시-앨버트 모델의 핵심은 단 두 가지:

선호적 연결(preferential attachment) 은 직관적으로 "부익부 빈익빈" 또는 "마태 효과" 다. 새 웹 페이지를 만들 때, 이미 유명한 사이트에 링크할 확률이 높다. 신입 연구자는 이미 많이 인용된 논문을 더 많이 인용한다. 새 공항 노선은 이미 허브인 공항에 연결될 가능성이 높다.

이 논문은 현재 26,000회 이상 인용되었다.

에르되시-레니 vs. 바라바시-앨버트

"강건하지만 취약한": 허브의 양면성 (2000년)

앨버트, 정하웅, 바라바시는 2000년 Nature에 "Error and attack tolerance of complex networks"를 발표해, 척도 없는 네트워크의 결정적 특성을 밝혔다:

• 랜덤 실패에 강건하다: 노드를 무작위로 제거해도 네트워크 연결성이 유지된다 (제거되는 대부분이 저차수 노드이므로)
• 의도적 공격에 취약하다: 허브 노드를 의도적으로 제거하면 네트워크가 빠르게 분열된다

이 "강건하지만 취약한(robust yet fragile)" 이중성은 인터넷, WWW, 생물학적 네트워크 등 모든 척도 없는 네트워크의 보편적 특성이며, 사이버 보안에서 전염병 통제까지 심오한 함의를 갖는다.

---

4부: 네트워크 과학의 핵심 도구들

약한 유대의 힘 (1973년)

바라바시보다 26년 앞서, 사회학자 마크 그래노베터(Mark Granovetter) 가 1973년 American Journal of Sociology에 발표한 "The Strength of Weak Ties"는 네트워크 사고의 패러다임을 열었다.

핵심 발견: 새로운 정보와 취업 기회를 제공하는 것은 친한 친구(강한 유대)가 아니라 지인(약한 유대) 이다. 약한 유대는 서로 다른 사회적 클러스터를 다리처럼 연결하기 때문이다. 282명의 구직자를 조사한 결과, 약한 유대가 강한 유대보다 더 유용했다.

이 논문은 사회과학 역사상 가장 많이 인용된 논문으로, 인용 횟수가 약 70,000회에 달한다.

커뮤니티 구조와 모듈성

마크 뉴먼(Mark Newman) 과 미셸 기르반(Michelle Girvan) 은 2002년 PNAS에서 기르반-뉴먼 알고리즘을 소개했다. 매개 중심성(betweenness centrality)이 가장 높은 변을 반복적으로 제거하면, 네트워크가 자연스럽게 커뮤니티로 분리된다는 것이다.

뉴먼은 이어서 2006년 모듈성(modularity, Q) 이라는 정량적 지표를 도입했다 — 네트워크가 얼마나 잘 커뮤니티로 분할되는지를 측정하는 척도다.

네트워크 모티프 (2002년)

우리 알론(Uri Alon) 의 바이츠만 연구소 팀은 2002년 Science에서 네트워크 모티프(network motifs) 개념을 발표했다. 복잡한 네트워크에서 랜덤 네트워크보다 유의미하게 자주 출현하는 연결 패턴(부분 그래프) 이 있으며, 이것이 네트워크의 기본 구성 블록이라는 것이다. 특히 피드포워드 루프(feed-forward loop) 는 대장균부터 효모, 인간까지 보편적으로 발견되는 3-노드 모티프다.

핵심 지표 정리

---

5부: 주요 논문 연대기

---

6부: 특집 — 네트워크 분석 실전 사례

사례 1: 전염병 확산 — 슈퍼스프레더의 네트워크 과학

척도 없는 네트워크에서는 전염 역치가 사라진다

2001년, 파스토르-사토라스(Pastor-Satorras) 와 베스피냐니(Vespignani) 가 Physical Review Letters에 발표한 논문은 전염병학을 뒤흔들었다. 고전적 SIR/SIS 모델에서는 전염률이 특정 역치(threshold) 아래면 전염병이 사라진다. 그러나 척도 없는 네트워크에서는 이 역치가 0으로 수렴한다 — 아무리 낮은 전염률이라도 항정 상태의 감염이 유지된다.

이유는 허브 때문이다. 소수의 초연결 개인(슈퍼스프레더)이 전체 전파를 지배한다.

COVID-19: 8%가 60%를 감염시킨다

2020년, 락슈미나라얀(Laxminarayan) 등이 Science에 발표한 연구는 사상 최대 규모의 COVID-19 접촉 추적이었다. 인도 타밀나두와 안드라프라데시에서 84,965명의 확진자와 575,071명의 접촉자를 추적한 결과:

한국 31번 환자 (2020년 2월): 대구 신천지교회 신도인 61세 여성이 증상이 있는 상태에서 4차례 예배에 참석한 뒤 확진 판정을 받았다. 한 달 내 이 클러스터에서 5,080명이 확진 — 당시 한국 전체 확진자의 절반 이상이었다.

이 사례들은 네트워크 과학의 예측을 정확히 확인했다: 허브를 차단하면 전염이 붕괴하고, 허브를 놓치면 대유행이 된다.

사회적 네트워크가 건강을 결정한다

니콜라스 크리스타키스(Nicholas Christakis) 와 제임스 파울러(James Fowler) 는 프래밍엄 심장 연구 데이터를 활용해, 건강 상태가 사회적 네트워크를 통해 3단계까지 전파됨을 밝혔다:

• 비만 (2007, NEJM): 친구가 비만이 되면 본인이 비만이 될 확률 57% 증가. 이 영향은 3단계까지 미침
• 금연 (2008, NEJM): 흡연자와 비흡연자 클러스터가 네트워크에서 명확히 구분됨
• 행복 (2008, BMJ): 1마일 이내 행복해진 친구는 본인의 행복 확률 25% 증가, 옆집 이웃은 34% 증가

---

사례 2: 금융 위기 — "파산하기엔 너무 연결된"

2008년 금융 위기의 네트워크 분석

아세모글루, 오즈다글라르, 타흐바즈-살레히(Acemoglu, Ozdaglar & Tahbaz-Salehi) 는 2015년 American Economic Review에서 금융 네트워크의 상전이를 수학적으로 증명했다:

• 충격의 크기가 임계값 이하일 때: 연결성이 높을수록 안정성 향상 (손실 분산)
• 충격의 크기가 임계값 이상일 때: 연결성이 높을수록 전염 증폭 (손실 전파)

DebtRank: "파산하기엔 너무 중심적인"

바티스톤(Battiston) 등은 2012년 Scientific Reports에서 2008~2010년 미 연준의 긴급 대출 프로그램 1조 2천억 달러를 네트워크로 분석했다. 가장 많은 자금을 받은 22개 기관이 강하게 연결된 그래프를 형성하며, 위기 정점에서 각각이 시스템적으로 중요해짐을 밝혔다.

핵심 결론: 논쟁의 프레임을 "too-big-to-fail"에서 "too-central-to-fail(파산하기엔 너무 중심적인)"로 전환해야 한다. 규모가 작더라도 네트워크에서 중심적인 위치에 있으면 시스템적 위험을 초래한다.

글로벌 기업 지배 네트워크

2011년 ETH 취리히의 비탈리, 글래트펠더, 바티스톤(Vitali, Glattfelder & Battiston) 은 PLoS ONE에서 43,060개 다국적 기업의 소유 구조를 600,508개 노드, 1,006,987개 소유권 관계의 네트워크로 분석했다:

---

사례 3: 인터넷과 WWW — 디지털 세계의 구조

인터넷 토폴로지: 팔루초스 3형제 (1999년)

미할리스, 페트로스, 크리스토스 팔루초스(Faloutsos) 3형제는 1999년 ACM SIGCOMM에서 인터넷의 AS(Autonomous System) 간 토폴로지가 멱법칙을 따른다는 것을 발견했다. 상관계수 96% 이상, 1997년 11월~1998년 12월 동안 인터넷이 45% 성장했음에도 멱법칙은 유지되었다.

WWW의 "나비넥타이" 구조 (2000년)

브로더(Broder) 등은 AltaVista 크롤 데이터 2억 페이지, 15억 링크를 분석해, 웹의 거시 구조가 나비넥타이(bow-tie) 형태임을 밝혔다:

Google PageRank: 네트워크 분석의 상업적 승리

래리 페이지(Larry Page) 와 세르게이 브린(Sergey Brin) 이 1996년 스탠퍼드에서 개발한 PageRank는 본질적으로 웹 그래프에 대한 고유벡터 중심성(eigenvector centrality) 분석이다. "랜덤 서퍼"가 링크를 따라가거나 무작위로 점프하는 확률 과정의 정상 분포를 계산한다. 5억 1,800만 개의 하이퍼링크를 매핑한 이 작업은, 네트워크 분석을 역사상 가장 성공적인 사업으로 만들었다.

---

사례 4: 뇌 과학 — 커넥톰의 시대

예쁜꼬마선충: 최초의 완전한 커넥톰 (1986년)

화이트(White) 등은 1986년 연속 전자현미경 사진으로부터 15년간 수작업으로 예쁜꼬마선충(C. elegans)의 302개 뉴런과 약 7,000개 시냅스 연결을 매핑했다. 이것은 역사상 최초의 완전한 동물 신경 회로도(커넥톰)다.

초파리 뇌: FlyWire 프로젝트 (2024년)

2024년 10월 Nature에 발표된 FlyWire 프로젝트는 성체 초파리 뇌 전체를 매핑했다:

인간 뇌 커넥톰 프로젝트

2010년 NIH가 4,000만 달러, 5년 규모로 착수. 1,200명의 건강한 성인을 대상으로 fMRI, dMRI, MEG/EEG 등 다중 뇌영상을 촬영하여 장거리 뇌 연결을 매핑했다. 뇌 회로가 무작위 얽힘이 아니라 격자 패턴에 더 가깝게 조직되어 있다는 것을 발견했다.

---

사례 5: 대규모 정전 — 연쇄 실패의 역학

2003년 북미 대정전

2003년 8월 14일, 미국 역사상 최악의 정전이 발생했다.

던컨 와츠는 저서 Six Degrees(2003)에서 전력망의 연쇄 실패를 네트워크 과학의 관점에서 분석했다. 개별 요소를 보호하기 위한 보호 장치(차단기, 릴레이)가 역설적으로 시스템 전체의 연쇄 붕괴 가능성을 높인다 — 한 요소가 차단되면 부하가 이웃에 재분배되고, 이것이 다시 차단을 유발하는 도미노 효과.

이것은 좁은 세상 네트워크의 짧은 경로 길이가 효율성과 함께 취약성도 높인다는 이론적 예측의 정확한 실증이다.

---

사례 6: 테러 네트워크 분석 — 9/11

밸디스 크렙스의 9/11 네트워크 분석 (2002년)

네트워크 분석가 밸디스 크렙스(Valdis Krebs) 는 공개 데이터를 사용해 19명의 9/11 납치범과 그들의 연결망을 매핑했다 (Connections, 2002).

• 모하메드 아타(Mohamed Atta) 가 차수 중심성과 근접 중심성 모두에서 최고 점수
• 4명의 조종사가 밀접한 클릭(clique) 을 형성
• 모든 납치범이 나와프 알하즈미(Nawaf Alhazmi) 와 칼리드 알미다르(Khalid Almihdhar) 로부터 2단계 이내에 위치

핵심 취약점: 네트워크가 고유 기술(조종)과 높은 연결성을 동일한 노드에 집중시켰다. 이 허브를 발견했다면 네트워크 전체를 무력화할 수 있었다 — 척도 없는 네트워크의 "의도적 공격에 취약" 속성 그대로다.

---

사례 7: 소셜 네트워크 — 4.74단계의 세상

페이스북: 밀그램을 세계 규모로 재현 (2012년)

백스트롬(Backstrom) 등은 2012년 ACM Web Science Conference에서 7억 2,100만 명의 페이스북 사용자와 약 690억 개의 친구 관계를 분석한 결과를 발표했다. 평균 거리는 4.74 — 밀그램의 "6단계"가 5단계 미만으로 줄어든 것이다.

이것은 세계 최초의 행성 규모(planetary-scale) 사회 네트워크 거리 측정이었다.

케임브리지 애널리티카: 네트워크의 어두운 면 (2018년)

2013년 알렉산드르 코간(Aleksandr Kogan)이 만든 앱 "thisisyourdigitallife"에 약 270,000명이 참여했다. 그러나 이 앱은 참여자들의 친구 데이터까지 수확하여 최대 8,700만 프로필에 접근했다. 이 데이터로 미국 유권자 1인당 최대 5,000개 데이터 포인트의 심리 프로필을 구축했다.

2018년 3월 스캔들이 폭로된 뒤, 페이스북 시가총액이 며칠 만에 1,000억 달러 이상 하락했고, FTC는 2019년 7월 역대 최대 규모의 50억 달러 벌금을 부과했다.

이것은 네트워크의 구조적 특성 — 친구의 친구를 통한 정보 전파 — 이 어떻게 무기화될 수 있는지를 보여준 사건이다.

---

7부: 현재와 미래 — 네트워크 과학의 최전선

그래프 신경망 (Graph Neural Networks, GNNs)

네트워크 과학과 딥러닝의 결합이 GNN이다. 주요 프로덕션 사례:

• Pinterest (PinSage, KDD 2018): 30억 노드, 180억 엣지의 그래프에서 수억 명에게 개인화 추천
• Uber Eats: GraphSage 기반 음식 추천, 기존 모델 대비 AUC 12% 향상
• AlphaFold 2 (DeepMind, CASP14 2020): 단백질을 공간 그래프로 처리, 중간값 GDT-TS 92.4/100, 원자 하나 폭(1.6Å) 수준의 정확도. 97개 표적 중 88개에서 승리 — 사실상 단일 체인 단백질 구조 예측 문제를 해결

네트워크 의학 (Network Medicine)

바라바시 등은 2021년 PNAS에서 인간 인터랙톰(18,508개 단백질, 332,749개 상호작용)에 SARS-CoV-2의 332개 숙주 단백질 표적을 매핑하여, COVID-19 약물 재목적화 후보 6,340종을 순위화했다. 332개 바이러스 표적 중 208개가 연결된 질환 모듈을 형성한다는 것을 밝혔다.

이것은 질환을 개별 유전자가 아니라 네트워크의 교란으로 이해하는 패러다임이다. 바라바시의 인간 질환 네트워크(Diseasome, 2007, PNAS) 에서 시작된 이 접근법은 정밀 의학의 새로운 기반이 되고 있다.

핵심 도서

---

맺으며: 네트워크적 사고의 힘

1736년 오일러가 다리 문제를 풀기 위해 했던 핵심적 작업은, 복잡한 현실을 노드와 엣지로 추상화한 것이다. 290년이 지난 오늘날, 우리는 같은 추상화로 전염병을 추적하고, 금융 위기를 예측하고, 뇌를 해독하고, 테러 네트워크를 분석한다.

복잡계 네트워크 과학이 가르쳐 주는 핵심 통찰은 세 가지다:

1. 구조가 기능을 결정한다. 같은 노드라도 네트워크에서의 위치에 따라 역할이 완전히 달라진다. 허브를 제거하면 네트워크가 붕괴하고, 약한 유대를 끊으면 정보 흐름이 차단된다.

2. 보편적 법칙이 존재한다. 인터넷과 세포 대사 네트워크, 할리우드 배우 관계와 예쁜꼬마선충의 신경망이 같은 수학적 구조를 공유한다. 이것은 자연이 스스로 조직하는 방식에 근본적인 원리가 있다는 뜻이다.

3. 연결이 곧 리스크이자 기회다. 2003년 정전, 2008년 금융 위기, COVID-19 팬데믹은 모두 네트워크의 연결성이 효율과 취약성을 동시에 만든다는 것을 보여줬다.

오일러는 다리를 보고 그래프를 발견했다. 바라바시는 웹을 보고 허브를 발견했다. 다음 발견은, 네트워크적 시각으로 세상을 바라보는 사람의 몫이다.