電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第３部講義(2007年6月19日，6月26日)

Presentation on theme: "電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第３部講義(2007年6月19日，6月26日)"— Presentation transcript:

1 電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第３部講義(2007年6月19日，6月26日)
本実験DのWebpage: 東北大学 大学院情報科学研究科 田中 和之 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

2 第3部の参考文献 大久保潤, 田中和之: 統計力学の基礎 ---複雑ネットワークとの関連にもとづいて---, 特集/ネットワーク科学の数理, 数理科学, Vol.44, No.8 (通巻 518 号), pp.24-29, August 2006. Jun Ohkubo, Muneki Yasuda and Kazuyuki Tanaka: Preferential Urn Model and Nongrowing Complex Networks, Physical Review E, Vol.72, No.6, Article No (R), December 2005. 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

3 今回の話題 複雑ネットワークの科学 マルコフ過程とネットワーク生成モデル スケールフリーネットワーク
19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

4 確率的情報処理 (Probabilistic Information Processing) の更なる拡大
日常生活の情報処理 ポイントはやはり「たくさんが関連」 ICT 技術の要請に耐えうる統計科学 通信理論・像情報処理・確率推論 データマイニング 統計科学 複雑ネットワーク科学 統計的学習理論 情報統計力学 今回のテーマ 確率的情報処理のこれからの数理的基盤 コトの物理学としての定着 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

5 基本構成要素間の関連リンク(Link)
ネットワークと情報処理 たくさんが関連して構成されるシステム 基本構成要素ノード (Node) 基本構成要素間の関連リンク(Link) すぐ思いつく現実的なネットワークの例 インターネット World Wide Web 都市間の交通網（高速道路，航空路線） ネットワーク (Network) ネットワークの構造に共通する性質 すべてのノード間がつながれている訳ではない（非完全グラフ）． ノード間のリンクの存在にはランダム性がある（ランダム性）． 少数ではあるがたくさんのノードとリンクでつながれているノードが存在する（ハブノードの存在）． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

6 ネットワーク生成メカニズムと情報処理 すべてのノード間がつながれている訳ではない（非完全グラフ）．
ノード間のリンクの存在にはランダム性がある（ランダム性）． 少数ではあるがたくさんのノードとリンクでつながれているノードが存在する（ハブノードの存在）． 世の中で自然発生的に構成されたネットワーク上のシステムは何故，うまく機能するのか? 解明のための戦略 どのような数理モデルに基づいてネットワークが生成されていると解釈することが妥当なのか? 生成したネットワーク上で与えられた計算モデルにおいてどのような計算ルール（アルゴリズム）が効率的に機能するのか? 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

7 さまざまのネットワークにおける共通の数理の存在
ネットワークにおけるハブの役割 例：仙台からベネチアまで飛行機で移動したいとしたら ジェノバ ハブ空港のおかげで世界的距離が短くなる （スモールワールド）． 新潟 仙台 東京成田 ミラノ ベネチア 札幌 フィレンツェ もしすぐ近くの空港としか航空便がなければ何回乗り継ぎをしなければならなくなるだろう． もしすべての空港間で航空便が運行していたら何台飛行機が必要だろう． ハブの役割を果たす空港は多い必要はないが，ある程度の数は必要． ハブの役割にも種類がある（日本のハブ空港，アジアのハブ空港，世界のハブ空港）． 空港間・航空会社間の競争の原理から生み出され，最適化されている． 空港のネットワークに階層構造が生まれる． さまざまのネットワークにおける共通の数理の存在 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

8 複雑ネットワーク生成におけるランダムネス
たくさんが関連して構成されるシステム 全体の構造はとても複雑だが個別のノード間のリンクはある一定の単純な規則に従って構成される． 必ず規則に従うのか?すべてのノードのリンクが規則に従って張られているならネットワークには規則性があるはず． 実際のネットワークは完全に規則性をもって構成されているとは言い難い．むしろランダムネスを伴うと考える方が自然． 複雑ネットワーク （ランダムネットワーク，スモールワールドネットワーク等） 複雑ネットワークはその生成過程でどのような規則性とどのようなランダムネスを伴うとき現実の効率的ネットワークと同様の統計的性質をもつのか? 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

