네트워크의 이해 배우는즐거움

1. 무작위의 세계 (The Random Universe)
1959년 이후 폴 에스되르(Paul Erdos)와 알프레드 레니(Alfred Reney)에 의해 기초된 무작위적 네트워크 이론(Random Network Theory). 모든 구성원(node)들이 하나 이상의 링크(link)를 갖는다는 임계문턱(threshold)만 넘는다면 결국 네트워크가 커졌을 때, 모든 노드들은 같은 수의 링크를 갖게 될것이다라는 매우 평균적인 네트워크 개념이다.

2. 여섯 단계의 분리 (Six Degrees of Separation)
1929년 프리제시 카린시(Frigyes Karinthy)의 저서 <연쇄(Chains)>에서 언급된 "사람들은 기껏해야 다섯 개의 링크의 연쇄적 친분관계로 연결되어 있다"는 통찰을 1967년 하버드 교수인 스탠리 밀그램(Stanley Milgram)이 재발견한 여섯 단계의 분리(Six degrees of separation) 개념. 실험에 의해서 임의의 한쌍의 노드간 거리는 평균 6단계밖에 되지 않는다는 개념. 이 개념을 통해 우리는 단지 연결되어 있을 뿐만 아니라 매우 짧은 단계로 연결되어진 "좁은 세상(Small World)"에 살고 있다는 인식을 하게 된다.

3. 클러스터 모델 (Cluster Model)
1973년 3월 마크 그라노베터(Mark Granovetter)는 <약한 연결의 힘(The Strength of Weak Ties)>이라는 제목의 논문을 통해 사회적 네트워크는 에스되르-레니의 무작위적 모델과는 사뭇 다른 이미지를 가지고 있는데, "사회는 몇 개의 클러스터로 구성되어 있는며, 각 클러스터 내부는 모두가 서로 잘 아는 긴밀한 친구들이 서클(circle)을 이루고 있고, 외부로는 몇 개 안 되는 링크들이 있어서 클러스터들이 외부 세계로부터 격리되는 것을 막아주고 있다"는 것이다. 즉, 내부적으로 완전하게 연결된 클러스터들이 상호 간에 몇몇 약한 연결들을 통해 연결되어 있는 분절화된 그물망의 모습으로 이루어져 있다고 주장했다.

4. 클러스터 모델의 보완
던컨 와츠(Duncan Watts)와 스티븐 스트로가츠(Steven Strogatz)는 1998년 <네이처(Nature)>에 기고한 논문에 의해서 클러스터링과 무작위 모델을 화해시키는 모델을 제시한다.

노드가 많은 네트워크에 클러스터링 개념을 도입하면 그 대가로 "좁은 세상"이 사라지게 되는데 (즉 나의 1차적 또는 2차적 이웃만이 가깝게 되는데), 여기에 장거리 링크 몇개만 추가하면 클러스터링의 정도에 크게 영향을 주지 않으면서 "좁은 세상"의 속성을 유지할 수 있다는 모델이 제시되었다.

5. 무작위적 세계관의 폐기
로봇을 통해 웹구조를 이해해 보려는 노력에 의해서 위의 모든 모델으로도 설명되지 않는 현상이 발견되는데, 실제 네트워크에는 연결선 수가 극히 많은 노드(허브)가 존재하고 이는 민주주의, 공정성, 평등성의 속성을 가진 무작위적 세계관을 우리에게 버리도록 강요한다.

6. 네트워크의 속성 : 멱함수 법칙 (Power Law)
웹에서의 링크의 분포는 일반적으로 예상할 수 있는 정규 분포(Nornal Distribution, Gaussian)를 따르는 것이 아니라, 멱함수 법칙(Power Law)를 따른다. 이러한 불균등성(unevenness)은 멱함수 분포를 가진 모든 네트워크의 특징이며, 이러한 불균등성을 통해 허브의 존재는 가능하다.

멱함수 법칙을 따르는 분포란? : Power Laws, Weblogs, and Inequality

