4.1 소개
월드와이드맵의 연결 구조를 나타낸 그림을 살펴보면 무작위 네트워크에서는 고도로 연결된 노드 또는 허브가 있을 수 없는데, 링크수가 적은 노드와 수많은 노드가 공존함을 알 수 있다. 실제 네트워크의 링크수 분포를 탐구하면 척도 없는 네트워크를 발견하고 규정할 수 있다.
4.2 거듭제곱 법칙과 척도 네트워크
포아송분포는 월드와이드웹의 링크수 분포를 맞출 수 없어 월드와이드맵은 무작위 네트워크가 아니다.
대신, 분포 데이터가 로그-로그 척도에서 대략적인 직선을 형성하기에 월드와이드웹의 링크수 분포는 다음과 같이 근사될 것이라고 짐작할 수 있다.
월드와이드웹은 방향성 네트워크이므로, 각 문서는 해당 문서에서 연결되는 링크의 숫자인 나가는 링크수(k_out)과, 들어오는 링크수(k_in)을 구분해야 한다. 무작위로 선택한 문서가 k_out개의 웹 문서로 연결되어 있을 확률은 p_k_out이고, 무작위로 선택한 노드가 k_in 웹 문서로부터 연결되어 있을 확률은 p_k_in이다.
척도 없는 네트워크는 링크수 분포가 거듭제곱 법칙을 따르는 네트워크이다.
4.3 허브
무작위 네트워크와 척도 없는 네트워크의 주요 차이점은 p_k의 큰 k값 영역을 나타내는 영역인 링크수 분포에서 꼬리 부분에 존재한다.
>> k값이 크면 거듭제곱 법칙이 다시 포아송 곡선보다 더 위에 있게 되며, 이는 척도 없는 네트워크에서 링크수가 많은 노드 또는 허브를 관찰할 확률이 무작위 네트워크에 비해 수십배는 더 크다는 뜻이다.
4.3.1 가장 큰 허브
모든 실제 네트워크는 크기가 유한하다. 네트워크의 크기가 허브의 크기에 어떤 영향을 줄까?
이 질문의 답을 위해서는 링크수분포 pk의 자연 절단 이라고 하는 최대 링크수 k_max를 계산해야 하는데, 이는 네트워크에서 가장 큰 허브의 예상 크기를 뜻한다.
따라서 네트워크가클수록 가장 큰 허브의 링크수가 커진다. 이러한 k_max의 N에 대한 다항 함수 관계는, 큰 척도 없는 네트워크에서 가장 링크수가 적은 노드의 링크수 k_min과 가장 큰 허브의 링크수 k_max의 크기 차이가 수십배가 될 수도 있다.
즉, 무작위 네트워크에서는 허브가 사실상 있을 수 없지만 척도 없는 네트워크에서는 허브가 자연스럽게 존재한다.
무작위 네트워크와 척도 없는 네트워크의 핵심적인 차이는 poisson과 거듭제곱 함수의 모양이 달라서 생긴다.
4.4 척도 없음의 의미
척도 없다: 상전이 이론이라는 통계물리학의 한 분야로부터 기원한 것
해당 용어를 이해하기 위해서는 수 분포의 모멘트(moment)에 익숙해져야 한다.
링크수 분포의 n번째 moment는 다음과 같다.
척도 없는 많은 네트워크에서 링크수 자수 r은 2와 3 사이에 있다. 그럴 경우 N이 무한대로 발산하는 경우 첫번째 모멘트 <k>는 유한하지만 두번째 이상의 모멘트는 발산한다. 이러한 발산하는 특성이 척도 없다 라는 용어의 기원을 이해하는데 도움이 된다.
- 무작위 네트워크에는 규모가 있다.
- 무작위 네트워크의 노드는 비슷비슷한 링크수를 가지며 평균 링크수 <k>가 무작위 네트워크의 규모(scale) 역할을 한다
- 척도 없는 네트워크에는 규모가 없다
- r<3인 거듭제곱 법칙 링크수 분포를 따르는 네트워크의 경우 첫 번째 모멘트는 유한이지만 두 번째 모멘트는 무한하기에, 무작위로 노드를 선택한다면 어떤 링크수를 기대할 수 있는지를 알 수 없다.
즉, 척도 없다라는 이름은 정해진 내부 규모가 없다는 의미이며, 하나의 네트워크에 링크수가 매우 다른 노드들이 공존한다는 사실의 결과다. 이러한 특성이 네트워크의 견고성(robustness)에서 무작위 고장, 바이러스의 독특한 확산까지 척도 없는 네트워크의 가장 흥미로운 몇몇 속성의 원인이다.
4.5 보편성
월드와이드웹은 노드가 문서이고 링크가 URL인 정보 네트워크이고 인터넷은 노드가 라우터라고 하는 컴퓨터이고 링크가 구리 및 광 케이블과 같은 물리적 연결에 해당한다.
네트워크의 척도 유무를 어떻게 알 수 있을까?
- 링크수 분포를 간략히 살펴보면 네트워크의 척도가 없는지 여부를 즉시 알 수 있다. 척도 없는 네트워크에서는 가장 작은 노드와 가장 큰 노드의 링크수가 크게 다르며 종종 수십 배 이상 차이가 나낟. 반면, 이런 노드들이 무작위 네트워크에서는 비슷한 링크수를 가지게 된다. 링크수 지수의 값은 매우 중요하기에p_k분포를 맞추고 링크수 지수를 추정하는 도구가 필요하다.
- 링크수 분포 그리기
- 로그-로그 그림이라는 이중 로그 척도로 나타나는데, 이 책에 걸쳐 등장하는 깔끔한 링크수 분포를 얻기 위해서는 logarithmic binning이라는 로그 묶기를 사용해야 한다.
- 링크수 지수 측정하기
- 로그-로그 그림에서 p_k에 직선을 맞추면 링크수 지수의 추정치를 얻을 수 있지만, 이는 편향되어 있기 때문에 잘못된 r을 얻을 수 있다.
- 실제 네트워크에 대한 p_k의 모양
- 실제 네트워크에서 관찰되는 많은 링크수 분포는 순수한 거듭제곱 법칙에서는 벗어나 있다.
4.6 극단적인 좁은 세상 성질
척도 없는 네트워크에 허브가 있다는 것으로부터 허브가 좁은 세상 설질에 영향을 주는가 ? 라는 질문을 할 수 있다.
척도 없는 성질은 네트워크 거리에 다음과 같은 영향을 준다.
- 평균 경로 길이를 줄인다. 따라서 실질적으로 관심이 있는 대부분의 척도 업슨 네트워크는 좁을 뿐 아닌, 극단적으로 좁다.
- 시스템 크기에 대한 <d>의 의존성을 바꾼다. r이 작을수록 노드들 사이가 더 짧다.
- r>3인 경우에만 무작위 네트워크를 특징짓는 좁은 세상 성질의 특성인 lnN을 다시 얻게된다.
4.7 링크수 지수의 역할
척도 없는 네트워크의 많은 성질은 링크수 지수 r의 값에 따라 달라진다.
네트워크의 속성이 r에 따라 어떻게 변하는지 논의한다.
- 특이 영역 r<=2
- 이 경우, 가장 큰 허브에 연결되는 링크의 수가 네트워크 자체의 크기보다 빠르게 증가한다.
- 이것은 충분히 큰 N의 경우 가장 큰 허브의 링크수가 네트워크의 총 노드 수를 초과해야하므로 연결할 노드가 부족해진다.
- 즉, 이러한 사실은 다중 링크가 없는 r<2인 큰 척도 없는 네트워크는 존재할 수 없다는 사실을 알려준다.
- 척도 없는 영역 2<r<3
- 이 영역에서 링크수 분포의 첫 번째 모멘트는 유한하지만 두번째 이상의 모멘트는 N이 무한대로 수렴할 때 발산한다. 즉, 이 영역에서 척도 없는 네트워크는 극단적으로 좁다.
- 무작위 네트워크 영역 r>3
- 이 경우, 첫 번째 모멘트와, 두 번째 모멘트가 모두 유한하다. 현실적으로는 이 영역에서 척도 없는 네트워크의 성질을 비슷한 크기의 무작위 네트워크의 성질과 구별하기 어렵다.
- r이 큰 척도 없는 네트워크는 임의의 네트워크와 구별하기 어렵다. 실제로 거듭제곱 법칙 링크수 분포의 존재를 확신하기 위해, 수십에서 수천배의 크기에 걸쳐 살펴봐야 한다.
- k_max가 k_min보다 적어도 10^2 ~ 10^3배 커야 한다는 뜻이다.
4.8 임의의 링크수 분포를 가진 네트워크 만들기
에르되시 레니 모형으로 만든 네트워크에서는 Poisson 링크수 분포가 있다. 그러나, 실제 결과를 보면 실제 네트워크의 링크수 분포가 Poisson에서 크게 벗어나 있다. 이 절에서는 임의의 p_k를 가지는 네트워크를 만드는 방법으로 소개한다.
4.8.1 구조 모형
구조 모형(configuramtion model)은 미리 정의된 링크수 배열로 네트워크를 구축하는 것을 도와준다. 모형에 의해 생성된 네트워크에서 각 노드는 미리 정의된 링크수 k_i를 가지고, 그 제한조건 외에는 네트워크가 무작위로 연결된다.
미리 정의된 링크수 배열을 가지고 있는 무작위 네트워크 라고 부른다.
이 과정을 같은 링크수 배열에 반복적으로 적용ㅎ면 동일한 p_k를 가진 다른 네트워크를 생성할 수 있다.
4.8.2 이웃 수를 보존하는 무작위화
무작위로 연결되어 있지만 p_k는 원래 네트워크와 동일한 네트워크를 생성하는 것이 이웃수 보존 무작위화이다.
- 링크 2개를 무작위로 고른 다음 양쪽의 노드를 교체하는 것이 다중 링크가 되지 않으면 교체한다.
- 이때 교체 과정에 포함된 4개 노드각각의 링크수는 바뀌지 않는다.
결과적으로 ㅎ브는 허브로 유지되고 링크수가 작은 노드는 작은 링크수를 유지하지만 생성된 네트워크의 연결 구조는 무작위가 된다.
4.8.3 숨은 매개변수 모형
구조 모형에서 나타나는 단점인 자기 연결과 다중 링크를, 숨은 매개변수 모형(hidden parameter model)을 사용해, 미리 정의된 p_k가 있으면서도 다중 링크와 자기 연결이 없는 네트워크극 생성할 수 있다.
