링크(LINKED) The New Science of Networks


A. L. 바라바시 저/강병남,김기훈 공역 | 동아시아 | 원제 LINKED The New Science of Networks | 2002년 10월

2. 무작위의 세계 The Random Universe

그래프(graph) Theory : 오일러 쾨니히스베르크 bridge problem

Island = Node, bridge = link
오일러의 위대한 통찰력은 쾨니히스베르크의 다리들을 하나의 ‘그래프’로서 , 즉 ‘링크’들에 의해 연결된 ‘노드’들의 집합으로 파악한데 있다. p27

그래프 내지 네트워크라는 것은 그 구조 안에 속성들을 갖고 있는데, 그것들은 우리가 무엇인가를 할 때 우리의 능력을 제약하거나 향상 시킬 수 있다는 것. p28

에르되스 – 레니 의 무작위성 네트워크

assume : 신은 주사위 놀이를 즐긴다.
복잡성을 무작위성과 동일시 - 네트워크가 단순한 개념으로 포착되기 어려울 만큼 복잡하다면, 우리가 그것을 무작위적이라고 간주해야 하는 것이라고 여겼다.

• For p = 0, we get a regular structure (ring-like).
• As p increases, there is more randomness.
• For p = 1, it becomes the standard Erdos-Renyi random graph.
 

가정 : 신은 주사위 놀이를 즐긴다.
무작위성 링크의 속성 : 처음에는 불균등해 보이나 무작위성의 증가는 모든 노드를 같은수의 링크를 가지게 만든다. 고로 모든 노드는 평등하게 평가된다.

3. 여섯 단계의 분리 Six Degrees of Separation

1967년 하버드 대학 스탠리 밀그램 (Stanley Milgram)
여섯 단계만 거치면 모든 노드에 접근할 수 있다.

수천대의 컴퓨터를 동원해서 쉴새 없이 웹을 긁어 오고 있는 대규모 검색엔진조차도 전체 웹의 15%에 못 미치는 부분만을 포괄하고 있다 p62

웹은 19단계의 분리로 볼 수 있다.

여섯 단계 또는 열아홉 단계라는 문구는 자칫하면 ‘좁은세상’에 서는 사물들을 쉽게 찾을 수 있다는 잘못된 오해를 낳을 소지를 갖고 있다. ~ 열아홉 단계의 거리에 있는 노드에 도달할 때쯤이면 우리는 논리상 10 에 16승개의 문서들을 뒤져본 셈이 된다.

엄청난 문서가 있음에도 불구하고 우리는 생각보다 빠르게 문서를 찾아낸다. 트릭은 우리가 모든 링크를 다 따라가지 않는다는데 있다. 우리는 단서를 적절히 활용한다. pp68,69

이러한 비유클리드적 세계에는 새로운 기하학이 존재한다.

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

문제점 : 클러스터 모델은 인접한 클러스터 이외에 클러스터링 계수가 높아짐으로써 무작위적 세계에서의 small world가 사라짐

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

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

문제점 : 특정 노드가 평균적 노드에 비해 훨씬 많은 수의 링크를 갖는 것을 허용하지 않는 다는것

5. 허브와 커넥터 Hubs And Connectors

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

Random graphs에서는 종형(bell curve)그래프가 형성되는데 scale을 가진 정규 분포 이외의 노드가 생성될 가능성은 거의 제로에 가깝다.

hub와 connector의 생성 가능성은 멱함수 법칙(Power Law)의 도입으로 설명이 가능해지며, 멱함수의 도입은 불균등성(unevenness)를 인정해야 했다.

6. 80/20 법칙 The 80/20 Rule

웹에 대한 연구결과 파레토의 법칙에 따르는 power law 분포를 따른다.

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

7. 부익부 빈익빈 Rich Get Richer

웹을 통해서 보는 바와 같이 네트워크는 성장(growth)한다. 네트워크에 노드가 추가되면 각 노드들은 새로운 링크를 추가하는데 가장 오래된 노드가 링크 당할 기회를 가장 많이 갖는다.

하지만 이 속성만으로는 허브의 탄생을 설명하기는 부족하다. 그 크기가 너무 작고 수가 너무 적다.

그런데 웹상에서 어떤 사이트를 링크할 것인가를 결정함에 있어서 우리는 링크의 수가 많은 노드를 더욱 선호하는 경향이 있다. 즉, 우리는 허브(Hub)를 선호한다.

요컨대 웹상에서 어디를 링크할 것인가를 결정함에 있어서 우리는 선호적 연결(Preferential Attachment)이라는 방식을 따른다.

8. 아인슈타인의 유산 Einstein's Legacy

웹에서의 뉴 키즈 온더 블록(New Kids On The Block)효과의 존재

