[논문소개] Barabasi-Albert model (바라바시 알베르트 모델)

 바라바시의 Emergence of Scaling in Random Networks 라는 논문에서 소개된 Barabasi-Albert model (BA 모델)을 파해쳐 보기로 한다.

참조: [논문] Emergence of Scaling in Random Networks (http://mons1220.tistory.com/47) 

(노드=지점 : 새로운 네트워크 기점을 가르킴)

Babasi-Albert Model의 의의

 바라바시모델은 기존의 네트워크 모델들이 사회현상에서 발생하는 거듭제곱 분포(Power Law Distribution)을 설명하지 못했던 것을, 두가지의 네트워크 생성원칙의 도입을 통해 해결하였다.

 거듭제곱 분포의 법칙이란 한개의 네트워크를 가진 기점의 수, 두개의 네트워크를 가진 기점의 수... n개의 네트워크를 가진 기점의 수 이렇게 쫘악~~~ 숫자를 세서 분포 그래프로 그려보면, 기점이 가진 네트워크 수와 그 기점의 수의 분포가 거듭제곱의 형태로 나타나는 것이다.

 

 바라바시의 논문에서 제시하는 예제로는 배우들의 협업 네트워크, 월드와이드웹, 전력망 네트워크가 있다.

 

 그래프의 스케일을 보면 k도 p(k)도 대수 스케일로 작성되었고, 일직선으로 표시되는 걸 볼 수 있다. 상기 식에 로그를 씌어 보면 그 이유를 알 수 있는데, 이 그래프에서 구해지는 기울기가 Power law의 스펙트럼이 되겠다.

Babasi-Albert Model 의 생성원칙 

 이러한 거듭제곱 분포를 만들기 위해 바라바시가 제시한 두가지 생성원칙은 다음과 같다.

 첫번째 생성원칙은 네트워크는 성장한다는 것이다. 기존에 제안된 모델들에서는 정해진 숫자의 노드(기점)사이에서 네트워크들이 생성되었는데, 바라바시 모델에서는 노드의 숫자가 시간이 지날수록 증가한다. 새로운 기점들이 유입되는 것이다.

 두번째 생성원칙은 네트워크 연결은 선호도를 가진다는 것이다. 즉, 연결이 많은 기점일수록 새로운 연결이 생길 수 있는 확률이 더 높다는 것이다.

 이 두가지 생성원칙을 통해 생성된 네트워크는 거듭제곱 분포의 성질은 지니게 된다. 

 다음은 바라바시모델의 시뮬레이션 결과이다.

그림 A는 BA 모델으로써, 대수 스케일의 그래프에서 일직선의 분포(거듭제곱 성질)가 나타나는 것을 알 수 있다.

그림 B는 BA 모델의 생성 규칙 중, 두번째 규칙 연결 선호도의 규칙을 없앴을 때의 성질이다. 일직선이어서 거듭제곱이라 착각할 수 있지만 k의 스케일을 보면 대수스케일이 아니다. 이건 거듭제곱의 규칙이 아니라 지수분포(e의 k승)일 때 나타나는 분포의 모습이다.

그림 C는 한 기점 i에서 연결의 수 k가 시간에 따라 어떻게 성장해 나가는지를 나타내고 있다. 시간이 지남에 따라 연결은 시간의 거듭제곱에 비례하여 증가하는 걸 알 수 있다.

Babasi-Albert Model 분석

 

 그리고, 바라바시는 시뮬레이션 뿐 아니라, 식으로도 이러한 관계를 설명하였다.

 우선, 다음과 같이 모델링을 생각해보자.

 시작 기점 수가 정해져있고, 새로운 노드는 시간이 1 증가할 때마다 한개씩 증가한다. 그리고 새로운 노드는 새로운 연결을 기존의 노드들과 생성하게 되는데 이 새로운 연결의 수는 m으로 정해져있다. 

 이 때, 기존 노드 중에 새 노드와 연결이 생길 확률은 한 노드가 지닌 연결의 수를 각 노드가 지닌 모든 연결의 수로 나눈 값이다. 이를 노드에 새 연결이 추가된 확률이라고 부르며 다음과 같이 나타낼 수 있다.

 

  그리고 이를 이용해서, 시간에 따른 노드의 증가를 계산 할 수 있다. 사실 여기서 연결의 수 k는 확률에 따라 증가할 수도 증가하지 않을 수도 있다. 그래서 연속함수라고 보기는 힘들지만, t가 충분히 큰 즉, 커다란 네트워크 구조상에서 보았을 때, 특정 기울기를 지녔다고 볼 수 있다. 이를 평균장 근사라는 개념을 사용하면

와 같이 나타낼 수 있다. 여기서 모든 연결의 수 가 2mt가 되는 이유는 t의 증가에 따라 연결이 m씩 증가하였으므로 총 네트워크는 mt가 되지만, 한 연결은 각각의 노드에 연결된 연결로 따로따로 더해지므로 전체 연결의 개수의 두배의 값이 분모가 되는 것이다.

 이를 통해 i 지점의 연결 수 k를 시간에 관한 함수로 표현할 수 있다.

 여기서 ti는 i지점의 노드가 네트워크에 추가된 시점의 시간이고, 첫 연결 시에 노드는 m개의 연결을 지니므로 위와 같이 표현할 수 있게 된다. 이 식을 통해 시뮬레이션 결과(상기 그래프 Fig2-C) 에서 시간의 증가와 연결의 증가의 관계를 설명할 수 있게 된다. 그리고 이는 나중에 추가된 노드는 기존의 노드보다 더 많은 연결을 가질 수 없다는 설명이 되므로, 부익부 빈익빈 현상을 설명할 수 있는 모델임을 이야기 해준다.

 다음으로 Power law, 거듭제곱 현상을 설명할 시간이다.

 지점 i에서 연결의 수 ki가 특정 수 k보다 작을 확률을 다음과 같이 표현한다.

 

 그럼 k가 커지면 커질 수록 증가하여, k가 가장 커졌을 때에 확률 P가 1에 도달하는 그래프가 만들어진다.

 여기서 의 증가량은 그 지점에서의 확률 을 나타내게 되고, 우리는 를 구하여 k로 미분을 하면 시간 t에서 지점i에 k_i의 연결이 생길 확률을 구할 수 있게 되는 것이다.

 위에서 구한 k_i와 시간 t에 관한 식을 이용하면 다음과 같이 변형이 가능하다.

(제곱을 할 수 있는 이유는 k가 1보다 크기 때문이다.)

 그럼 이게 무슨 의미를 지니는지 알아보자. 위식에서 다음 조건

의 확률은 어떤걸 의미하는가? 우변은 시간 t에서 k개의 연결을 가지는 지점이 네트워크에 처음 추가된 시간이다.

말이 좀 어렵다면 위에서 구한 k_i를 구하는 식을 변형하여 생각해보자.

 

 

윗 식에서 t_i는 네트워크에 i번째 노드가 처음으로 추가된 시간이다. 그러므로 제일 아래의 식 t_k는 시간 t에서 k개의 연결을 가지는 지점이 네트워크에 추가된 시간이다. 그럼 조건은 다음과 같이 나타낼 수 있다.

그리고 이걸 말로 풀이하자면 k개의 연결을 가지는 지점보다 빠른 시간에 발생한 i지점의 확률이다. 우리는 상기의 부익부 빈익빈 현상을 통해 이를 해석할 수 있다. 빨리 네트워크에 합류한 지점이 더 많은 연결수를 가지게 되는(긴 시간 t가 주어졌을 때) 현상을 통해 t_k보다 빨리 합류한 지점 t_i의 연결 k_i는 k보다 작게 되는 것이다.

 한가지 더, 우리는 1의 시간간격마다 새로운 노드가 추가된다고 하였다. 그렇다면 총 노드의 개수는 

 이고, 시간t에서 k개의 연결을 가지는 노드가 네트워크에 합류한 시간 는 그 이전에 개의 노드들이 생겨났다는 것을 의미하고, 개의 노드들은 위의 조건 에 해당하는 노드들의 개수이다. 그럼 확률은 해당 노드 나누기 전체 노드의 개수 이고, 이를 이제 제일 위의 식에 대입해보면

의 결론을 얻게 된다.

 또한 우리는 이 식을 k로 미분한 값이 k의 연결을 가질 확률이라는 것을 위에서 언급하였다.

그리하여 k로 미분을 하게 되면 다음 식을 얻을 수 있고, t가 m_0에 비해 충분히 큰 시간일 때 약분 되는 것을 알 수 있다.

그럼 P(k)는 k에 관한 식으로 나타낼 수 있으며, k의 -3의 스펙트럼을 지니는 Power law, 즉 거듭제곱의 형태로 수식이 표현되는 것을 보일 수 있게 되는 것이다!

 이 식을 통해 다시 한번 위에있는 Fig2-A를 보자. 대수 스케일의 그래프에서 기울기가 -3인 것을 확인 할 수 있다.

고찰

 직관에 의한 네트워크 생성원칙의 발견, 그리고 수식을 통한 그 증명이란 점에서 세상에 큰 영향을 미쳤던 논문이다. 바라바시는 이 논문을 통해 네트워크에 관한 연구에 큰 영향을 주었다.

 더 많은 연결을 지닌 노드가 새로운 연결이 생길 확률이 높다는 원리는 자원 단위에서 힘이 작용하고 있다는 것을 의미한다. 네트워크라는 것을 자원으로 생각하면, 더 많은 자원이 있는 곳에, 더 많은 자원들이 몰리게 되는 현상이다. 이 현상을 통해 거듭제곱 형태 즉 Power Law 현상이 일어나게 된다.

 이러한 통찰을 통해, 특정 네트워크 또는 자원의 분포가 거듭제곱 형태인지 지수분포 형태 인지에 따라 네트워크의 생성 메카니즘을 가늠해 볼 수 있다.