멱함수 법칙을 따르는 분포는 평균적 노드와 분포의 정점으로 구체화되는 고유한 척도(scale)을 갖지 않는다. 그리하여 멱함수 법칙을 따르는 네트워크를 척도 없는(scale-free) 네트워크라고 부른다.

7. 네트워크의 속성 : 성장(growth)과 선호적 연결(Preferential Attachment)
웹을 통해서 보는 바와 같이 네트워크는 성장(growth)한다. 네트워크에 노드가 추가되면 각 노드들은 새로운 링크를 추가하는데 가장 오래된 노드가 링크 당할 기회를 가장 많이 갖는다. 하지만 이 속성만으로는 허브의 탄생을 설명하기는 부족하다. 그 크기가 너무 작고 수가 너무 적다.

그런데 웹상에서 어떤 사이트를 링크할 것인가를 결정함에 있어서 우리는 링크의 수가 많은 노드를 더욱 선호하는 경향이 있다. 즉, 우리는 허브(Hub)를 선호한다. 요컨대 웹상에서 어디를 링크할 것인가를 결정함에 있어서 우리는 선호적 연결(Preferential Attachment)이라는 방식을 따른다.

8. 적합성 모델 (Fitness Model)
성장하는 네트워크에서 진입순서와 선호적 연결을 통해서 부익부(rich-get-richer) 현상을 야기된다. 그렇다면 성공하는 노드는 가장 처음 출발한 노드일까? 경쟁적 환경에서 각 노드들은 적합성(fitness)를 가지고 있고, 이러한 적합성 모델에 의해서 적합성이 높은 노드가 링크를 많이 획득하게 되는 적익부(fit-get-richer) 현상을 보인다.

"보즈-아인슈타인 응축(Bose-Einstein Condensation)에 의해 어떤 네트워크에서는 적합성이 가장 높은 노드가 링크를 독식할 수 있다"는 이론적 가능성 또한 존재한다.

적합성 모델은 네트워크를 노드들이 링크를 두고 치열하게 싸우는 경쟁 시스템으로 서술할 수 있도록 해준다. 현실의 네트워크에는 승자가 연속적인 허브의 위계와 함께 스포트라이트를 나누어 갖는 척도 없는 위상구조가 일반적이나, 운영체제 시장에서의 마이크로소프트의 독주와 같이 승자가 모든 링크를 가져서 척도 없는 위상 구조가 사라지는 현상이 존재한다.

(보즈-아인슈타인 응축을 네트워크에서 독식을 설명하기 위해서 도입한 부분은 개인적인 생각으로는 물리학자의 억측 같다는 생각이 듭니다.)

update : 2003. 10. 30.

9. 견고성(rubustness)와 취약성(weakness)
무작위 네트워크에서는 어떤 임계점을 초과해서 장애가 발생하면 네트워크가 붕괴될 것이라고 여겨지는데, 어떤 종류의 척도 없는 네트워크에서는 상당부분의 노드를 임의로 제거했을 때에도 네트워크는 붕괴되지 않고 그대로 작동된다. 이 같은 장애에 대한 견고성이야말로 무작위 네트워크와 구별되는 척도 없는 네트워크만의 특성인 것이다.
이러한 위상구조적 견고성은 척도 없는 네트워크에서 볼 수 있는 뚜렷한 특징인 허브의 존재에 기인한다.

하지만 이러한 척도 없는 네트워크의 구조적 특성으로 인해 허브를 제거하면 네트워크가 급격히 붕괴될 수 있다는 취약성을 아킬레스건으로 가지고 있다.

10. 바이러스와 유행
척도 없는 네트워크의 특성으로 인하여 에이즈나 컴퓨터 바이러스 같은 질병 혹은 유행이 허브를 통해서 급속하게 전파될 수 있고, 역시 허브를 찾아 치료하게 되더라도 척도 없는 네트워크의 위상구조적 특성으로 인해 질병이 완전히 사라지지 않고 소수에 노드에 남아 있을 수 있는 가능성이 존재한다.

