ランダムグラフ

ランダムグラフ
エルデシュとレーニイによって研究された．→ER-model
pN ( N  1) p:辺連結確率
分
2
N:ノード総数
布：
スモールワールドネットワーク
コンセプト：任意の二つのノード間が相対的に短い経路である．
スケールフリーネットワーク
成長と優先的選択→集合と進化のモデル化＝動的性
クラスタ
集合性の測定→クラスタ係
数：
完全グラフの総辺数：
2 Ei
Ci 
ki ki  1
ki (ki  1)
2
次数分布
ランダムグラフ：平均次数<k>でピークを持つポワソン分布
スケールフリーネットワーク：ベキ乗則分布
スケールフリーモデルの定義
（1）成長：少ないノード数(m0)で始め，毎回m(<=m0)個の異な
るノードと連結した新規ノードを追加する．
（2）優先的選択：新規ノードのノードiへの連結確率Πは，ノー
ドiの次数kiに依存する．
選択確率Π： (ki ) 
ki
k
j
j
理論的アプローチ
マスター方程式アプローチとレート方程式に従う，ノード次
数の変動．
次数分
布：
P(ki (t )  k ) 2m1  t 1
P( k ) 

k
m0  t k 1  1
1

r
t→∞： P(k ) ~ 2m k ，　with　r 
1

1  3
マスター方程式，レート方程式
・マスター方程式アプローチ
時間t，ノードi，導入時間tiで次数kを持つ確率P(k, ti, t)の
時間変化
・レート（反応速度）方程式アプローチ
時間tのとき次数kを持つノードの平均数Nk(t)に注目．Nk(t)
の時間変化
モデルA（優先的選択なし，成長の
み）
選択確
率：
1
 ( ki ) 
m0  t  1
t→∞で次数分布は，指数関数的に衰退する．
モデルB（成長なし，優先的選択の
み）
N個の孤立ノードで始め，ランダム選択と優先的選択のノード
を連結する．次数分布は，ガウス分布に近くなる．
SFモデルの特徴
・平均経路長 l  A log(N  B)  C
・ノード間の相互関係
nkl 
4(l  1)
12(l  1)

k (k  1)(k  l )(k  l  1)(k  l  2) k (k  l  1)(k  l )(k  l  1)(k  l  2)
・クラスタ係数
ベキ乗則C～N-0.75に比例して減少する．
適応度モデル
ビアンコーニとバラバシは，実際のネットワークでノードが競争
原理を持つことを論じた．
→各ノードに適応度ηiを割り当てる．
選択確率：  i 
i ki
 j jk j
大きな適応度を持つノードが小さな適応度を持つノードよりも
速く次数を増加させる．
エラー耐性
辺の除去よりノードの除去のほうがダメージが大きい．
SFネットワークのエラー耐性
ランダムなノード除去よりもハブ優先なノード除去のほうが早く
システムが崩壊する．
P(k0)から選択された次数k0のノードを考える．
臨界基準
点：
1
fc  1 
 k02 
1
 k0 

Download Report