청-루 피트니스 모델

청-루 피트니스 모델

Chung-Lu Fitness Model

정의

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

알고리즘

Input

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

청-루 모델 1

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 \leftarrow G + ij$$


Output

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

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

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 \leftarrow G + ij$$


Output

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

칼다렐리 모델 3

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$ 의 확률로 링크를 주었으므로, 청-루 모델과 갈라스켈리-로프레도 모델은 그 일반화로 볼 수 있다.


  1. Chung, Lu. (2002). Connected components in random graphs with given expected degree sequences. https://doi.org/10.1007/PL00012580 ↩︎

  2. Garlaschelli, Loffredo. (2004). Fitness-Dependent Topological Properties of the World Trade Web. https://doi.org/10.1103/PhysRevLett.93.188701 ↩︎

  3. Caldarelli. (2002). Scale-Free Networks from Varying Vertex Intrinsic Fitness. https://doi.org/10.1103/PhysRevLett.89.258702 ↩︎

댓글