9 複雑ネットワークにおける統計的性質 平均次数 次数 ki：ノード i につながっているリンクの本数 N：ノードの総数
スモールワールド性はもつがスケールフリー性をもたない複雑ネットワーク N：ノードの総数 平均次数 ハブのあるなしの違い 平均最短経路長 l: ノード間を結ぶ最短経路の長さ（最短経路長）のすべてのノード対についての平均 log スモールワールド性とスケールフリー性を併せ持つ複雑ネットワーク スモールワールド性 スケールフリー性 l 関数系は生成モデルによる 共通の数理 平均次数とともに平均最短経路長が急速に減少する． 両対数プロットで直線にのる． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

10 確率モデルからの複雑ネットワークの理論的解明
複雑ネットワークと確率モデル スモールワールド性はもつがスケールフリー性をもたない複雑ネットワーク スモールワールド性とスケールフリー性はどのようなネットワーク生成モデルで出現するか? ハブの生まれる原因は何か? ハブのあるなしの違い log どのような競争の原理がポイントか? スモールワールド性とスケールフリー性を併せ持つ複雑ネットワーク 確率モデルからの複雑ネットワークの理論的解明 数値実験ではだめ!! 解析計算がはずせない!! 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

11 スモールワールドネットワークの生成の簡単な例
初期状態 すべてのノードの次数は4 ノードにつながっているリンクの本数をそのノードの次数という． 最短で９本のリンクを通って到達 最短で４本のリンクを通って到達 ランダムにリンクを選んで一端を別のノードにつなぎ変える操作を繰り返す． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

12 スモールワールドネットワークの生成と次数分布
初期状態 すべてのノードが次数4 次数が3と5のノードが1個ずつ出現 次数が3と5のノードが2個ずつとなる． 次数が6のノードが出現． 4 4 4 4 k k k k k 本のリンクを持つノードの個数についてのヒストグラム ノード毎につながっているリンクの本数をそのノードの次数という． ランダムにリンクを選んで一端を別のノードにつなぎ変える操作を繰り返す． この操作を繰り返すと k はどのような分布に従うのだろうか? 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

13 スモールワールドネットワークの生成 p=0 1 1 0 5 10 15 20 p=0 P(k) 10-4 10-3 10-2 10-1 1
p=0 P(k) 10-4 10-3 10-2 10-1 1 l(p)/l(0) 平均最短経路長 p 0.2 0.4 0.6 0.8 C(p)/C(0) 初期状態 p=0.8 k 1 p=0.8 P(k) Poisson分布へ近づく 80%のリンクがつなぎ変えられた時 つなぎ変えられたリンクの割合 k 本のリンクを持つノードの 個数についてのヒストグラム ランダムにリンクを選んで一端を別のノードにつなぎ変える操作を繰り返す． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

14 ランダムネットワークの生成 N 個のノードを用意する． 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ． N=6 5 10 15
5 10 15 20 0.5 P(k) Poisson分布へ近づく 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

15 ランダムネットワークの次数分布の解析 N 個のノードを用意する． 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ． 母関数 5
5 10 15 20 0.5 P(k) Poisson分布へ近づく 2項分布 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

16 ランダムネットワークの平均経路長の解析 N 個のノードを用意する． 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ．
あるノードからみて距離 L にある頂点の総数 n ~ N 平均最短経路長 l ~ L l 1 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

17 成長と優先的選択を伴うネットワーク生成モデル（Barabasi and Albert Model）
初期状態はノード２個，リンク１本から出発 ノード１個，リンク１本を時刻 n のネットワークのノードを1つランダムに選んで追加． 時刻 n のネットワークの i 番目のノードに追加する確率 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

18 成長と優先的選択を伴うネットワーク生成モデル（Barabasi and Albert Model）
19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

19 成長と優先的選択を伴うネットワーク生成モデル（Barabasi and Albert Model）
k 本のリンクにつながっているノードの個数に対するヒストグラム 時刻 n のネットワークの i 番目のノードに追加する確率 スケールフリーネットワーク 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

