ネットワーク理論
Paul ErdősとAlfréd Rényiの名前にちなんだErdős-Rényiモデルは、エッジが等しい確率のノード間に設定されたランダムグラフを生成する。 確率方法で、さまざまなプロパティを満たすグラフの存在を証明したり、多くのグラフに対してあるプロパティが持つ重要性を厳密に定義したりできる。Erdős-Rényiモデルを生成するには2つのパラメータが必要である。1つは、生成されたグラフ内のノード数Nと、ある2つのノード間でリンクpを形成する確率である。Eをエッジ数の期待値とすると、 式⟨k⟩ = 2 ⋅ E / N = p ⋅ (N − 1)を使って定数⟨k⟩を導き出せる。
Erdős-Rényiモデルには、他のグラフと比べるといくつかの興味深い特徴がある。 このモデルは特定のノードにバイアスをかけずに生成されるため、度数分布は次の式のように二項式となる:
P ( deg  ( v ) = k ) = ( n − 1 k ) p k ( 1 − p ) n − 1 − k {\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}}
その結果、クラスター係数が0になる傾向にある。 このモデルは⟨k⟩ > 1を「パーコレーション」と呼ばれるプロセスでgiant component(大きいコンポーネント)を生成する。 またこのモデルでは、平均距離が比較的短く、log Nに近くなる。
Mediation-Driven Attachment(MDA、仲介駆動型接続)モデルでは、 m {\displaystyle m} 個のエッジを持つ新しいノードが既にリンクされているノードをランダムに選択し、そのノードだけでなく、その隣人のノード m {\displaystyle m} 個にランダムにリンクする。 既存のノード i {\displaystyle i} が新しいノードに選ばれる確率 Π ( i ) {\displaystyle \Pi (i)} は以下のようになる:
Π ( i ) = k i N ∑ j = 1 k i 1 k j k i {\displaystyle \Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}
この式の2つ目の因数は、調和平均(IHM)の逆数である。ノード i {\displaystyle i} の k i {\displaystyle k_{i}} 近傍の次数(IHM)を計算する。