[네트워크과학] Scale free network - degree distribution 핏팅

Degree distribution과 Scale-free network

 Network에서 각 node가 지닌 link의 수의 분포를 degree distribution이라고 한다. 그리고, 이 degree distribution의 형태를 통해 network의 특징을 살펴볼 수 있다.

 Scale-free network는 degree distribution에 대해 척도 불변의 성질을 지닌 네트워크를 말한다. scale-free는 여기서 scale invariance(척도 불변)를 나타내는데, 함수 f(x)의 형태가 x의 스케일 요소에 의존하지 않는다는 뜻이다. 좀 더 쉽게 말해보자면, 서로 다른 degree scale에서 함수의 형태를 살펴 봐도 그들이 빚어내는 형상은 불변한다. 

 이러한 특징을 지닌 함수는 power law function의 형태를 취한다. (p(x)는 확률밀도함수, x는 degree)

x를 스케일링한 값 λx를 넣어도, Cλ^(-α)x^(-α) 로, 상수항만 변할 뿐 함수 x의 형태는 변하지 않는다. 이 성질은 x축 y축이 log-log 스케일인 그래프로 보면 더 확실히 다가오는데, 어떤 x구간을 보더라도 -α의 기울기를 지닌 직선의 형태가 변하지 않는다.

 이런 scale-free network는 degree를 많이 지닌 node가 더 많은 link를 얻는 부익부 빈익빈의 메커니즘을 담고 있으며, 실제 네트워크에서 엄청나게 많은 link를 지닌 Hub의 존재를 설명한다.

 Scale-free network가 성공적이었던 이유는, 이론과 함께 실제 data에서 보여지는 degree distribution의 척도 불변성에 대한 분석이 함께 발전 하여 성공적으로 원인과 결과의 고리가 이어졌기 때문이다.

 Degree distribution은 굉장히 거칠게 어림 잡는 network의 성질이다. 이 어림잡기에는 node간의 종속성이 배제되어 있으며, 네트워크의 특성을 제시할 때 이와 같은 어림잡기의 오류를 보완하기 위해 node간 종속성을 고려한 clustering coefficient, assortativity와 같은 network의 구조적 성질과 함께 사용된다.

Degree distribution을 power-law function에 핏팅시키기

 허나 Degree distribution을 특정 함수에 핏팅하고, 특징을 규정하는 것 자체도 하나의 도전적 과제이다. 오늘은 실제 data에서 power-law distribution을 추정하는 방식을 제시한 Clauset의 논문을 통해 올바른 핏팅 방법에 대해 살펴보려 한다.

기존 핏팅 법의 문제점

 보통, 가장 쉽게 생각할 수 있는 방법은 단순히 Data로 부터 구한 degree distribution을 log-log 스케일에서 선형 함수에 핏팅하는 방법일 것이다. 식을 통해 보자면, 

와 같이 기울기 -α의 선형 함수로 나타낼 수 있으며, 최소자승법과 같은 방법으로 구할 수 있을 것이다. 

 하지만, 이런 방법에는 여러 오차의 위험이 존재한다고 한다. 

1) Data의 pdf를 구하기 위한 binning 구간을 어떻게 잡는지에 따라 오차가 발생할 수 있고, 

2) 핏팅의 질을 나타내는 r2계수가 power-law function의 형태가 아닌 data에서 유효하지 못하며, 

3) 핏팅 후 구한 power-law 함수의 형태가 probability distribution의 기본 전제인 확률밀도함수의 특성(전 구간 적분 시 1이 되는)에 기반하지 않는다는 점이다.

논문에서 제안하는 핏팅법

 과정이 꽤 복잡하므로, 간단히 먼저 정리해보자면 다음과 같다.

---

 1) Power law function에 해당하는 데이터 구간 선택을 위해 낮은 degree 구간을 cutoff하기 위한 xmin 설정

 2) Data로부터 likelihood를 최대화 하는 계수 α를 계산

 3) Kolmogorov-Smirnov test를 위한 cumulative dsitribution function의 maximum distance D 계산

 4) 다른 xmin 조건에서 1)-3) 반복

 5) 모든 xmin 에서 3)의 D를 비교, D를 최소화 하는 xmin 결정. 그 때 2)로 부터 구한 alpha가 우리가 구하고자 하는 power law function의 거듭제곱 지수

---

천천히 살펴보자.

1) xmin

 논문에서는 먼저 기존 핏팅 법의 문제점인 3)을 극복하기 위해 degree x의 최소값인 xmin의 필요성을 제시한다. 실제 데이터는 지저분하다. 그래서 power-law function의 형태는 전 degree 구간에서 뚜렷하게 나타나기보다는 특정 degree이상에서 나타나는 것이 일반적이다. (이를 설명하는 다양한 model들이 연구되어 있다 e.g. Initial attractiveness model) 그래서, xmin 이상의 degree만을 대상으로 확률밀도 함수를 재구성하고 normalization을 해줄 필요가 있다. xmin은 data로부터 가능한 degree를 모두 대입해본다. 

 

2-1) power law function

 xmin을 대입한 상태에서 Power law function은 x의 Continuous/Discrete의 여부에 따라 달라진다. x가 continuous라 함은 가정하는 x의 상태가 연속적인 수 전체에서 나타날 수 있다는 점이다.

 network를 예로 들자면 link의 weight가 1.232 처럼 실수로 표현된 network에서, 각 node가 지닌 link의 weight의 합산 값에 대한 확률밀도 함수를 구할 때, x는 continuous하다. 반면 단순히 link의 개수만으로 degree를 표현하는 경우 x는 1, 2, 3 과 같이 discrete하다.

 이 때, 확률밀도 함수의 적분값을 1로 만드는 normalization항을 적용한 power law function의 형태는 다음과 같다.

