3.2 무작위 네트워크 모형
네트워크 과학은 실제 네트워크의 특성을 재현하는 모형을 만드는 것을 목적으로 한다.
하지만, 대부분의 네트워크는 규칙성이 없다.
무작위 네트워크 이론은 진정한 무작위성이 있는 네트워크를 만들고 특징지어서, 이런 명백한 우연성을 포괄한다.
무작의 네트워크는 모든 노드 사이에 확률 p로 연결된 N개의 노드로 구성한다.
무작위 네트워크(무작위 그래프) 구성 방법
- N개의 고립된 노드로 시작
- 노드 쌍을 하나 고르고 0~1사이의 무작위 수를 하나 만든다. 이 무작위 수가 p보다 작다면 노드 쌍을 연결하고, 아니면 끊는다.
- 2번 과정을 모든 N(N-1)/2개의 노드 쌍에서 반복
3.3 링크의 수
같은 매개변수 N,p로 만든 무작위 네트워크들은 서로 조금씩 다르고 총 링크의 수 L또한 달라진다.
그렇기에 고정된 매개변수 p와 N에 따라 총 링크 수의 기대값을 구하면 유용하다.
즉, 무작위 네트워크는 생성 할 때마다 전체 링크 수가 달라지며, 총 링크 수의 기댓값은 N과 p가 결정한다.
총 링크 수의 평균값은 <L> = 0부터 L_max까지 선형으로 증가하고, 노드의 평균 링크 수 또한 <k> = 에서 <k> = N-1로 선형적으로 증가한다.
총 링크 수의 평균: p * L_max(가능한 모든 링크 수) = p * (N(N-1))/2
무작위 네트워크의 평균 링크 수 <k> = p * (N-1)
3.4 링크 수 분포
무작위 네트워크의 생성한 결과물이 있을 때 어떤 노드는 링크가 많고, 어떤 노드는 링크가 아주 적거나 없을 수 ㅣㅇㅆ다. 이러한 차이는 무작위로 고른 노드의 링크 수가 k일 확률을 나타내는 링크수 분포 p_k로 나타낼 수 있다.
3.4.1 이항 분포
무작위 네트워크에서 노드 i의 링크수가 정확히 k개일 확률은 다음과 같은 세가지 항의 곱이다.
3.4.2 포아송분포
이항 분포 B(n,p)에서 n이 충분히 크고 p가 충분히 작을 떄, 이항 분포는 포아송 분포에 근사한다.
대부분의 현실 네트워크는 <k> << N으로 Sparse 하기에 이항 분포인 링크 수 분포가 Poisson 분포로 근사된다.
무작위 네트워크의 링크 수 분포는 2가지이다.
- 이항 분포에서
- 이항 분포를 근사시킨 포아성 분포에서
- 두 분포 모두 <k> 근처에서 최고점이 있다. p를 증가시켜 네트워크를 빽빽하게 만들면 <k>가 증가하고, 최고점이 오른쪽으로 이동한다.
- p나 <k>로 폭(분산)을 조절한다. 네트워크가 뺵빽할수록 분포가 더 넓어지고 링크수의 차이가 더 커진다.
즉, 포아송분포는 무작위 네트워크 인용 수 분포의 근사치이지만, 해석적으로 간편하므로 대부분 포아송 분포를 사용한다. 이 분포는 , 단일 매개변수인 평균 링크 수 <k>에만 의존한다는 특징이 있다.
3.5 실제 네트워크는 포아송 분포가 아니다.
무작위 네트워크에서는 한 노드의 링크수가 0부터 N-1까지 변할 수 있기에, 구축한 네트워크 하나에서 노드의 링크수 사이에 차이가 얼마나 큰지 확인해야 한다.
즉, ""링크수가 많은 노드가 링크수가 적은 노드와 공존하고 있을까?"" 라는 질문을 바탕으로 무작위 네트워크에서 가장 큰 노드와 가장 작은 노드의 크기를 추정해 질문에 답해야 한다.
세계의 사회 연결망이 무작위 네트워크로 설명된다고 가정했을 때, 큰 무작위 네트워크에서는 대부분 노드의 링크수가 <k> 근처에 몰려있다. 라는 무작위 네트워크의 중요한 성질에서 온다.
불일치의 기원을 이해하려면 현실 네트워크와 무작위 네트워크의 링크 수 분포를 비교해야 한다.
이떄, 포아송 추정이 많은 노드의 수를 과소평가하기에 무작위 네트워크 모형은 실제 데이터와 비교해서 현실 네트워크의 링크 수 분포를 잡아내지 못한다는 단점이 있다.
3.6 무작위 네트워크의 점진적 변화
p의 점진적인 증가는, 네트워크 구조에 놀라운 결과를 가져온다. 네트워크 안의 거대 덩어리의 크리 N_G가 <k>에 따라 변하는 과정을 생각해본다.
다음은 두가지 극단적인 상황이다.
- p = 0일 때 <k> = 0이 되므로 노드는 고립된 상태이고, 이때 거대 덩어리 N_G = 1이고, 큰 N에서는 N_G/N은 0으로 수렴한다.
- p = 1일 때 <k> = N-1이 되므로 완전 그래프이고, 모든 노드는 거대 덩어리에 속하고, N_G = N이고 N_G/N은 1이다
<k> = 0 부터 N-1로 커질 때, 거대 덩어리는 점진적으로 커지는게 아니라, <k>가 작을 떄는 0으로 있으며, <k>가 임계값을 넘어서면 거대 덩어리라고 나타나는 큰 덩어리가 빠르게 증가한다.
즉, 각 노드에 평균적으로 하나 이상의 링크가 있을 때, 거대 덩어리가 나타난다.
이를 통해,
- 준임계 영역(0<(k)<1,p<1/N)
- 임계점(<k> = 1, p = 1/N)
- 임계점에서 대부분의 노드는 크기 분포를 따르는 수많은 작은 덩어리에 속하지만, 준임계 영역 대비 몇십만배 커진다.
- 초임계 영역(<k> >1 , p>1/N)
- 실제 시스템과 관련이 가장 깊고, 처음으로 네트워크처럼 보이는 덩어리가 생겨난다.
- 수많은 고립된 덩어리와 거대 덩어리가 공존하고, 작은 덩어리는 트리 구조인 반면, 거대 덩어리는 고리와 순환 구조를 가지고 있다.
- 연결 영역(<k>>ln N, p>ln N / N)
- p가 충분히 클 떄, 거대 덩어리는 모든 노드와 덩어리를 흡수하고, 이때 평균 링크수는 ln N이다.
- 이때 <k> = N-1일 때만 완전 그래프이다.
3.7 실제 네트워크는 초임계성을 보인다.
- 일단 평균 링크수가 <k> = 1을 넘어가면, 전체 노드의 유한한 부분집합이 속한 거대 덩어리는 꼭 나타난다. 즉, <k> >1일 떄만 네트워크로 인식할 수 있는 형태가 된다.
- <k> < ln N이면 모든 덩어리는 거대 덩어리에 흡수돼서 1개의 연결된 네트워크가 된다.
" <k> > 1" : 현실 네트워크에서 거대 덩어리의 존재 기준
대부분의 현실 네트워크는 초임계 영역에 있다. 그러므로 이런 네트워크는 거대 덩어리가 있을 것으로 예상할 수 있고, 관측 결과 역시 그렇다. 하지만, 이런 거대 덩어리는 분리된 많은 덩어리와 공존하므로, 현실 네트워크가 무작위일 때만 옳다.
뒤에 나올 현실 네트워크의 구조를 공부할 떄, 조건 <k> > ln N에는 도달하지 못했지만 연결된 상태인 이유에 대해 이해할 수 있다.
3.8 좁은 세상
여섯 단계 분리: 지구상에 어디에 있든지 두 사람은 6명 이하의 지인으로 이어진 사슬로 연결되나.
이 좁은 세상 이론은 네트워크에서 무작위로 고른 두 노드 사이의 거리가 짧다.
d_max = ln N / ln <k>
- d_max 보다는 평균 거리 <d>와 더 잘 맞는다.
- 따라서 <d> ~ ln N / ln<k> 로 나타낼 수 있다.
- 일반적으로 ln N << N 이므로, ln N에 대한 <d>의 의존성은 무작위 네트워크의 거리가 네트워크의 크기보다 자릿수가 작다는 것을 의미한다. 결과적으로 좁은 세상 현상에서 작다는 것은 평균 거리 또는 지름이 시스템 크기에 로그로 의존한다는 뜻이다.
- 따라서, 작다는 것은 <d>가 N의 수 제곱에 비례하는 것이 아닌, ln N에 비례하는 것을 의미한다.
좁은 세상 현상은 노드에서 거리 d만큼 떨어진 노드의 수가 d에 따라서 기하급수적으로 증가한다는 사실에 뿌리를 두고,
위 식의 결과와 현실 네트워크가 편차가 있기에 더 정확한 예측으로 대처해야 한다.
3.9 뭉침 계수
위의 식 C_i는 두가지 예측을 제시한다.
- <k>가 고정되면 네트워크가 클수록 노드의 뭉침 계수가 작아져 노드의 국소 뭉침 계수 Ci는 1/N에 비례한다.
- 국소 뭉침 계수는 노드의 링크수와 무관하다.
하지만, 무작위 네트워크 모형은 실제 네트워크의 뭉침을 제대로 잡아내지 못한다. 대신, 실제 네트워크는 유사한 N과 L로 구성한 무작위 네트워크에서 예상하는 것보다 뭉침계수가 훨씬 더 크다.
3.10 정리: 실제 네트워크는 무작위가 아니다.
실제로 대부분의 복잡계 뒤에는 심오한 질서가 있다고 의심한다. 무작위 네트워크가 현실 시스템을 얼마나 잘 설명하는가의 정도는 단순한 인식론적 주장이 아니라 체계적인 정량적 비교로 결정해야 한다.
- 링크 수 분포
- 무작위 네트워크의 링크 수 분포는 이항 분포이며 k << N인 극한에서 포아송 분포로 잘 근사되지만, 이는 현실 시스템 네트어크의 링크수 분포를 포착하지 못한다.
- 연결상태
- <k> >1이면 거대 덩어리가 있어야 하는데, 이는 거의 만족시킨다. 하지만, 대부분 네트워크는 <k> > ln N을 충족히키지 않고, 대부분 쪼개지지 않은상태로 존재한다.
- 평균 경로 길이
- 무작위 네트워크 이론은 평균 경로 길이가 예측을 따를 것이고, 이 경로 길이에 대해 합리적인 근사치를 제공한다.
- 뭉침 계수
- 현실 네트워크에서 C(k)는 노드의 링크수가 증가하면 감소하고 시스템의 크기에는 무관하다.
이러한 모형은 실제 네트워크의 속성을 탐색할 때 참고자료 역할을 하고 여전히 중요한 관련성이 있다.
해당 게시물은 알버트 라슬로 바라바시,"네트워크 사이언스", 이미지 등 교재를 바탕으로 작성된 글입니다.
3.12.1 포아송 분포의 유도 과정
3.13 최대 링크수와 최소 링크수
무작위 네트워크에서 노드의 가장 큰 링크수를 찾기 위해서는, N개 노드로 구성한 네트워크에서 k_max보다 링크수가 큰 노드가 최대 1개만 있도록 하는 링크수인 k_max를 정의해야 한다.
3.14 거대 덩어리
거대 덩어리의 시작 시점이 <k> = 1인 이유를 설명한다.