성장과 선호적 연결로만은 구글과 같이 후발 주자가 많은 링크를 획득하는 것이 어렵지만(선호적 연결은 네트워크에 일찍 진입한 노드가 링크를 획득할 가능성이 높다 이기 때문에)
 후발 주자가 허브로 성장하는 경우가 빈번하게 발생 되었다.

이를 설명하기 위해서 적합성모델 (Fitness Model)이 도입되었다.

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

적합성 = 적합도 * 링크수

각각의 노드의 에너지 준위가 다르다는 것을 인정

보즈 – 아인슈타인 응축물 : 모든 링크를 흡수하여 마이크로 소프트와 같은 star topology를 가지는 네트워크 모델이 존재 할 수 있음

9. 아킬레스건 Achilles' Heel

견고성(rubustness)와 취약성(weakness)

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

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

허브를 가진 클러스터 구조 이기 때문에 몇 개의 허브에 제거에 의해서 네트워크가 급격히 붕괴할 수 있는 취약성을 가지고 있다.

10. 바이러스와 유행 Viruses And Fads

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

11. 인터넷의 등장 The Awakening Internet
12. 웹의 분화 현상 The Fragmented Web

웹은 불평등한 세계이다. 새로 진입하는 당신의 웹페이지가 다른페이지에서 링크 되거나, 검색엔진에 의해서 인덱스 될 확률은 매우 적다.

웹은 지속적으로 성장하며, 그 노드수는 인덱스 할 수 없을 정도로 많으며, 검색엔진이 인덱스 하는 노드 수는 전체의 30%도 커버하지 못한다.

Nature 400, 107 (8 July 1999) | doi:10.1038/21987
Accessibility of information on the web
Steve Lawrence1 and C. Lee Giles1
1. Steve Lawrence and C. Lee Giles are at NEC Research Institute, 4 Independence Way, Princeton, New Jersey 08540, USA.
e-mail: Email: lawrence@research.nj.nec.com
Abstract
Search engines do not index sites equally, may not index new pages for months, and no engine indexes more than about 16% of the web. As the web becomes a major communications medium, the data on it must be made more accessible.

당신의 웹페이지가 인덱스 되거나 노출 될 수 있는 방법은 허브에 링크 되는 것

웹의 링크는 방향성을 가지며, 아래와 같이 네개의 대륙으로 표현 될 수 있다.
 

핫메일의 성공 비결
p346

대부분의 검색엔진은 웹 전체를 커버하려는 시도조차 하지 않는다. 그 이유는 단순한다. 가장 많은 검색결과를 가져다 주는 검색엔진이 반드시 최선의 것은 아니기 때문이다. ~ 아무리 단순한 질의에도 웬만한 검색엔진이라면 수천 건의 검색 결과를 보여주는 것에 우리는 익숙해져 있다 .여기에다 수백만 건을 추가 하는 것은 전혀 무의미한 일이다. p272

(99년 Steve Lawrence1 and C. Lee Giles의 논문 Accessibility of information on the web
에서 웹커버리지의 최고는 38%의 Northern Light라는 검색엔진이며,  구글은 18.6%에 지나지 않았으나  page rank (page and brin  - The Anatomy of a large-scale hypertextual web search engne  Publication: 1998)라는 알고리즘으로 최고의 검색엔진으로 평가 받고 있다. )

자신들에게 들어오는 링크가 많지 않다면 검색될  가능성은 거의 없다. 반면 허브는 시간이 갈수록 집중도가 더욱 높아지기 마련이다 . p288

많은 사람들이 내 웹페이지에 대해 흥미를 느끼고 링크를 연결시킨다면 나의 웹사이트는 소형 허브로 변해갈 것이고 검색엔진도 불원간 그것을 알아차리게 될 것이다. p289




이책을 읽는 목적은 복잡계의 네트워크를 이해하고 , 구글과 핫메일과 같은 사이트를 어떻게 만들어 낼 수 있을까 일 것이다.





참고자료

Graph Theory Tutorials :
 http://www.utm.edu/departments/math/graph/

에르되스-레니 Random Graphs
Random Graphs (Erdos-Renyi)


마크 그라노베터  :
THE STRENGTH OF WEAK TIES: A NETWORK THEORY REVISITED Mark Granovetter


Viral Marketing for the Real World.


Small World 구글링 :
http://www.google.co.kr/search?complete=1&hl=ko&newwindow=1&q=Duncan+Watts+small+world+filetype%3Apdf&lr=


FIRST-MOVER ADVANTAGES

Factors indicating first-mover advantages and second-mover advantages

키워드 정리 잘되어 있는 블로그 :
http://erehwon.egloos.com/70222


구글 , 페이지 and 브린
pagerank 알고리즘 번역 : http://2world.tistory.com/category/IT정보/검색엔진?page=3