📂그래프이론

청-루 피트니스 모델

정의

각 노드 별로 가중치^weight를 주고 그에 따라 링크가 연결되는 확률을 다르게 주는 랜덤 네트워크를 피트니스 모델^{fitness model}이라 한다.

알고리즘

Input

$n \in \mathbb{N}$ 개의 노드를 가진 널 그래프 $G$ 가 주어져 있다고 하자.

청-루 모델 ¹

Step 1.

$\displaystyle \max w_{k}^{2} < \sum_{k=1}^{n} w_{k}$ 을 만족하게끔 하는 디그리 시퀀스 $\displaystyle \mathbf{w} := \left( w_{1} , \cdots , w_{n} \right)$ 를 만든다. 여기서 각 노드 $k \in V(G)$ 에는 가중치^weight $w_{k}$ 가 할당된다.

---

Step 2. 베르누이 시행

for $i,j \in \left\{ 1, \cdots , n \right\}$
　　if $i \ne j$ then
　　　　$$p_{ij} = {{ w_{i} w_{j} } \over { \sum_{k=1}^{n} w_{k} }}$$ 　　　　의 확률로 다음과 같이 네트워크 $G$ 에 링크 $ij$ 를 추가한다. $$G \gets G + ij$$

---

Output

노드의 기대 차수^{expected Degree}가 $\mathbf{w}$ 인 랜덤 네트워크 $G$ 를 얻는다.

갈라스켈리-로프레도 모델 ²

Step 1.

파라미터 $\delta > 0$ 가 주어져 있고 각 국가 $k \in V(G)$ 마다의 국내총생산^gDP $w_{k}$ 를 생각해보자. 이에 대해 다음과 같이 노멀라이즈^normalized한 상대적^relative GDP $x_{k}$ 들을 적합도^fitness라 하자. $$ x_{k} := {{ w_{k} } \over { \sum_{k=1}^{n} w_{k} }} $$

---

Step 2. 베르누이 시행

for $i,j \in \left\{ 1, \cdots , n \right\}$
　　if $i \ne j$ then
　　　　$$p_{ij} = {{ \delta x_{i} x_{j} } \over { 1 + \delta x_{i} x_{j} }}$$ 　　　　의 확률로 다음과 같이 네트워크 $G$ 에 링크 $ij$ 를 추가한다. $$G \gets G + ij$$

---

Output

스케일-프리 네트워크 $G$ 를 얻는다.

칼다렐리 모델 ³

Step 1.

$n$ 에 종속된 역치함수^threshold $z(n)$ 이 주어져 있다고 하자. 지수 분포 $\exp(1)$ 에서 $x_{1} , \cdots , x_{n}$ 을 샘플링 한다. 각 노드 $k \in V (G)$ 마다 가중치 $x_{k}$ 가 할당된다.

---

Step 2.

헤비사이드 계단 함수 $\theta$ 에 대해 다음과 같은 행렬 $A$ 을 만든다. $$ \left( A \right)_{ij} := \theta \left( x_{i} + x_{j} - z(n) \right) $$ 이렇게 만들어진 행렬 $A$ 는 두 노드 $i,j$ 의 적합도의 합이 임계치 $z(n)$ 을 넘기면 $1$, 넘기지 못하면 $0$인 행렬이다.

---

Step 3.

$A$ 를 인접행렬으로 하는 그래프 $G$ 를 만든다.

---

Output

차수분포가 파레토 분포 $\text{Pareto} \left( 2 \right)$ 인 스케일-프리 네트워크 $G$ 를 얻는다.

설명

피트니스 모델은 주로 스케일-프리 네트워크를 생성하기 위해 개발된 모델로써, 소개된 바와 같이 다양한 방법이 있지만 본질적으로는 가중치(영향력)가 높은 노드가 많은 링크와 연결됨으로써 파레토 분포의 헤비 테일^{heavy Tail}을 유도해낸다는 점에서 서로 유사하다. 그러니 가중치^weight나 적합도^fitness와 같은 단어 자체에 집착할 필요는 없다.

길버트 모델는 모든 노드쌍에 대해 상수 $p$ 의 확률로 링크를 주었으므로, 청-루 모델과 갈라스켈리-로프레도 모델은 그 일반화로 볼 수 있다.