PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

えいしろうながおか
7 years ago
Views:

1 2012 年 11 月 2 日複雑系の科学第 3 回複雑ネットワークその 1 東京大学大学院工学系研究科鳥海不二夫

2 複雑ネットワーク 1. 世の中すべてネットワーク~ 複雑ネットワーク入門 2. ネットワークを見る~ 複雑ネットワーク分析指標 3. 古典的ネットワーク~ランダム格子ネットワーク 4. 世間は狭い~スモールワールドネットワーク 5. 不平等な世界 ~スケールフリーネットワーク 6. ネットワークを作る~ネットワーク生成モデル1 7. ネットワークを作る~ネットワーク生成モデル2

3 複雑ネットワークの歴史 1736 年ケーニヒベルグ問題 1960 年 RandomGraph 1998 年 SmallWorldNetworks グラフ理論複雑ネットワーク 1967 年ミルグラムの実験 1999 年 ScaleFree 理論複雑ネットワークは新しい学問ここ 10 数年で大きく前進

4 複雑ネットワークの歴史ケーニヒスベルグの橋 RandomGraph ミルグラムの実験 SmallWorld 理論 ScaleFree 理論

5 ケーニヒスベルグの橋問題スタート地点ケーニヒスベルグという町 a~g という 7 つの橋が架かっている

6 ケーニヒスベルグの橋問題スタート地点ルールスタート地点から出発して, スタート地点に戻る橋は一度しか渡れないルールに従ってスタートからスタートへ戻れるか?

7 ケーニヒスベルグのネットワーク A c a d b C B e f g D グラフ理論っての考えたオイラー

8 RandomGraph ポールエルディシュ著名な数学者生涯に約 1500 篇の論文を書いたエルデシュ = レーニィモデル ERモデルともランダムに作られたネットワークグラフ理論から一歩前進グラフネットワーク

9 ミルグラムの実験スタンレーミルグラム ( ) イェール大学社会心理学

10 ミルグラムの実験友人の友人のとたどっていってカンザスからマサチューセッツまで何人で到達できるか?

11 ミルグラムの実験カンザス州に住むさまざまな境遇の応募者に手紙を送るマサチューセッツ州のとある人に手紙を送りたいルールファーストネームで呼び合う人にしか手紙は送れない= 割と仲がいい人限定最終的に目標の人に到達するように手紙を出す

12 ミルグラムの実験目標人物何人の人を経由して手紙は目標人物に到達するのか

13 平均で 6 人を経由ミルグラムの実験およそ 6~7 人を経由すれば世界中の人とつながることが出来る世界が狭い =6 次の隔たり

14 Small World Networks Duncan J. Watts コロンビア大学の学生 1998 年 Nature に投稿した 3 ページの論文 Collective dynamics of 'small-world' networks ネットワークの世界を変えた世界は狭く, そして固まっている

15 Scale Free Network Albert-László Barabási ノートルダム大学教授 1999 年 Science に投稿した 4 ページの論文 Emergence of scaling in random networks やっぱりネットワークの世界に衝撃を与えた世界は不平等だ

16 それから世界的に複雑系ネットワークの研究が盛んにさまざまな現象が明らかに WEB の発達により大規模なネットワークが出現電子データの利用従来より簡単に巨大なネットワークを分析可能にネットワーク分析に注目ビッグデータソーシャルメディア

17 ネットワークとは何か?

18 世の中色々ネットワーク

19 ネットワークとは? グラフとも呼ぶネットワーク = ノードとそれをつなぐリンクノードノードノードリンクノードノードノード

20 ノードとリンク人間がノード友人関係がリンクお客様と商品がノード購買関係がリンク経営者と従業員がノード命令関係がリンク会社がノード会社間の商品やお金の流れがリンク

21 世の中すべてネットワーク世の中の色々な現象がネットワークで表せる地下鉄路線航空経路インターネット WEBページのリンク Wikipediaのカテゴリ mixi ケーニヒスベルグの橋

22 地下鉄路線図駅 = ノード線路 = リンク

23 航空経路ネットワーク空港 = ノード経路 = リンク

24 インターネットのつながり何十万のコンピュータ同士が接続コンピュータ = ノード接続 = リンク

25 WEB ページのつながり WEB ページ = ノードハイパーリンク = リンク

26 Wikipedia カテゴリのつながりカテゴリ = ノードリンク構造 = リンク

27 mixi 上の友人ネットワーク人間 = ノード友人関係 = リンク

28 ケーニヒスベルグの橋問題スタート地点ケーニヒスベルグという町 a~g という 7 つの橋が架かっている

