네트워크에서 차수의 분포

네트워크에서 차수의 분포

빌드업

랜덤 네트워크는 그 함수값이 네트워크인 랜덤 엘러먼트이므로, 샘플링을 할 때마다 다른 네트워크를 얻는다. 네트워크를 구축하는 방법에 따라, 즉 모델에 따라 어떠한 일관된 성질을 가지긴 하겠지만 그렇게 얻어진 실현은 제각각이다. 이에 따르면 각 노드의 차수 $\deg$ 역시 매번의 샘플링때마다 바뀌는데, 네트워크 이론에서 차수는 대단히 중요한 요소기 때문에 확률변수로 보고 관심을 가진다.

컨벤션

랜덤 네트워크에서 각 노드 $v$ 의 차수 $\deg v$ 는 (이산) 확률변수로 본다. 일반적으로 모든 노드 $v$ 가 같은 확률분포를 가진다면 확률 $P$ 와 확률질량함수 $f$ 에 대해 다음과 같이 나타낸다. $$ P \left( \deg v = k \right) = f(k) $$

예시

차수의 분포는 네트워크의 성질이 될 수도 있고 애초에 정의가 될 수도 있다. 예로써 차수의 분포가 파레토 분포인 네트워크로 정의되는 스케일 프리 네트워크는 수식으로 다음과 같이 나타낼 수 있다. $$ P \left( \deg v = k \right) \sim k^{- \gamma} $$ 또 다른 예로써 $n$ 개의 노드를 가지고 각 노드가 연결될 확률 $p$ 가 주어진 길버트 모델에서 노드의 차수는 나머지 $(n-1)$ 개의 다른 노드와 연결되었느냐 연결되지 않느냐에 달려 있으므로, 이항분포 $B(n-1,p)$ 를 따르게 된다. 수식으로 깔끔하게 적어보면 다음과 같다. $$ P \left( \deg v = k \right) = \binom{n-1}{k} p^{k} \left( 1 - p \right)^{n-1-k} $$

댓글