네트워크 세상보기 - 2 복잡한 네트워크에도 법칙은 있다 글 강병남, 정하웅 사진 GAMMA 필자소개 강병남 kahng@phya.snu.ac.kr 1989년 미국 보스턴대에서 박사학위를 받고 버클리 소재 캘리포니 아대 연구원, 건국대 물리학과 교수(1991-2000)를 거쳐 현재 서울 대 자연과학부에 재직중이다. 복잡계와 나소 시스템에 관한 연구를 수행중이다. 화제를 불러일으킨 책 링크 를 번역했다. 정하웅 hjeong@mail.kaist.ac.kr 1998년 서울대 물리학과에서 박사학위를 받고 미국 노트르담대에 서 연구원과 조교수를 거쳐 2001년부터 한국과학기술원 물리학과 에 재직중이다. 현재 정보통신망과 생물정보학 등의 예를 통해 네트 워크 개념을 이용한 복잡계의 이해에 관한 연구를 수행중이다. 1993년 윌 스미스가 주연한 영화 6단계 분리 (six degrees of separation)에는 다음의 대사가 나온다. 이 지구상에 있는 모든 사람은 단지 여섯사람의 타 인에 의해 서로 떨어져있을 뿐이란다. 6단계의 분리란 말 이지. 우리와 이 세상에 있는 그 어떤 사람과도 단지 여 섯사람만 거치면 서로 연결이 된단 말이지. 대통령과 같 은 유명인뿐 아니라 베니스에서 곤돌라를 젓는 뱃사공이 나 열대우림 지대에 사는 원주민하고도 그렇지. 결국 나 는 이 지구상의 모든 사람들과 단지 여섯명의 사람들로 이뤄진 사슬에 의해 묶여있는 셈이지. 이건 정말로 심오 한 사상이야. 모든 사람들을 새로운 세상으로 이끌어주 는문인게야. 이 대사처럼 우리는 매우 좁은 세상에서 살고 있다. 사 람들이 그물같이 서로 얽혀있는 사회라는 네트워크 안에 서 우리는 서로의 연결을 통해 좁은 세상을 만들고 있는 것이다. 재미난 점은 이러한 좁은 세상 현상이라는 것이 사회에만 국한되는 것이 아니라는 것이다. 엄청난 크기 의 지식 네트워크인 월드와이드웹이 단지 19번의 마우 스 클릭으로 모두 다 연결될 만큼 좁다. 우리 몸속의 신 진대사 반응에 참여하는 여러 물질들도 단 3번의 생화 학 반응을 통해서 연결 가능하다. 이런 점을 살펴볼 때, 다음과 같은 성급한 결론에 다다를 지도 모른다. 우리 주
일러스트 박현정 N 네트워크의 구조가 바둑판처럼 생겼다면 좁은 세상이 만들어지지 않는다. A에서 B로 갈 때 2N을 거쳐가야 한다. 짧은 거리로 연결될 수 없다. N 위의 모든 네트워크는 구성성분들이 서로 가깝게 연결돼 있는 좁은 세상을 이루고 있다고. 그렇다면 좁은 세상 을 이루는 네트워크는 실제로 어떤 모습일까. 인간사회는 바둑판 아니라 무작위 그래프 인간 사회의 네트워크는 사람을 점으로 인맥을 선으로 나타낼 수 있다. 바둑판처럼 말이다. 그러나 바둑판처럼 생긴 네트워크는 결코 좁은 세상이 되지 못한다. 예를 들 어 점 A에서 반대편 모서리에 있는 점 B로 간다고 생각 해보자. 이 경우 짧은 거리에 의해 연결될 수가 없다. 따 라서 바둑판 모양의 네트워크는 우리의 세상을 잘 나타 내주지 못한다. 그렇다면 실제 네트워크는 어떻게 생겼을까. 바둑판 네 트워크는 가까이 있는 점들만 연결돼 있다. 가까이 있는 사람들만 아는 꼴이다. 그러나 우리는 먼 거리에 있는 사 람과도 알고 지낸다. 따라서 실제 네트워크는 가까운 점 뿐 아니라 먼 거리의 점과도 연결이 가능해야 한다. 1959년 헝가리의 천재 수학자인 에르도쉬와 레이니는 실제 네트워크를 무작위적 그래프(random graph)라는 모델로 설명했다. 이 모델은 각각의 점들이 위치에 관계 없이 동일한 확률로 서로 연결된다. 따라서 먼 거리를 연 결하는 몇몇의 무작위적 연결선 덕분에 멀리 떨어져 있 는두사람사이가쉽게연결될수있는좁은세상을형 성한다. 사실 무작위적 네트워크는 실제 주변의 여러가지 네트 워크들이 복잡하다는 점을 무작위적이라는 점으로 바꿔 생각한 것이다. 복잡성을 무작위성으로 바꿔보았던 에르 도쉬와 레이니의 사고의 전환은 좁은 세상을 구현하는 훌 131
륭한 네트워크 모형을 만들어준 것이다. 에르도쉬와 레이니의 논문 발표 이후 무작위적 네트 워크는 네트워크에 관한 연구에서 절대적인 위치를 차지 했다. 때문에 사회학자나 인터넷 전문가들은 사회, 세포, 인터넷 등 충분히 복잡한 네트워크는 무작위적 네트워크 로 설명되리라고 굳게 믿어왔다. 3-4년 전까지만 해도 그랬다. 1 2 3 최근에야 실제 네트워크와 모형 비교 네트워크가 막연히 무작위적이라고 하기에는 사회나 세 포, 인터넷 등이 어떤 법칙에 따라 짜여진 것처럼 보인다. 하지만 복잡한 네트워크의 모습이 네트워크의 모델과 실 제로 똑같은지를 비교하기는 그리 쉬운 문제가 아니다. 만약 두 네트워크를 서로 겹쳐보는 방법이 있다면 쉽겠 지만 이 방법은 거의 불가능하다. 과학자들이 생각한 비교 방법은 네트워크의 중요한 특 징을 찾아 이를 비교하는 것이다. 네트워크를 이루는 점 이 몇개의 선으로 연결돼 있는지를 살펴보는 방법이다. 각 점이 몇개의 선으로 연결되는지를 세어보고 히스토그램 으로 만들어본다. 히스토그램의 각 기둥들을 연결한 곡선 은 연결선 분포함수라고 한다. 이 방법으로 바둑판식 네 트워크를 나타내면 분포함수는 막대 하나로 표현할 수 있 다. 모든 점이 정확하게 4개의 연결선을 갖기 때문이다. 무작위적 네트워크의 경우는 어떨까. 수학적으로 엄밀 히 말하자면 쁘와송(Poisson) 분포를 따른다. 쁘와송 분 포에서는 모든 점들이 동일한 확률로 여러 점들에 연결 되는 기회를 갖는다. 즉 균일한 분포라는 말이다. 이 경 우 연결선 분포가 종모양이 된다. 대부분의 점들이 곡선 의 최고점, 즉 가장 많이 존재하는 부분의 값(최빈도값) 에 해당하는 연결선 수를 갖게 된다. 따라서 상당히 적거 나 반대로 상당히 많은 수의 연결선을 가진 점은 극히 드 물다. 그렇다면 실제 네트워크의 연결선 분포함수가 무작위 네트워크 모델의 연결선 분포처럼 종모양을 나타낼까. 너 무나 단순한 이 질문에 대한 답은 놀랍게도 최근까지 제 대로 연구되지 못했다. 그 까닭은 복잡하고 광범위한 실 제 네트워크에 대한 자료가 부족했기 때문이다. 또한 복 잡한 것은 무작위하다는 막연한 믿음도 실제 네트워크와 무작위 네트워크 모델의 비교를 가로막고 있었다. 하지만 컴퓨터와 인터넷의 발달로 여러 자료들을 손쉽게 구할 수 있게 되면서 실제 네트워크의 베일이 조금 씩 벗겨지고 있다. 최초의 비교 실험 대상은 월드와 이드웹이었다. 1999년 필자 (정하웅)는 미 노트르담대 의 바라바 시교수 인간 사회와 같은 네트워크 는 사람을 점으로, 인맥을 선으 로 나타내면 연구하기에 편리 하다. 모델 네트워크와 실제 네트워 크를 비교하기 위해 각 점이 얼 마나 많은 선으로 연결돼 있는 지를 히스토그램으로 표현하는 방법이 쓰인다. 월드와이드웹이 무작위 네트워 크라면 5백개의 웹사이트와 링 크돼 있는 사이트가 있을 확률 은 전체 우주에서 특정한 원자 하나를 찾을 확률보다 작다. 132 과학동아 2003.02
4 가 이끄는 연구팀에 소속돼 실험을 주도했다. 그는 월드 와이드웹을 자동으로 돌아다니며 정보를 모으는 프로그 램인 로봇(또는 크롤러, crawler)를 만들어 월드와이드웹 의 연결지도를 얻었다. 즉 각 웹페이지가 어떤 웹페이지 와 어떻게 링크가 되는지를 알아낸 것이다. 월드와이드웹의 지도를 통해 웹페이지가 평균적으로 19번의 링크로 서로 연결돼 있는 좁은 세상이라는 점을 연구팀은 알아냈다. 하지만 더 재미있는 점은 실제 네트 워크가 정말로 무작위한지를 비교할 수 있었다는 것이다. 실제 네트워크인 월드와이드웹의 지도를 손에 넣었기 때 문이다. 연구를 시작하기 전 연구팀도 무작위적 네트워크 이론 의 지배를 받았던 탓에 웹페이지들이 비슷한 정도의 연 결선을 가질 것이라고 예상했다. 아마도 독자들도 웹페 이지들에 링크된 다른 웹페이지의 수가 대부분 비슷할 것 이라고 예상하기 쉬울 것이다. 링크수가 1천개 넘는 웹페이지 존재 그러나 결과는 놀랍게도 쁘와송 분포의 종모양이 아니 었다. 멱함수(power-law)라고 불리는 새로운 분포함수 를 따르는 것으로 밝혀졌다. 멱함수 분포는 평균 주위에 정점( )이 없고 계속 감소하는 모양을 갖는다(그림 2). 따라서 멱함수 분포를 따르는 네트워크에서는 연결선이 적은 점들이 대부분이지만 동시에 연결선이 많은 점들도 적지만 함께 존재한다. 점의 개수 연결선 수 막대모양의 바둑판 네트워크 모든 점이 연결선 수가 동일하기 때문에 막 대 하나로 표현된다. 종모양의 무작위 네트워크 대부분 점들이 비슷한 연결선 수를 가지며, 상당히 적거나 많은 수의 연결선을 가진 점 은 드물다. 멱함수 법칙을 따르는 네트워크 대다수 점들은 소수의 연결선을 갖고, 이례 적으로 많은 링크를 갖는 소수의 허브들이 공 존한다. 133
1 2 월드와이드웹의 경우를 통해 두 분포를 좀더 비교해보 자. 평균적으로 한 웹페이지의 링크수가 6개 정도라고 가 정할 때, 만약 링크수 분포가 쁘와송 분포를 따른다면 어 떠한 웹페이지가 링크수를 매우 많이 가질, 예를 들어 5 백개 정도의 링크수를 가질 확률을 계산해보면 10-99 밖에 안된다. 전체 우주에서 특정한 원자 하나를 찾을 확률보 다작다. 그러나 마찬가지의 경우를 멱함수 분포로 계산해보면 상황은 무척 달라진다. 확률이 10-6 으로, 쁘와송 분포의 값과 비교했을 때 10 93 배가 된다. 다시 말해 5백개 웹사 이트와 링크가 된 웹페이지가 나올 확률이 1백만분의 1 정도다. 따라서 전체 웹페이지의 수가 10억개 이상이므 로 1천개 이상의 웹페이지가 5백개 이상의 연결선을 갖 는다. 실제로 필자의 연구 결과에서도 하이퍼링크가 심지어 1천개가 있는 웹페이지를 발견할 수 있었다. 궁금 한 독자는 웹에서 직접 찾아보는 것도 재미있을 것 같다. 멱함수 분포는 엄청나게 많은 연결선을 갖는 점, 즉 허 브가 존재할 수 있음을 말해준다. 허브의 존재유무는 앞 으로 밝혀질 네트워크의 특징을 결정짓는 중요한 역할을 한다. 무작위 네트워크와 멱함수 법칙을 따르는 네트워크 간 의 가시적이고 구조적인 차이를 쉽게 볼 수 있는 방법으 로 노트르담대의 바라바시 교수는 고속도로지도와 항공 노선지도로 설명한다(그림 3). 고속도로노선과 항공노선의 차이 고속도로 지도에서는 도시가 점이 되고 도시를 연결하 는 고속도로들이 그 점들을 잇는 연결선이 된다. 각 도시 들은 대부분 비슷한 숫자의 고속도로에 연결돼 있다. 따 라서 고속도로의 연결선 분포함수를 그려보면 대부분의 점들이 비슷한 수의 연결선을 갖는 종모양의 분포함수를 갖게 된다. 결국 무작위 네트워크는 고속도로 지도와 비 슷한 모양을 갖는다는 말이다. 반면 항공노선 지도는 고속도로 지도와는 판이하다. 이 네트워크에서는 각각의 도시에 있는 공항들이 점들이 되 고 이러한 여러 도시 간을 운항하는 비행편이 연결선이 된다. 비행기 좌석 뒤편에 꽂혀있는 항공잡지를 본 적이 있는 독자는 항공노선지도를 쉽게 기억할 것이다. 대부 분의 작은 공항들은 몇개의 주요 대도시들에 연결되는 적 은 수의 연결선을 갖는 반면 대도시들은 많은 수의 연결 선을 갖는 불균일한 네트워크를 이루고 있다. 결국 대부 분의 점들이 비슷한 숫자의 연결선으로 이어져있는 고속 도로와는 대조적으로 항공노선은 수많은 항공편을 가진 무작위 네트워크와 멱함수 분포를 따르는 네트워크는 고 속도로노선과 항공노선에 비유 된다. 고속도로노선도 각 도시를 연결하는 고속도로의 수가 대부분 비슷하다. 항공노선도 몇개의 허브 공항이 훨씬 많은 항공노선을 갖는 불균일한 네트워크 구조를 이룬다. 134 과학동아 2003.02
몇개의 허브가 수백개의 작은 공항들을 연결하는 모양을 띠게 된다. 이러한 불균일성이 멱함수 분포를 가진 네트워크의 특 징이다. 멱함수 법칙은 대다수의 점들은 소수의 연결선을 갖고, 이례적으로 많은 링크를 갖는 소수의 큰 허브들이 이 들과 공존하고 있다는 사실을 수학적으로 표현한 것이다. 참고로 바라바시 교수의 설명 이후 미 보스턴대 아마 랄 박사가 직접 항공망의 연결선 수의 분포를 조사했다. 연구 결과는 항공망의 연결선 분포가 멱함수 법칙을 정 확히 따르지는 않았다. 그러나 연결선이 많은 허브의 출 현을 쉽게 설명할 수 있는 예이기 때문에 여기서도 이를 소개했다. 할리우드 배우인맥의 연결구조는 척도가 없다 무작위 네트워크와 멱함수 법칙을 따르는 네트워크의 또다른 차이점은 고유한 척도(scale)의 유무에서 찾아볼 수 있다. 종모양의 무작위적 네트워크에서는 대부분의 점 들이 평균 또는 최빈도 값의 연결선을 갖는다. 결국 이 숫 자가 그 네트워크를 특징짓는 고유한 연결선 정도가 된 다. 그러나 이와는 대조적으로 멱함수 연결선수 분포에 서는 정점이 없기 때문에 척도로 사용할 연결선 정도가 없다. 따라서 멱함수 법칙을 따르는 네트워크에서는 내재한 고유한 척도가 없고, 이러한 이유에서 척도없는 (scale-free) 네트워크 라고 불린다. 지금까지 월드와이드웹의 연결구조가 멱함수 법칙을 따 르는 척도없는 네트워크라는 것을 살펴보았다. 더욱 재미있는 점은 척도없는 네트워크의 구조가 월드와이드 웹뿐만 아니라 여러 네트워크에서 공통적으로 발견된다 는 것이다. 네트워크에 관한 연구를 진행해 나가면서 주변에서 쉽 게 발견할 수 있는 여러가지 네트워크의 예들이 멱함수 법칙을 따르는 척도없는 네트워크라는 점이 밝혀졌다. 우 리 몸 속의 신진대사 망, 할리우드 배우들의 연결을 고려 한 사회적 네트워크, 인터넷 연결망이 그랬다. 물론 필자 (정하웅)가 연구중인 충무로 네트워크도 예외는 아니었다. 결국 1959년 이후 네트워크의 구조에 관해 우리의 사고 를 지배했던 무작위 네트워크의 이론은 막을 내리고 새 로운 척도없는 네트워크라는 이론이 탄생한 것이다. 불균일한 척도없는 네트워크의 구조가 우리에게 어떤 영향을 미칠 수 있을까. 다음호에서는 척도없는 네트워 크들이 어떻게 생겨났으며 그 구조의 중심에 있는 허브 가 어떠한 역할을 수행하는지에 대해서 살펴보기로 하 자. 1 135