[네트워크과학] degree distribution을 설명하는 최적의 function 찾기

 지난번 글 'Scale free network - degree distribution 핏팅' 에서는 네트워크 데이터로 부터 구한 degree distribution에 power law function을 핏팅하기 위한 테크닉을 정리했었다.

 오늘은 과연 power law function이 degree distribution을 설명하는 적합한 function일까? 라는 질문에 대해 다뤄보려 한다.

 power law function은 '부익부 빈익빈'에 유래한다. 네트워크에서 '부익부 빈익빈'이란 link를 많이 지닌 node에 더 많은 node의 유입이 이루어 지는 것을 의미한다. degree distribution의 형태가 power law로 나타난다는 것은 네트워크 형성 메카니즘에 이러한 부익부 빈익빈 적 요인이 있다는 주장을 지지하는 중요한 근거가 된다. 그래서 degree distribution을 power law function에 핏팅하고 그 지수를 살펴보는 것은 중요한 네트워크의 지표로 사용된다.

 그런데 과연 power law function이 맞는가? exponential 이라던가 log-normal의 형태가 더 적합하지 않을까? 하는 질문이 남는다. 만약 다른 형태의 function이 더 적합하다면? 부익부 빈익빈의 메카니즘 자체를 회고해 볼 필요가 있지 않을까? exponential과 log-normal의 형태는 선호성을 지니는 성장 메커니즘 (preferential attachment)보다는 임의적인 성장 메커니즘에 기반할 가능성이 높기 때문이다.

 그래서 도입한 방법은 likelihood ratio test다. 이전 글에서 degree distribution을 power law function에 핏팅하기 위해서, maximum likelihood를 이용했다. power law function의 지수를 모수로 두고, 데이터에 기반하여 likelihood를 최대화 하는 모수를 찾는 방법이다.

 마찬가지로, exponential, lognormal, stretched exponential... 등등 비교하고 싶은 function들도 같은 방식으로, data에 최적화된 함수의 형태로 핏팅한다. 그리고 이 때 구한 각각의 함수의 likelihood를 power law function의 likelihood와 비교함으로써 어떤 함수가 적합한지 판단한다.

likelihood ratio를 식으로 나타내면 다음과 같다.

$ \large \begin{align}\mathcal{R} &= \mathcal{L}_{PL} - \mathcal{L}_{alt}\\&= \sum_{i=1}^N \left[l_{i}^{(PL)} - l_{i}^{(alt)}\right]\end{align} $

 여기서 $\mathcal{L}_{PL}$은 power law function의 log-likelihood를, $\mathcal{L}_{alt}$는 alternative function(exponential, lognormal...)의 log-likelihood를 나타낸다. likelihood의 ratio는 log-likelihood에서는 차로 나타난다.

Non-nested function

 likelihood ratio를 이용한 적합도 판별은 비교하고자 하는 두 함수의 형태가 서로를 포함하고 있는지의 여부에 따라 다르다. 예를들면, $e^{\lambda}x^{\alpha}$는 $x^{\alpha}$를 포함한(nested) 형태이므로 항상 fitting에 있어서 우위를 차지하게 된다. 먼저 그렇지 않은 경우 non-nested function들 간의 차이를 알아보자.

 

 Non-nested function에서는 likelihood 의 비율이 크고 작음으로 적합도를 판단하는데, 그 정도의 유의함을 검증할 필요가 있다. 여기서 필요한 가정은 각각의 node i가 지닌 degree 값은 독립적이라는 것이다. 그렇게 되면 각 노드에서의 log-likelihood $\mathcal{l}_{l}^{(PL)}-\mathcal{l}_{l}^{(alt)}$ 또한 독립적인 값이 되고, 이들의 합인 $\mathcal{R}$는 중심극한정리에 의해 node의 수 n이 커질 수록 normal distribution을 이룰 것이다. 이 distribution의 분산값은 $n\sigma^{2}$고, $\sigma^{2}$는 $\mathcal{l}_{l}^{(PL)}-\mathcal{l}_{l}^{(alt)}$ 의 표본분산이다. 

 이 distribution을 통해 가설 검증을 할 수 있는데, 'Power law function과 alternative function의 likelihood ratio에 차이가 없다.'라는 가설(귀무가설 $H_{0}$)을 설정한다. 귀무가설에 의해 평균값 $\mu$는 0으로 설정되고, 분산은 $n\sigma^{2}$인 $\mathcal{R}$값의 기대 distribution에서 관찰된 $\mathcal{R}$값에 대한 two-tail probabilty를 p-value로 설정한다. 

 p-value가 작아 귀무가설을 기각하게 될 때, $\mathcal{R}$이 음의 값을 지니는지 양의 값을 지니는지에 따라 어떤 function이 적합한지 검증할 수 있다.

 단 위의 방법은 non-nested function에 적용할 수 있다. non-nested란 서로의 함수에 서로가 포함되지 않는 경우이다.

Nested function

 Nested function간 비교의 경우 조금 다른 방법을 취한다. power law function에 대한 nested function은 exponentially truncated power law function을 예로 들 수 있는데, 함수의 형태가 다음과 같다

$ \large \begin{align}\mbox{power law} &: Cx^{-\alpha}\\ \mbox{truncated power law} &: Cx^{\alpha}e^{-{\lambda}x}\end{align} $

 exponentially truncated powerlaw function(여기서 부터 줄여서 TCPL)의 형태는 powerlaw 형태를 유지하다가 degree가 증가하면서 distribution의 tail이 exponential 하게 떨어지는 function인데, 물리적으로 성장이 제한되는 경우의 scale-free network에서 나타나는 형태이다.

 이 때, TCPL은 power law에 비해 모수를 하나 더 지니므로, 여러모로 핏팅 성능에 유리하게 된다. 그렇기 때문에 만약 power law가 TCPL보다 더 적합한 경우 위에서 구한 $\mathcal{l}_{l}^{(PL)}-\mathcal{l}_{l}^{(TCPL)}$의 분산과 p-value는 0으로 수렴하게 되고, normal distribution을 상정하는 중심극한 정리의 사용이 불가능하게 된다. 

 그래서 nested function에 대해서는 L'Hopital's rule이라는 방식을 사용하게 되는데, $-2\mathcal{R}$의 distribution이 chi-squared distribution를 따른다는 것을 이용한다. 이 때, chi-squared distribution에서 $-2\mathcal{R}$보다 클 확률은 powerlaw가 TCPL의 비율이 충분히 작을 확률에 해당하고, 이 값이 충분히 작을 경우에는 power law가 TCPL보다 적합하지 않다는 해석을, 그렇지 않을 경우에는 TCPL이 powerlaw보다 distribution을 더 잘 설명할 수 있다는 충분한 근거가 없다는 해석을 내릴 수 있게 된다.

 

[참고]

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

[2] https://www.statisticshowto.datasciencecentral.com/likelihood-ratio-tests/