5.1 소개
허브는 무작위 네트워크와 scale-free 네트워크의 가장 큰 차이이다.
허브의 존재와 관련된 척도 없는 법칙을 따르는 구조는 두가지 근본적인 질문을 제기한다.
- 왜 WWW나 세포처럼 상당히 다른 시스템이 비슷한 척도 없는 구조로 수렴하는가?
- 왜 에르되시와 레니의 무작위 네트워크 모형은 실제 네트워크에서 나타나는 허브와 거듭제곱 법칙을 재현하지 못할까?
WWW와 세포처럼 다른 시스템이 왜 비슷한 구조에 수렴하는지 이해하기 위해서 척도 없는 특성을 발현시키는 기작을 이해해야 한다.
위 질문에 대한 답이 5장에서의 핵심 주제이다.
5.2 성장과 선호적 연결
"왜 허브와 거듭제곱 법칙이 무작위 네트워크에서는 발현되지 않는가?"
이 질문은 에르되시-레니 모형을 실제 네트워크와 다르게 하는 숨겨진 두가지 가정을 재조명하며 1999년 대두되었다.
- 가정 1: 새로운 노드의 추가를 통해 확장되는 네트워크
- 에르되시-레니 무작위 네트워크 모형은 노드의 수 N이 고정되어 있다고 가정하지만, 실제 네트워크에서 노드의 수는 새로운 노드가 추가되며 끊임없이 증가한다. 즉, 정적인 모형에 의지하면 안된다.
- 가정 2: 노드는 더 많이 연결되어 있는 노드와 연결되는 것을 서호한다.
- 무작위 네트워크 모형은 노드가 상호작용할 대상을 무작위로 선택한다고 가정하지만, 대부분의 실제 네트워크에서 새로운 노드는 더 많이 연결된 노드와 연결되는 것을 선호하는데, 이를 선호적 연결(prefernetial attachment)라고 한다.
즉, <성장>, <선호적 연결> 이 실제 네트워크와 무작위 네트워크 모형의 차이를 의미한다. 이 두가지 특성이 네트워크의 링크수 분포를 형성하는데 중요한 역할을 한다.
5.3 바라바시-알버트 모형(Barabasi-Albert mode)
실제 네트워크에서 성장과 선호적 연결이 동시에 존재하는 사실이 BA 모형(바라바시-알버트 모형: 척도 없는 모형: scale-free model).
정의는 다음과 같다
: m_0개의 노드에서 시작하며 링크는 임의로 선택된다. 다만, 각 노드는 최소한 하나의 링크를 가지도록 한다.
선호적 연결은 확률 연결과정으로 새로운 노드는 허브든 링크가 하나뿐인 노드든 상관없이 네트워크에 존재하는 어떤 노드와도 연결될 수 있다. 하지만, 링크수가 더 높은 노드에 연결될 확률이 높다는 것을 의미한다.
바라바시-알버트 모형은 t time step이 지났을 때, 노드 개수가 N = t + m_0(시작 노드 수) 이고 링크수가 m_0 + m*t개인 네트워크를 만들고 이는 거듭제곱 링크수 분포를 가진다.
이를 통해 부익부 현상(rich-gets-richer phenomenon)의 결과로 더 큰 노드는 더 작은 노드의 희생으로 최종적으로 허브가 된다.
바라바시 -알버트 모형은 <성장>과 <선호적 연결>을 통해 척도 없는 특징을 가지고, 허브는 부익부 현상으로 생겨난다. 이를 정량화하기 위해 수학적으로 증명한다.
5.4 링크수 동역학
척도 없는 특성의 출현을 이해하기 위해, 바라바시-알버트 모형에서 하나의 노드와 연결된 링크수가 시간에 따라 어떻게 달라지는지 알아보면서 시작한다.
모형에 이미 존재하던 노드는 새로운 노드가 네트워크로 유입될 때마다 링크수를 증가시킬 수 있다.
K_i(t)의 의미
- 각 노드의 링크수는 B = 1/2를 따르는 거듭제곱 법칙으로 증가한다.
- 링크수 증가는 sublinear(B<1)이다. 이는 바라바시-알버트 모형의 성장 특성의 결과로, 개별 노드는 이전 노드보다 연결할 수 있는 더 많은 노드를 가진다. 즉, 이미 존재하는 노드들은 증가한 다른 노드들과 링크를 얻기 위해 경쟁해야 한다.
- 노드 i가 먼저 유입될수록, 그 링크수 k_i(T)는 더 많아진다. 선발자 이익(first-mover-adavtage)라고 부른다.
즉, 바라바시-알버트 모형은 실제 네트워크에서 노드가 하나씩 유입된다는 사실을 바탕으로 네트워크 진화를 동적으로 묘사하고, 더 오래된 노드들이 젊은 노드 대비 이점을 가진다.
네트워크에서의 시간
네트워크 이론에서는 사건 시간(event time)을 사용해, 네트워크 구조에 변화가 있을 때 시간을 1씩 증가시킨다. 예를 들어 바라바시-알버트 모형에서는 새로운 노드의 추가가 새로운 시간 단위에 해당해 t = N이 된다.
5.5 링크수 분포
바라바시-알버트 모형으로 만들어진 네트워크의 뚜련한 특징은 이 네트워크들이 거듭제곱 법칙을 따르는 링크수 분포를 가진다는 것.
p_k를 함수 형태로 유도하며 거듭제곱의 근원을 알아본다.
즉, 바라바시-알버트 모형이 링크수 지수 r = 3인 scale-free network 만들고, 이 링크수 지수 r은 m과 m_0에 대해 독립적이다. 또한, 링크수 분포는 시간과 무관한 stationary함의 결과로, 왜 서로 다른 역사, 크기, 나이의 네트워크가 비슷한 링크수 분포를 발전시키는지 설명한다.
5.6 성장 혹은 선호적 연결의 부재
바라바시-알버트 모형에서 성장과 선호적 연결의 공존ㅇ에서 다음과 같은 질문이 제기된다.
척도 없는 특성이 발현되기 위해, 이 두가지는 필수적인가? 이 두 용소 중 하나만으로는 척도 없는 네트워크를 만들 수 없는가?
두 요소 중 하나만 가지는 바라바시-알버트 모형의 두가지 제한된 경우에 대해 논의한다.
5.6.1 모형 A
선호적 연결의 역할을 시험하기 위해, 성장 요소는 유지하고, 선호적 연결은 제거한다.
즉, 모형 A는 m_0개의 노드로 시작하고, 다음의 단계를 거치며 성장한다.
성장
각 단계마다 m(<= m_0)개의 링크를 가지는 새로운 노드를 추가하며, 이 링크들은 이전부터 존재했던 m개의 노드와 연결된다.
선호적 연결
결과적으로 링크수 분포는 지수함수를 따르고, 이 형태의 함수는 거듭제곱보다 훨씬 빠르게 감소하기에 허ㄹ브를 뒷받침할 수 없다. 즉, 선호적 연결의 부재는 네트워크의 척도 없는 성질과 허브를 만들지 못한다.
5.6.2 모형 B
성장의 역할을 알아보기 위해, 선호적 연결은 유지하고, 성장을 제거한다.
선호적 연결
각 단계마다 임의의 노드가 무작위로 선택되어, 이미 네트워크에 존재하는 링크수가 k_i인 노드 i와 연결된다. 이때 i는 확률 파이(k)를 따라 선택된다.
여기서 노드의 개수는 네트워크가 성장하는 과정에서 상수로 유지되지만, 리이크의 개수는 선형적으로 증가하고, 결과적으로 아주 오랜 시간 t가 지나면 개별 노드의 링크수 또한 시간에 대해 선형적으로 증가한다.
선호적 연결의 부재는 고정적이지만 지수함수적 링크수 분포를 가지는 성장하는 네트워크를 만든다.
성장의 부재는 정상성을 잃게하며, 네트워크를 완전 네트워크로 수렴시킨다.
5.7 선호적 연결 측정하기
성장과 선호적 연결이 척도 없는 특성에 동시적으로 요구된다. 선호적 연결이 실제 네트워크에 존재함을 설득하려면, 선호적 연결을 실험적으로 발견해야 한다. 이번 절에서는 실제 네트워크에서 파이(k)를 측정해 선호적 연결을 발견하는 방법을 소개한다.
선호적 연결은 다음 두 가정에 의존한다.
- 임의의 노드와 연결할 가능성은 그 노드의 링크수 k에 의존한다. 이는 무작위 네트워크 모형과 구분되는 부분으로, 무작위 모형에서 파이(k)는 k에 무관하다.
- 확률 파이(k)는 k에 선형적인 함수 형태를 가진다.
인터넷과 인용 네트워크에서 a 는 1에 근사하기에 k에 선형적으로 알 수 있다.
즉, 이 식을 통해 실제 네트워크에서 선호적 연결의 존재를 탐지할 수 있다. 이 측정은 연결 확률이 노드의 링ㅋ으수에 의존한다는 사실을 보인다.
이 선호적 연결이 선형성, 비선형성을 모두 보일 수 도있다.
5.8 비선형 선호적 연결
지수 a에 따라 네트워크 구조가 변한다.
지구 a = 0일 때 링크수 분포는 지수함수 형태가 되고, 지수 a = 1일때는 바라바시-알버트 모형으로 된다.
- 0<a<1
- a>0에서 새로운 노드는 연결이 적은 노드보다 더 많이 연결된 노드를 선호한다.
- a<1일 경우 이러한 편향이 약해서 척도 없는 링크수 분포를 만들기에 충분하지 않다.
- 준선형 선호적 연결은 가장 큰 링크수 k_max의 크기도 변환시킨다.
- 결국, 이를 통해 허브의 크기를 제한할 수 있다.
- a>1
- 연결이 잘된 노드와 연결하려는 경향은 이때 더 강화되어 부익부 과정을 가속시킨다.
- a>2의 경우 거의 모든 노드가 아주 적은 슈퍼 허브, 승자독식과 연결된다.
5.9 선호적 연결의 근원
실제 네트워크의 진화에 있어 선호적 연결이 핵심적인 역할을 하는걸 고려할 때, 이 선호적 연결이 어디서 왔는가?
- 왜 파이(k)는 k에 의존하는가?
- 왜 파이(k)의 k에 대한 의존도는 선형적인가?
이에 대한 철학적으로 두가지 답이 제시됐다.
- 선호적 연결을 무작위적 사건과 몇몇 네트워크의 구조적 특성 사이의 상호작용으로 바라본다.
- 이 매커니즘은 네트워크 전반의 지식이 요구되지는 않지만, 무작위적 사건에 대한 지식은 요구한다. > local, random 매커니즘이라고 한다.
- 각각의 새로운 노드 혹은 링크가 경쟁하는 필요의 균형을 맞춘다고 가정한다.
- 이는 비용 편익 분석 >> global, optimized 매커니즘
5.9.1 local 매커니즘
바라바시-알버트 모형은 선호적 연결의 존재를 사실이라 가정하지만, 선호적 연결 없이도 척도 없는 네트워크를 만들 수 있다. 이는 선호적 연결을 generating해서 이뤄진다.
5.9.2 링크 선택 모형(link-selection model)
선호적 연결 없이 척도 없는 네트워크를 만들 수 있는 국소 메커니즘의 예 중 가장 단순한 형태
다음과 같이 정의된다.
- 성장: 시간 단계마다 네트워크에 새로운 노드를 추가한다.
- 링크 선택: 링크를 무작위로 선정하고, 이 링크의 양 끝에 있는 노드 중 하나의 노드와 새로운 노드를 연결한다.
이 모형은 네트워크에 대한 지식을전혀 요구하지 않고, 무작위적이다. 그리고 파이(k)함수가 없지만 선호적 연결을 만들어낼 수 있다.
식 5.26은 한 노드의 링크수가 많을수록, 그 노드가 선택된 링크의 한쪽 끝에 위치할 가능성이 높다, 네트워크에 링크수가 k인 노드가 많을수록 링크의 한쪽 끝에 링크수가 k인 노드가 존재할 가능성이 높다.
마지막 식은 새로운 노드가 링크수 k인 노드와 연결될 확률로 선형 선호적 연결을 통해 척도 없는 네트워크를 만들 수 있음을 보여준다.
5.9.3 복제 모형
복제 모형이 국소 메커니즘을 따르는 모형들 중 가장 대중적인 모형이다.
각 단계마다 새로운 노드가 네트워크에 추가된다. 누구와 연결할지 선택할 때 노드 u를 무작위로 선택한다. 예컨대, 샐운 노드의 콘텐츠와 관련 있는 콘텐츠를 갖는 웹 문서와 연결하는 식이다.
- 무작위 연결: 확률 p로 새로운 노드가 u와 연결된다. 즉, 무작위로 선택된 웹 문서와 연결하는 것
- 복제: 1-p의 확률로 노드 u에서 나가는 링크(outgoing link)를 무작위로 선택하고, 새로운 노드와 서낵한 링크의 목표 노드를 연결한다. 즉, 새로운 웹 페이지가 노드 u와 바로 연결되는것이 아닌, 노드 u의 링크를 복제하여 노드 u의 링크가 목표한 노드와 연결되는 것이다.
이 모형이 사회 현상을 나타내기가 좋다.
즉, 링크 선택 모형과 복제 모형이 무작위 연결을 통한 선형 선호적 연결을 만들어 낸다.
5.9.4 최적화
비용, 상황 등을 모두 고려해 각각의 새로운 링크들은 심도있는 비용 편익 분석을 진행해야 한다.
단위 정사각형의 지형에 모든 노드가 위치해 있다고 가정한다. 각 시간 단계마다, 정사각형에서 임의로 한 지점을 선택해 노드의 물리적 위치를 정해서 추가한다. 새로운 노드 i를 누구와 연결할지 결정할 대는 다음의 비용 함수를 계산한다.
매개변수 피와 N에 의존해 네트워크는 세가지 구조를 가질 수 있다.
- 별모양 네트워크(피 < (1/2)^(1/2))
- 기하학적 거리는 피 = 0 일 경우 상관 없고, 각 노드는 모두 종심 노드와 연결되어 네트워크는 별 모양으로 변한다.
- 무작위 네트워크(피 > N^(1/2))
- 아주 큰 피의 경우, 네트워크는 무작위 네트워크처럼 제한적인 리ㅇ크수 분포를 가진다.
- 척도 없는 네트워크(4 < 피 < N^1/2)
- 중간 정도의 피 값이 척도 없는 특성을 가지는 네트워크를 만들 수 있다. 거듭제곱 분포의 근원은 두가지 경쟁 매커니즘에서 나온다.
- 최적화 : 각 노드는 끌림 영역을 가지기에 이 영역에 도달하는 노드는 항상 해당 노드와 연결한다.
- 무작위성: 새로운 노드의 위치를 무작위로 선택하는데, 이는 N개의 끌림 영역 중 하나에 속하게 된다. 가장 큰 링크수를 가지는 노드는 가장 큰 끌림 영역을 가지며, 이를 통해 대부분의 노드와 링크를 얻는다.
- 중간 정도의 피 값이 척도 없는 특성을 가지는 네트워크를 만들 수 있다. 거듭제곱 분포의 근원은 두가지 경쟁 매커니즘에서 나온다.
5.10 지름과 뭉침계수
지름은 ln N보다 천천히 증가하여, 바라바시-알버트 모형에서의 거리를 비슷한 크기인 무작위 네트워크에서의 거리보다 작게 만든다.
바라바시-알버트-네트워크는 무작위 네트워크보다 국소적으로 뭉침이 더 많이 나타난다.