Continuous X

Discrete X

 Discrete 데이터에서는 x가 정수만을 취하므로 normalization 항이 후르비츠 제타함수의 형태를 취한다고 한다.

 2-1) likelihood

 Degree distribution을 power law function에 핏팅한다는 것에 어떤 의미가 있을까?

 이것은 power law function 형태의 확률밀도 함수가 degree distribution의 model임을 의미한다. 이 말인 즉슨, degree distribution의 data X={x1, x2, x3, ...xn}은 power law function에서 튀어나온 표본임을 의미한다. 이 표본들을 통해 power law function의 거듭제곱 지수 α를 구하는 방법이 maximum likelihood이다.

 먼저 likelihood에 대해 간단히 설명해 보자. 확률밀도 함수와 likelihood는 같은 함수의 형태를 취하지만 관점이 다르다. pdf는 α가 정해져 있고, x가 가변이다. 즉 정해진 pdf 함수에서 x가 나올 확률은 α에 기반해 구할 수 있다. 반면, likelihood는 x가 정해져 있고, α가 가변이다. 즉, 추출된 표본 집단 X에서 pdf가 α의 모수를 지닐 때의 가능도를 likelihood라고 한다.

 조금 복잡하다면, 이렇게 생각해보자. 거듭제곱지수가 α1과 α2로 다른 power law function이 두 개가 있다고 치자. 주어진 data로부터 어느 function이 적합할지 어떻게 알 수 있을까? 표본에 많이 등장하는 x의 pdf값(likelihood)가 높은 값을 가져야 하고, 표본에 많이 등장하지 않는 x의 pdf값은 낮은 값을 가져야 할 것이다. 이를 설명하는 alpha값을 구하면 된다.

 이 때 표본 X={x1, x2, ..., xn}은 각각의 node의 degree이고, power law function으로부터 독립적으로 추출되었다. 이 말인 즉, 이 표본 데이터들이 우리가 가정한 α의 power law function에서 튀어나올 확률은 각각의 likelihood의 곱이 된다는 것이다. 식으로 표현하자면 다음과 같다.

윗 식에서 |는 거듭제곱지수의 조건을 나타낸다. 이제, 우리는 L(α)를 가장 크게 만드는 α를 구하면 된다. 그런데 그냥 윗 식을 이용하기에는 꽤 복잡하다. 그래서 단조증가 함수인 log함수에 넣는다. 우리는 최대 L을 만드는 α를 구하고 싶으니까 likelihood의 log값 log-likelihood를 최대로 만드는 α를 구하는 문제와 같다. 

2-2) maximum likelihood

 위에서 구한 식은 data의 continuous/discrete 여부에 따라 표현이 달라진다. 대입해서 풀어보면, 다음과 같다.

Continuous X

Discrete X

log-likelihood를 최대로 하는 alpha값을 구하기 위해선 alpha로 미분한 값이 0이 되는 곳을 찾으면 된다. 혹은, 다양한 alpha를 대입하여 직접 log-likelihood가 최대로 하는 alpha를 선정하는 방법도 있다.

3) Kolmogorov-Smirnov(KS) test와 maximum distance

 KS test는 non-normal data인 두 확률밀도분포의 거리를 정량적으로 평가하는 가장 보편적 방법이라고 한다. 방법은 간단한데, 두 함수의 누적확률분포(cumulative distribution function, cdf)를 구하고, 두 함수의 거리가 가장 벌어지졌을 때 그 절대값을 maximum distance(D)라 한다. 이를 식으로 굳이 나타내 보자면 다음과 같다.

탐색 구간은 xmin 이상의 x이고, S(x)는 실제 데이터로 부터 구성한 cdf, P(x)는 maximum likelihood로 구한 alpha를 사용한 power law function의 cdf를 의미한다.

 우리의 목표는 xmin에 따라 변하는 D값을 구해가며, D를 최소로 만드는 xmin을 구하는 것이다. 이렇게 구한 xmin은 낮은 x값에서 exponential과 같이 power-law가 아닌 성분을 제거하고, 곧은 power-law function을 만들어 줄 수 있는 cutoff가 될 것이다.

4-5) 반복

 xmin은 data가 지닌 x의 범위 내에서 반복하여 조사한다. 

 xmin을 정해 data를 cutoff하고, maximum likelihood를 통해 정제한 data에 맞는 power law function의 α를 구하고, 그 때의 관측 분포와 이론 분포의 차이를 cdf의 maximum distance(D)를 통해 정량화 하고, D가 최소가 되는 xmin을 찾는 과정을 되풀이 하는 것이다.

 그리고, 찾은 xmin과 그 때의 α가 우리가 최종적으로 구하는 powerlaw function을 구성하는 모수가 될 것이다.

결론

 이 알고리즘을 통해 Clauset은 robust하고 정확한 거듭제곱 지수 fitting 성능을 보였다. 지금은 거의 power law function fitting의 기준이 된 것 처럼 보인다. 그 인용 수가 7695회에 이른다.

 Clauset은 이를 발전시킨 통계적 수법을 통해 'Scale-free networks are rare'라는 논문을 발표하고, power law에 대한 통계적 엄밀성이 화제가 되며 핏팅 관련 일관성을 개선하기 위한 관련 논문들이 나오고 있다.

 다음에는 실제 예를 통해 알고리즘을 설명하는 글을 정리해 봐야겠다.

참고)

 [논문] Clauset, Aaron, Cosma Rohilla Shalizi, and Mark EJ Newman. "Power-law distributions in empirical data." SIAM review 51.4 (2009): 661-703.

 [Maximum likelihood] https://www.youtube.com/watch?v=XepXtl9YKwc

 [Barabasi Network science Section 4.13] http://networksciencebook.com/chapter/4#advanced-c