📂グラフ理論

ブルー・ルーフィットネスモデル

定義

各ノードにWeight（重み）を与え、その重みに従ってリンクが接続される確率が異なるランダムネットワークをフィットネス・モデルと言う。

アルゴリズム

入力

$n \in \mathbb{N}$ノードを持つNull Graph$G$が与えられているとする。

チュン・ルー・モデル ¹

ステップ 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}$が割り当てられる。

---

ステップ 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$$

---

出力

ノードのExpected Degreeが$\mathbf{w}$のランダムネットワーク$G$を得る。

ガロスケッリ・ロフレドモデル ²

ステップ 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} }} $$

---

ステップ 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$$

---

出力

Scale-Free Network$G$を得る。

カルダレッリ・モデル ³

ステップ 1.

$n$に依存したThreshold（閾値）関数$z(n)$が与えられているとする。Exponential Distribution $\exp(1)$から$x_{1} , \cdots , x_{n}$をサンプリングする。各ノード$k \in V (G)$にはWeight$x_{k}$が割り当てられる。

---

ステップ 2.

Heaviside Step Function$\theta$に対して、次のような行列$A$を作る。 $$ \left( A \right)_{ij} := \theta \left( x_{i} + x_{j} - z(n) \right) $$ このように作られた行列$A$は、二つのノード$i,j$の適合度の合計が閾値$z(n)$を超える場合は$1$, 超えない場合は$0$の行列になる。

---

ステップ 3.

隣接行列$A$を持つグラフ$G$を作る。

---

出力

パレート分布 $\text{Pareto} \left( 2 \right)$の次数分布を持つスケールフリーネットワーク$G$を得る。

説明

フィットネスモデルは、導入されたように、主にスケールフリーネットワークを生成するために開発されたモデルであり、本質的には、重み（影響力）が高いノードが多数のリンクと接続され、パレート分布のヘビーテールを引き出すことによって相似である。したがって、WeightやFitnessといった言葉自体に固執する必要はない。

すべてのノードペアに対して一定の確率$p$でリンクを与えたギルバートモデルは、チュン・ルー・モデルやガロスケッリ・ロフレドモデルの一般化と見ることができる。