29 ケーニヒスベルグの橋問題スタート地点ルールスタート地点から出発して, スタート地点に戻る橋は一度しか渡れないルールに従ってスタートからスタートへ戻れるか?

30 ケーニヒスベルグのネットワーク c d C g A a b B e f D A~D の土地 = ノード a~g の橋 = リンクオイラー

31 一筆書き出来ますか? c d g a b e f 一筆書きの一般則奇数個の線が出ている頂点が,0or2 個なら一筆書き可能

32 ケーニヒスベルグのネットワーク A c a d b C B e f g D 橋渡り問題もネットワーク陸地 = ノード橋 = リンク

33 グラフ理論グラフ理論ケーニヒスベルグの橋問題から発展複雑ネットワークを理解する上での基礎理論グラフネットワーク

34 グラフ理論の基礎 Graph とは V: 頂点 (vertex) からなる集合 E: 点をつなぐ辺 (edge) からなる集合 G:VとEの集合 G v 3 e 1 e 2 e 3 v 4 v 1 e 4 v 2

35 グラフの表現 V = v 1, v 2, v 3, v 4, v 5 E = {e 1 = v 1, v 3, e 2 = v 2, v 3, e 3 = v 3, v 4, e 4 = v 2, v 4 } G = {V, E} G v 3 e 1 e 2 e 3 v 4 v 1 e 4 v 2

36 隣接関係点の隣接関係 v 1, v 2 は隣接した点 e 1 v 1 v 2 辺の隣接関係 e 1, e 2 は隣接した辺 e 1 e 2 v 1 v 2 v 3

37 問題このグラフにおける隣接頂点, 隣接辺をすべて述べよ v 3 G e 1 e 2 e 3 v 4 v 1 e 4 v 2

38 解答隣接頂点 v 1, v 3, v 2, v 3, v 3, v 4, v 2, v 4 隣接辺 e 1, e 2, e 1, e 3, e 2, e 3, e 2, e 4, (e 3, e 4 ) G v 3 e 1 e 2 e 3 v 4 v 1 e 4 v 2

39 次数次数頂点 v i が接続している辺の数 deg v i 各頂点の次数はいくつか? ddd(v i ) v 1 1 G v 2 2 v 3 v 3 3 v 4 2 e 1 e 2 e 3 v 4 v 1 e 4 v 2

40 完全グラフすべての頂点が辺でつながれているグラフ v 3 v 1 v 4 v 2

41 問題頂点の数が n の完全グラフにおける辺の数はいくつか? 頂点 v 1 に接続する辺はn 1 本従って, 全頂点から接続する辺の総数はn(n 1) ただし, 一つの辺は2 頂点と接続する n(n 1) N e = 2

42 グラフからネットワークへグラフとネットワークは何が違うのか? 答え : 同じもの数学的な概念としてのグラフ実社会の現象としてのネットワーク色々名称が異なるグラフネットワーク頂点ノード辺リンク

43 グラフとネットワークグラフ理論グラフ頂点辺ネットワーク理論ネットワークノードリンクネットワーク v 3 ノード e 1 e 2 e 3 v 4 v 1 v 2 e 4 リンク

44 ネットワーク分析世の中をネットワーク構造として捉える分析が容易にネットワーク分析の例ケーニヒスブルグの橋社会ネットワーク分析企業間取引ネットワーク分析

45 大学運動部の人間関係 3 年生 2 年生 1 年生

46 大学運動部の人間関係 3 年生 2 年生 3 年生 1 年生 2 年生 1 年生

47 大学運動部の人間関係 3 年生の中心的グループ 1 年生の中心的グループ 3 年生 2 年生 1 年生 2 年生の中心的人物

48 風の谷のナウシカ ( 漫画版 ) の人間関係

49 高校生の恋人関係ネットワーク

50 業界構造マップ企業間取引をネットワークで表現東京大学工学系研究科総合研究機構イノベーション政策研究センター

51 対話における単語共起ネットワーク

52 複雑ネットワーク 1. 世の中すべてネットワーク~ 複雑ネットワーク入門 2. ネットワークを見る~ 複雑ネットワーク分析指標 3. 古典的ネットワーク~ランダム格子ネットワーク 4. 世間は狭い~スモールワールドネットワーク 5. 不平等な世界 ~スケールフリーネットワーク 6. ネットワークを作る~ネットワーク生成モデル1 7. ネットワークを作る~ネットワーク生成モデル2

53 次回予告ネットワークはどうすれば分析できるのか? 巨大すぎるネットワークを数字で読み取る

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p The size of the world It is a small world Araseki Hitoshi Can you believe that everyone is at most six steps away from any other person on the Earth? This phenomenon, which is called small world phenomenon,