ランダムグラフ エルデシュとレーニイによって研究された．→ER-model p:辺連結確率 N:ノード総数 分布：

Presentation on theme: "ランダムグラフ エルデシュとレーニイによって研究された．→ER-model p:辺連結確率 N:ノード総数 分布："— Presentation transcript:

1 ランダムグラフ エルデシュとレーニイによって研究された．→ER-model p:辺連結確率 N:ノード総数 分布：

2 スモールワールドネットワーク コンセプト：任意の二つのノード間が相対的に短い経路である．

3 スケールフリーネットワーク 成長と優先的選択→集合と進化のモデル化＝動的性

4 クラスタ 集合性の測定→クラスタ係数： 完全グラフの総辺数：

5 次数分布 ランダムグラフ：平均次数<k>でピークを持つポワソン分布 スケールフリーネットワーク：ベキ乗則分布

6 スケールフリーモデルの定義 （1）成長：少ないノード数(m0)で始め，毎回m(<=m0)個の異なるノードと連結した新規ノードを追加する． （2）優先的選択：新規ノードのノードiへの連結確率Πは，ノードiの次数kiに依存する． 選択確率Π：

7 理論的アプローチ マスター方程式アプローチとレート方程式に従う，ノード次数の変動． 次数分布： t→∞：

8 マスター方程式，レート方程式 ・マスター方程式アプローチ 時間t，ノードi，導入時間tiで次数kを持つ確率P(k, ti, t)の時間変化
・レート（反応速度）方程式アプローチ 　時間tのとき次数kを持つノードの平均数Nk(t)に注目．Nk(t)の時間変化

9 モデルA（優先的選択なし，成長のみ） 選択確率： t→∞で次数分布は，指数関数的に衰退する．

10 モデルB（成長なし，優先的選択のみ） N個の孤立ノードで始め，ランダム選択と優先的選択のノードを連結する．次数分布は，ガウス分布に近くなる．

11 SFモデルの特徴 ・平均経路長 ・ノード間の相互関係 ・クラスタ係数 ベキ乗則C～N-0.75に比例して減少する．

12 適応度モデル ビアンコーニとバラバシは，実際のネットワークでノードが競争原理を持つことを論じた． →各ノードに適応度ηiを割り当てる．
選択確率： 大きな適応度を持つノードが小さな適応度を持つノードよりも速く次数を増加させる．

13 エラー耐性 辺の除去よりノードの除去のほうがダメージが大きい．

14 SFネットワークのエラー耐性 ランダムなノード除去よりもハブ優先なノード除去のほうが早くシステムが崩壊する．
P(k0)から選択された次数k0のノードを考える． 臨界基準点：