2012 年 11 月 2 日 複雑系の科学 第 3 回複雑ネットワーク その 1 東京大学大学院工学系研究科鳥海不二夫
複雑ネットワーク 1. 世の中すべてネットワーク~ 複雑ネットワーク入門 2. ネットワークを見る~ 複雑ネットワーク分析指標 3. 古典的ネットワーク~ランダム 格子ネットワーク 4. 世間は狭い~スモールワールドネットワーク 5. 不平等な世界 ~スケールフリーネットワーク 6. ネットワークを作る~ネットワーク生成モデル1 7. ネットワークを作る~ネットワーク生成モデル2
複雑ネットワークの歴史 1736 年ケーニヒベルグ問題 1960 年 RandomGraph 1998 年 SmallWorldNetworks グラフ理論 複雑ネットワーク 1967 年ミルグラムの実験 1999 年 ScaleFree 理論 複雑ネットワークは新しい学問 ここ 10 数年で大きく前進
複雑ネットワークの歴史 ケーニヒスベルグの橋 RandomGraph ミルグラムの実験 SmallWorld 理論 ScaleFree 理論
ケーニヒスベルグの橋問題 スタート地点 ケーニヒスベルグという町 a~g という 7 つの橋が架かっている
ケーニヒスベルグの橋問題 スタート地点 ルール スタート地点から出発して, スタート地点に戻る 橋は一度しか渡れない ルールに従ってスタートからスタートへ戻れるか?
ケーニヒスベルグのネットワーク A c a d b C B e f g D グラフ理論っての 考えた オイラー
RandomGraph ポール エルディシュ 著名な数学者 生涯に約 1500 篇の論文を書いた エルデシュ = レーニィモデル ERモデルとも ランダムに作られたネットワーク グラフ理論から一歩前進 グラフ ネットワーク
ミルグラムの実験 スタンレーミルグラム (1933-1984) イェール大学 社会心理学
ミルグラムの実験 友人の友人の とたどっていってカンザスからマサチューセッツまで何人で到達できるか?
ミルグラムの実験 カンザス州に住むさまざまな境遇の応募者に手紙を送る マサチューセッツ州のとある人に手紙を送りたい ルール ファーストネームで呼び合う人にしか手紙は送れない= 割と仲がいい人限定 最終的に目標の人に到達するように手紙を出す
ミルグラムの実験 目標人物 何人の人を経由して 手紙は目標人物に到達するのか
平均で 6 人を経由 ミルグラムの実験 およそ 6~7 人を経由すれば世界中の人とつながることが出来る 世界が狭い =6 次の隔たり
Small World Networks Duncan J. Watts コロンビア大学の学生 1998 年 Nature に投稿した 3 ページの論文 Collective dynamics of 'small-world' networks ネットワークの世界を変えた 世界は狭く, そして固まっている
Scale Free Network Albert-László Barabási ノートルダム大学教授 1999 年 Science に投稿した 4 ページの論文 Emergence of scaling in random networks やっぱりネットワークの世界に衝撃を与えた 世界は不平等だ
それから 世界的に複雑系ネットワークの研究が盛んに さまざまな現象が明らかに WEB の発達により大規模なネットワークが出現 電子データの利用 従来より簡単に巨大なネットワークを分析可能に ネットワーク分析に注目 ビッグデータ ソーシャルメディア
ネットワークとは 何か?
世の中色々 ネットワーク
ネットワークとは? グラフとも呼ぶ ネットワーク = ノードとそれをつなぐリンク ノード ノード ノード リンク ノード ノード ノード
ノードとリンク 人間がノード 友人関係がリンク お客様と商品がノード 購買関係がリンク 経営者と従業員がノード 命令関係がリンク 会社がノード 会社間の商品やお金の流れがリンク
世の中すべてネットワーク 世の中の色々な現象がネットワークで表せる 地下鉄路線 航空経路 インターネット WEBページのリンク Wikipediaのカテゴリ mixi ケーニヒスベルグの橋
地下鉄路線図 駅 = ノード 線路 = リンク
航空経路ネットワーク 空港 = ノード 経路 = リンク
インターネットのつながり 何十万のコンピュータ同士が接続 コンピュータ = ノード 接続 = リンク
WEB ページのつながり WEB ページ = ノード ハイパーリンク = リンク
Wikipedia カテゴリのつながり カテゴリ = ノード リンク構造 = リンク
mixi 上の友人ネットワーク 人間 = ノード 友人関係 = リンク
ケーニヒスベルグの橋問題 スタート地点 ケーニヒスベルグという町 a~g という 7 つの橋が架かっている
ケーニヒスベルグの橋問題 スタート地点 ルール スタート地点から出発して, スタート地点に戻る 橋は一度しか渡れない ルールに従ってスタートからスタートへ戻れるか?
ケーニヒスベルグのネットワーク c d C g A a b B e f D A~D の土地 = ノード a~g の橋 = リンク オイラー
一筆書き出来ますか? c d g a b e f 一筆書きの一般則 奇数個の線が出ている頂点が,0or2 個なら一筆書き可能
ケーニヒスベルグのネットワーク A c a d b C B e f g D 橋渡り問題もネットワーク 陸地 = ノード 橋 = リンク
グラフ理論 グラフ理論 ケーニヒスベルグの橋問題から発展 複雑ネットワークを理解する上での基礎理論 グラフ ネットワーク
グラフ理論の基礎 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
グラフの表現 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
隣接関係 点の隣接関係 v 1, v 2 は隣接した点 e 1 v 1 v 2 辺の隣接関係 e 1, e 2 は隣接した辺 e 1 e 2 v 1 v 2 v 3
問題 このグラフにおける隣接頂点, 隣接辺をすべて述べよ v 3 G e 1 e 2 e 3 v 4 v 1 e 4 v 2
解答 隣接頂点 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
次数 次数 頂点 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
完全グラフ すべての頂点が辺でつながれているグラフ v 3 v 1 v 4 v 2
問題 頂点の数が n の完全グラフにおける辺の数はいくつか? 頂点 v 1 に接続する辺はn 1 本従って, 全頂点から接続する辺の総数はn(n 1) ただし, 一つの辺は2 頂点と接続する n(n 1) N e = 2
グラフからネットワークへ グラフとネットワークは何が違うのか? 答え : 同じもの 数学的な概念としてのグラフ 実社会の現象としてのネットワーク 色々名称が異なる グラフ ネットワーク 頂点 ノード 辺 リンク
グラフとネットワーク グラフ理論グラフ頂点辺 ネットワーク理論ネットワークノードリンク ネットワーク v 3 ノード e 1 e 2 e 3 v 4 v 1 v 2 e 4 リンク
ネットワーク分析 世の中をネットワーク構造として捉える 分析が容易に ネットワーク分析の例 ケーニヒスブルグの橋 社会ネットワーク分析 企業間取引ネットワーク分析
大学運動部の人間関係 3 年生 2 年生 1 年生
大学運動部の人間関係 3 年生 2 年生 3 年生 1 年生 2 年生 1 年生
大学運動部の人間関係 3 年生の中心的グループ 1 年生の中心的グループ 3 年生 2 年生 1 年生 2 年生の中心的人物
風の谷のナウシカ ( 漫画版 ) の人間関係
高校生の恋人関係ネットワーク
業界構造マップ 企業間取引をネットワークで表現 東京大学工学系研究科総合研究機構イノベーション政策研究センター
対話における単語共起ネットワーク
複雑ネットワーク 1. 世の中すべてネットワーク~ 複雑ネットワーク入門 2. ネットワークを見る~ 複雑ネットワーク分析指標 3. 古典的ネットワーク~ランダム 格子ネットワーク 4. 世間は狭い~スモールワールドネットワーク 5. 不平等な世界 ~スケールフリーネットワーク 6. ネットワークを作る~ネットワーク生成モデル1 7. ネットワークを作る~ネットワーク生成モデル2
次回予告 ネットワークはどうすれば分析できるのか? 巨大すぎるネットワークを数字で読み取る