1. 소개
유명인들이 유명인들과 만나는 것 처럼 허브는 다른 허브와 연결하는 경향이 있다.
하지만 모든 네트워크에서 이 성질이 나타나는 것이 아니다. 효모의 단백질 상호작용 네트워크에서는 scale-free 성질을 가지고 링크수가 1이나 2인 수많은 단백질이 소수의 많은 연결을 가진 허브와 공존한다. 그런데 이 허브들은 서로 연결하는 것을 피하고, 링크수가 작은 노드와 연결됨으로써 허브-바큇살 구조를 생성한다.
링크수인 k와 k'이 클수록 확률이 커진다. 하지만, 단백질 네트워크에서 허브 사이에는 링크가 없다. 반대로 링크수가 작은 노드 사이에는 수많은 링크가 있다.
즉, 요약하면 사회연결망에서 허브들은 서로 데이트하는 경향이 있지만 단백질 상호작용 네트워크에서는 그 반대이다.
이는 링크수 상관관계 Degree correlation이라는 현상으로 설명이 가능하다.
2. 끼리끼리 반대끼리
이렇게 많은 링크를 가졌다는 것만으로 허브는 서로 연결될 가능성이 높고, 어떤 네트워크에서는 그렇지 않다. 다음 세가지 같은 링크수 배열을 가진 네트워크에서 확인 가능하다.
- 중립 네트워크:
- 연결이 무작위인 네트워크: 허브 사이의 링크수가 무작위 연결을 의미하는 식 7.1이 예측한 그대로 나온다.
- 끼리끼리 네트워크.
- 여기서는 링크수분포는 같지만, 허브끼리 연결하려는 경향이 있고 링크수가 작은 노드는 피한다. 또한, 링크수가 작은 노드 역시 서로 연결하는 경향이 있다.
- 이를 assortative(끼리끼리)라고 부른다.
- 이 패턴의 극단은 링크수가 k인 노드는 링크수가 k인 노드하고만 연결된다.
- 반대끼리 네트워크
- 여기서는 허브는 서로 피하고 링크수가 작은 노드와 연결한다.
- dissortative 성질을 가진다.
일반적으로 링크수가 높은 노드와 링크수가 낮은 노드를 잇는 링크의 개수가 우연에 의한 기댓값과 체계적으로 다르면 네트워크가 링크수 상관관계(Degree Correlation)을 가진다고 할 수 있다.
즉, 링크수가 k인 노드와 k'인 노드 사이의 링크수가 7.1과 다른경우.
e_ij가 7.5와 다르면 링크수 상관관계가 있다는 것이다.
중립 네트워크에서 e_ij는 특별한 경향을 보이지 않지만, assortive network에서 주대각선을 따라 높은 상관관계를 보이는데 이는 비슷한 링크수를 가진 노드의 연결이 우세하다는 것을 의미한다. 반대로 disassortive network에서는 부대각선을 따라 높은 상관관계를 보이며 큰 링크수를 가지는 노드가 작은 링크수를 연결하려는 경향을 띈다.
하지만 e_ij를 이용해 링크수 상관관계를 연구할 때는 다음과 같은 약점이 있다.
- 행렬을 시각화해 정보얻기 어렵다.
- 상관관계의 크기를 유추할 수 없고 네트워크끼리 비교하기도 어렵다.
- 정보량이 너무 많다.
링크수 상관관계를 찾아낼 더 간결한 방법을 발전시켜야 한다. 7.3에서 진행할 것.
7.3 링크수 상관관계 측정하기
e_ij를 완전히 해석하는 것은 어렵고 링크수 상관관계를 정량화하는 링크수 상관 함수를 소개한다.
링크수 상관관계는 연결된 노드들의 링크수 사이의 관계를 잡아낸다. 크기를 재는 법중 하나는 각 노드 i에 대해 그 이웃들의 링크수의 평균을 구하는 것이다.
k_nn(k)가 k에 어떻게 의존하는지 확인하고 링크수 상관관계를 정량화할 수 있다.
- 중립 네트워크
즉, 중립 네트워크에서 노드의 이웃들의 평균 링크수는 네트워크의 전체 성질인 <k>와 <k^2\>에 의존한다.
즉, k_nn(k)를 k의 함수로 시각화하면 <k^2>/<k>에 해당하는 수평선이 나와야 하고, 이는 전력망에서 관찰할 수 있다.
우리의 친구는 우리보다 더 인기가 많다고 하는 친구관계 역설(friendship paradox)이다.(허브의 링크수가 많기 때문에 우리는 링크수가 작은 노드보다 허브와 친구가 될 가능성이 높은 것)
- assortive network
여기서 허브는 다른 허브와 연결되는 경향이 있고, 링크수 k가 큰 노드일수록 그 노드의 이웃들의 평균 링크수도 커져 k_nn(k)는 k의 증가함수이고, 과학 공동연구 네트워크에서 관찰할 수 있다.
- disassortive network
k_nn(k)는 k에 대한 감소함수이다.
즉, 링크수 상관함수는 실제 네트워크에서 상관관계 여부를 잡아내는데 도움을 주고, 링크수 상관관계가 다양한 네트워크 특성에 미치는 영향을 예측할 수 있게 해준다.
7.4 구조적 절단
이 책에서 네트워크는 단순하다고 가저아고, 두 노드 사이에 있을 수 있는 링크는 최대 1개만 가능하다.
하지만 scale-free와 링크수 상관관계 사이에는 모순이 있다.
7.15보다 큰 링크수를 가진 노드들에 대해서 E_kk' >1이 되며, 이 때문에 링크수 상관관계가 발생한다.
구조적 절단의 결과를 이해하기 위해 네트워크에 7.15보다 큰 링크수를 가진 노드가 있는지를 물어야 한다. 이를 위해 구조적 절단 k_s와 네트워크에서 기대되는 최대 링크수인 k_max를 비교한다. k_s와 k_max를 비교해 두 영역을 구분할 수 있다.
(k_max ~ N^(1/(r-1)))
- 구조적 절단이 없는 경우
- r>=3인 scale-free network와 무작위 네트워크의 경우 k_max의 지수가 1/2보다 작아 k_s보다 언제나 작다.
- 즉, 구조적 절단이 나타나기 위한 링크수가 가장 큰 허브의 링크수를 능가하고, E_kk'>1에 해당하는 노드는 없다.
- 구조적 반대끼리
- r<3인 scale-free network의 경우 1/(r-1) > 1/2가 되여 k_s가 k_max보다 작을 수 있다.
- 즉, 허브 사이에는 E_kk' 로 예측하는 것보다 링크가 더 적게 나타나 네트워크는 반대끼리 성지를 가진다.
- 구조적 반대끼리: structural disassortativity, ( 허브는 서로 피하고 링크수가 작은 노드ㄱ끼리 연결
- 구조적 반대끼리 없는 네트워크 생성하는법
- 단순 네트워크 조건을 완화해 노드 사이에 여러개 링크 존재하도록
- 중립이거나 끼리끼리인 scale-free network를 유지하려면 k_s보다 링크수가 큰 허브를 전부 없애야 한다.
특정한 네트워크에서 관찰한 상관관계가 structural disassortativity의 결과인지, 아니면 링크수 상관관계를 야기하는 어떤 알려지지 않은 과정의 결과인지 아는법: 이웃수 보존 무작위섞기
이웃수 보존 무작위 섞기(Randomization)
즉, 무작위 섞기를 해서 링크수 상관함수가 계속 똑같다면, 링크수분포로 상관관계를 완전히 이해할 수 있지만, 바뀐다면, 알려지지 않은 과정(구조적 절단)의 결과라고 생각할 수 있다.
1. 단순 링크만 허용하는 이웃수 보존 무작위 섞기(Randomization with Simple Links)
원래 네트워크의 링크수를 보존하며 무작위로 섞는 과정에서 각 단계에서 두 노드 사이에 1개보다 많은 노드를 허용하지 않는다.
즉, 다중링크를 생성하는 링크 재연결 시도를 무시한다는 것을 의미한다. 실제 k_nn(k) (링크수 상관함수)와 무작위로 섞은 후의 링크수 상관함수를 구별할 수 없다면, 실제 시스템에서 관찰한 상관관계는 모두 구조적이며, 링크수 분포로 완전히 이해할 수 있다.
2. 다중 링크를 허용하는 이웃수 보존 무작위 섞기 (Randomization with Multi Links)
이 과정은 링크수 상관관계를 완전히 무시한다.
요약하자면, scale-free 성질은 단순 네트워크의 반대끼리 성질을 야기할 수 있다. 실제로 중립 네트워크나 끼리끼리 네트워크에서는 허브 사이의 여러개의 링크를 기대한다.
하지만, 단순 네트워크에서 다중 링크가 금지돠면 네트워크는 반대끼리 경향을 보인다. 이런 대립은 r>=3인 scale-free network나 무작위 네트워크에서는 사라지고, 노드 사이에 다중 링크를 허용해도 사라진다.
(단일 링크, r<3인 scale-free network에서 반대끼리(structural disassortativity) 성질이 나타난다.)
>> 이거의 예시를 7.5에서 설명
7.5 실제 네트워크의 상관관계
끼리끼리: 링크수 k가 클수록 노드의 이웃들의 평균 링크수도 커진다.
반대끼리: 링크수 k가 클수록 노드의 이웃들의 평균 링크수는 작아진다.
결론
- 전력망만 진짜 중립 네트워크이고, 대부분의 실제 네트워크는 링크수 상관관계를 가지고 있다.
- disassortativity 경향을 보이는 모든 네트워크들은 링크수 상관함수의 전후를 구분할수 없기에 scale-free때문(링크수분포)에 그런 경향을 보이고, 모두 구조적 반대끼리 행동을 보인다.
- assortativity 경향을 보이는 모든 네트워크들은 링크수 분포로 설명되지 않는다.
7.6 상관관계가 있는 네트워크 만들기
다양한 네트워크 특성에 링크수 상관관계가 미치는 영향을 탐구하기 위해, 지금까지 논의한 네트워크 모형들의 상관관계를 먼저 이해해야 한다. scale-free 성질과 링크수 상관관계 사이의 대립이 있어 상관관계가 있는 네트워크를 만드는 것은 쉽지 않다.
7.6.1 정적 모형의 링크수 상관관계
- 에르되쉬-레니 모형
: 무작위 네트워크 모형은 중립이고, 허브가 없기에 구조적 상관관계도 없다.
- 배열 모형(미리 정의된 링크수 배열을 가지고 있는 무작위 네트워크)
링크수 분포 p_k의 선택과 무관하게 중립이다. 모형이 다중 링크와 자기 연결을 모두 허용하기 때문
- 숨은 매개변수 모형
다중링크를 허용하지 않으면 척도 없는 네트워크의 경우 구조적 반대끼리의 성질을 관찰한다.
즉, 정적 모형은 중립 네트워크를 생성하거나 구조적 반대끼리 경향을 가진 네트워크를 생성한다.
7.6.2 변화하는 네트워크의 링크수 상관관계
변화하는 네트워크에서의 링크수 상관관계를 이해하기 위해 초기 매력도 모형, 비안코니-바라밧ㅣ-모형을 알아보자.
- 초기 매력도 모형
- 반대끼리 영역: r<3
- 중립 영억: r = 3
- 약한 끼리끼리 영역 4>3
- 비안코니-바라바시- 모형
- 균일한 적합도 분포를 이용한 비안코니-바라바시 모형은 반대끼리 네트워크를 생성한다.
- 이 네트워크의 무작위 섞기 결과도 반대끼리라는 사실은 모형의 반대끼리 성질이 구조적임을 뜻하지만, 실제 완전 겹치지 않으므로 모형의 반대끼리 성질을 scale-free tjdwlffh dhkswjs dlgogkf tnsms djqtek.
7.6.3 링크수 상관관계 조절하기
네트워크의 링크수 상관관계를 원하는 값으로 조절할 수 있는 알고리즘은 여럿 있고, 이제 주어진 링크수 배열을 이용해 최대한의 상관관계를 가지는 네트워크를 생성하는 알고리즘을 단순화한 알고리즘을 소개할 것이다.
이 단계를 반복하면 2A, 2B 단계를 모두 강화할 수 있다.
이 알고리즘을 통해 생성된 네트워크의 산관관계는 주어진 링크수 배열을 이용해 도달할 수 있는 최댓값(assortativity) 또는 최솟값(disassortativity)으로 수렴한다.
요약하자면, 배열 모형이나 숨은 매개변수 모형같은 정적 모형은 다중 링크를 허용하면 중립이 되고, 단순 네트워크를 조절할 수 있는 네트워크를 만들기 위해 줄비-브루넷과 같은 알고리즘을 사용할 수 있다.
7.7 링크수 상관관계의 영향
대부분의 실제 네트워크는 링크수 상관관계를 보인다. 즉, 링크수 상관관계는 링크수 성질은 바꾸는가? 어떤 성질에 영향을 주는가??
무작위 네트워크의 중요한 성질은 <k> = 1에서 상전이가 나타난다는 것이다. 이때 거대 덩어리가 생긴다. 서로 다른 링크수 상관관계를 보이는 네트워크에서 거대 덩어리의 상대적 비율을 보여주고, 몇가지 패턴이 있음을 확인할 수 있다.
- assortativity network
- 상전이 점이 더 낮은 <k>로 이동한다. 즉, 거대 덩어리는 <k> <1에서 나타난다.
- 링크수가 높은 노드들이 서로 연결하려는 경향에 의해 거대 덩어리가 만들어지기 더 쉽기 때문이다.
- disassortativity network
- 여기서는 상전이가 지연된다.
- 거대 덩어리
- <k>가 큰 경우, assortativity netowkr의 거대 덩어리는 중립 네트워크나 disassortativity network보다 크기가 작다.
- 실제로 끼리끼리 네트워크에서 허브들이 서로 연결하려는 경향에 의해 수많은 링크수가 작은 노드들을 유인하는데 실패한다.