☞ 관련글 : 링크(Linked)에 나오는 개념들 [9/30]
☞ 관련글 : Network Theory [9/22]

P.S. 여기까지가 <링크(Linked)>를 중간까지 거의 끝까지 읽고 네트워크의 성질에 대해서 이해한 정리한 부분입니다. 제 이해가 맞을 수도 있고 아닐 수도 있습니다. 관심 있으신 분들은 직접 책을 보시는게 좋을 겁니다. :-)

덧글

  • erehwon 2003/10/15 23:02 #

    아~ 마음은 그렇지 않은데 책 읽는 속도가 넘 느려요. ( ..)a
  • 이장 2003/10/16 00:38 # 삭제

    와우~~대단하네요. 나중에 서평 모임이라도 함께 했으면 좋겠네요~ 서평까지는 거창한듯하고.. 아무튼 같은 공통의 관심사를
    가진다면..^^
  • erehwon 2003/10/16 10:20 #

    예, 좋지요. 이장님. 자리만 있으면 불러주십쇼~~
  • FunFun 2003/10/30 19:51 #

    와~ 저도 얼마전에 이 책을 읽었습니다..최근 이런 복잡계 시스템에 대해 관심이 많았는데 우연히 고른 책에서 이렇게 자세히 내용을 다루고있어 반갑더라구요~
    에스되르의 무작위네트워크는 네트워크가 커졌을때 모든 노드들이 같은 수의 링크를 가지는게 아니라 각각의 노드들에 링크가 추가될 확률이 같은..즉 무작위란 것이 아니였나요?
    정말로 서평모임이 필요할거같군여..^^;
    조만간 저도 정리해서 올릴테니..함 구경오세여~
  • erehwon 2003/10/30 20:00 #

    예. 정리해주시면 좋지요. 질문하신 부분은 44페이지 맨 윗쪽에 "만약 네트워크가 커지게 되면, 링크를 완전히 무작위적으로 부여하더라도 거의 모든 노드들은 같은 수의 링크를 갖게될 것이라는 뜻이다"라는 말이 있지요.

    즉, 빈익빈부익부 현상이 일어나지 않는 시스템이 충분히 클때는 매우 평균적인 정규분포를 가지게 만드는 이론이라는 뜻입니다. :-)
  • FunFun 2003/10/30 20:36 #

    아~ 그럼 링크를 무작위적으로 부여하게되면 링크개수에 따른 노드들의 통계를 냈을때 정규분포를 이룰것이다란 뜻으로 이해하면 되나요? 흠...그래서 무작위 네트워크 이론인줄 알았는데
    실제로는 아주 많은 링크를 지닌 노드들..(즉 정규분포에서는 양쪽의 가장자리를 차지하는 노드)들이 발생하게 되서 결국 기존 무작위 네트워크이론을 폐기하게 된거구요.
    흠..그렇더라도 처음에 거의 모든 노드들이 같은 수의 링크를 갖는다는것보다는...평균적인 링크를 가지는 노드의 수가 가장 많을것이다..라고 해야 하는게 좀더 정확한 표현이 되지 않을까여..개인적 생각임당..^^
  • lemonade4 2004/05/19 14:24 #

    - 예전에 링크를 걸었었는데 이제야 덧글을 남기게 되네요.
    - 업무겸 취미로 Probabilitic Model(Ross)를 공부하고 있는데, 책의 반이 Queuing Theory, Reliability Theory 등 뭔가 Network 와 관련된 확률의 얘기가 나오더군요. 제 업무와는 무관해서 Introduction 도 보지않고 무시해버렸는데, 혹시 멀게나마 관련된 얘기가 아닐까 생각이 듭니다. "몇명만 거치면 다 관계있는 사람"이 되잖아요.^^;;
  • lemonade4 2004/05/19 14:27 #

    - 아. 이글루 제목이 멋있습니다만, erehwon 은 무슨 의미인가요? 혹시 이름이 아닐까 생각하고 있었습니다만.^^;


Google Analytics