20 成長するが優先的選択を伴わない ネットワーク生成モデル
k 本のリンクにつながっているノードの個数に対するヒストグラム 時刻 n のネットワークの i 番目のノードに追加する確率 1/n 対数プロットしても直線にのらない スケールフリーネットワークではない 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

21 確率過程(離散時間) 確率変数の集合 n は時間 離散的な場合に限定 （離散）マルコフ過程 19 June - 22 July, 2007
電気・通信・電子・情報工学実験D

22 マルコフ過程 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

23 マルコフ過程の推移確率 マルコフ過程 定常分布 推移確率行列 推移確率 19 June - 22 July, 2007
電気・通信・電子・情報工学実験D

24 成長と優先的選択を伴うネットワーク生成モデル（Barabasi and Albert Model）
初期状態はノード２個，リンク１本から出発 ノード１個，リンク１本を時刻 n のネットワークのノードを1つランダムに選んで追加． 時刻 n のネットワークの i 番目のノードに追加する確率 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

25 マルコフ過程による Barabasi and Albert Model の解析
等価 Yule Process 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D 初期状態

26 マルコフ過程による Barabasi and Albert Model の解析
1 2 初期状態 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

27 マルコフ過程による Barabasi and Albert Model の解析
1 2 初期状態 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

28 マルコフ過程による Barabasi and Albert Model の解析
19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

29 マルコフ過程による Barabasi and Albert Model の解析
1 2 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D 初期状態

30 マルコフ過程による Barabasi and Albert Model の解析
19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

31 マルコフ過程による Barabasi and Albert Model の解析
定性的に再現 k についてのべき分布 スケールフリーネットワーク 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

32 複雑ネットワークの生成におけるメカニズム
まとめ 複雑ネットワークの生成におけるメカニズム ランダム性 優先的選択性 が重要 Barabasi and Albert Model はネットワークの成長を伴うがスケールフリー性にネットワークの成長は必要か? 成長を伴わないネットワークでもスケールフリー性は出現する: J. Ohkubo, M. Yasuda and K. Tanaka: Preferential Urn Model and Nongrowing Complex Networks, Phys. Rev. E, Vol.72, No.6, Article No (R), December 2005. 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

33 複雑系科学におけるネットワークの確率的生成・統計的分析課題
課題レポート提出期限：2007年7月23日 課題レポート提出方法：LaTeX で作成し，最終版を PDF に変換し，電子メール添付にて 宛に送付． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

34 複雑系科学におけるネットワークの 確率的生成・統計的分析課題１
ネットワークサイズN=1000のランダムネットワークを平均次数<k>が2と4である場合について，以下の手順による計算機実験からそれぞれ20個ずつ生成し，次数を横軸にとりヒストグラムを求めよ． N 個のノードを用意する． 2 個のノードを確率 p=<k>/(N-1) でランダムに選択し，リンクで結ぶ． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

35 複雑系科学におけるネットワークの 確率的生成・統計的分析課題２
ネットワークサイズN=1000のBAネットワークを平均次数<k>が2である場合について，次の手順による計算機実験からそれぞれ20個ずつ生成し，20個のサンプルのそれぞれに対して次数を横軸にとりヒストグラムを書け．さらにべき指数を評価せよ． 得られた次数分布にばらつきが多い場合はその20個のネットワークの次数分布の平均をとり評価せよ． 3個のノードを互いにリンクにより結合させ，完全グラフを構成する． 1本のリンクをもつ新しいノード1個を追加し，i 番目のノードに結合する確率が ki に比例するとしてランダムにノードを選び結合する．ここで ki は i 番目のノードの次数である． 2の操作を N-3 回繰り返す． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D

36 複雑系科学におけるネットワークの 確率的生成・統計的分析課題３
課題２で与えられた手順を拡張し，ネットワークサイズN=1000のBAネットワークを平均次数<k>が4である場合について，計算機実験からそれぞれ20個ずつ生成し，20個のサンプルのそれぞれに対して次数を横軸にとりヒストグラムを書け．さらにべき指数を評価せよ． 19 June - 22 July, 2007 電気・通信・電子・情報工学実験D