2章グラフ理論スピード入門
•
29 likes•20,671 views
社会ネットワーク分析勉強会 その２ 『オープンソースで学ぶ社会ネットワーク分析―ソーシャルWebの「つながり」を見つけ出す―』 2012/07/05開催
Recommended
More Related Content
What's hot
What's hot (20)
Viewers also liked
Similar to 2章グラフ理論スピード入門
Similar to 2章グラフ理論スピード入門 (10)
More from Teruo Kawasaki
Recently uploaded
Recently uploaded (10)
2章グラフ理論スピード入門
- 1. オープンソースで学ぶ 社会ネットワーク分析 2章グラフ理論スピード入門 社会ネットワーク分析勉強会 @teruu （てる） 2012/07/05
- 2. 目次 • 1章 イントロダクション • 2章 グラフ理論スピード入門 • 3章 中心性、権力、ボトルネック • 4章 クリーク、クラスタ、コンポーネント • 5章 2モードネットワーク • 6章 バイラルへ！―情報の拡散 • 7章 現実のグラフデータ
- 3. グラフ理論スピード入門 • グラフとは何か • グラフのトラバーサルと距離 • グラフの距離 • なぜこれが重要なのか • 6次の隔たりは神話に過ぎない • スモールワールドネットワーク グラフ理論とPythonの話題が混在 → 初心者には難しい
- 4. 自己紹介 • お仕事 – 元DBエンジニア – 現在、データマイニング専業のベンチャー所属 – 派遣先で、ソーシャルネットワークの分析に携わ る • 大学院で修士課程を修了（2011年3月卒） – 修論テーマ：小売業の購買履歴分析 – （グラフ理論の視点からとらえ直すと）二部グラフ のクラスタリング問題
- 5. グラフ理論スピード入門 • グラフとは何か • グラフのトラバーサルと距離 • グラフの距離 • なぜこれが重要なのか • 6次の隔たりは神話に過ぎない • スモールワールドネットワーク
- 6. グラフとは何か ダイアド（２者関係、diad） ノード（頂点、node） エッジ（辺、関係、edge） E1 N1 好き N2 （動詞） アリス ボブ （名詞） （名詞） 6
- 7. グラフとは何か グラフの種類 – 向き：無向⇔有向 – 重み：重みなし⇔重みつき – モード：1モードグラフ（一部グラフ、unipartite） 2モードグラフ（二部グラフ、bipartite） →５章 マルチモードグラフ（?部グラフ、multipartite） →６章 7
- 8. グラフの向き：無向⇔有向 （A)無向・重みなし・一部グラフ （B)有向・重みなし・一部グラフ
- 9. グラフの重み：重みなし⇔重みつき （A)有向・重みなし・一部グラフ （B)有向・重みつき・一部グラフ
- 10. グラフのモード： 一部グラフ⇔二部グラフ （A)無向・重みなし・一部グラフ （B)無向・重みなし・二部グラフ
- 11. 隣接行列、エッジリスト、隣接リスト グラフ２：無向、重み無し、二部グラフ グラフ１：有向、重み付き、（一部）グラフ （bipartite） （unipartite） グラフ 隣接行列 11
- 12. 隣接行列、エッジリスト、隣接リスト from to value AB2 AD5 AE5 BA2 BD1 ABCDE CD3 A02055 from edges CE4 A (B 2),(D 5),(E 5) B20010 DA5 B (A 2),(D 1) C00034 DB1 C (D 3),(E 4) D51300 DC3 D (A 5),(B 1),(C 3) E50400 EA5 E (A 5),(C 4) EC4 （A)隣接行列 （B)エッジリスト （C)隣接リスト デメリット：メモリの無駄 メリット：メモリ効率的 メリット：メモリ効率的 デメリット：高速サーチ不可 高速サーチ可能 デメリット：パース処理面倒
- 13. グラフとは何か • 隣接行列 • エッジリストと隣接リスト • ケーニヒスベルクの7つの橋
- 14. グラフのトラバーサルと距離 • 深さ優先探索 – 実装 – NetworkXによるDFS • 幅優先探索 – アルゴリズム – NetworkXによるBFS • 単純路と通路 • ダイクストラのアルゴリズム
- 15. グラフのトラバーサルと距離 • 深さ優先探索（DFS） 0→1 →3 →2 →5 →6 →4 →7 →8 →9 (1)何らかのノードnからスタートする。 (2)nに訪問済みのマークを付ける。 (3)nに隣接する未訪問の個々のniについて、 以下の処理を繰り返す。 (4)再帰的にノードniにDFSを適用する。
- 16. • 幅優先探索（BFS） 0→1 →2 →3 →5 →4 →6 →7 →8 →9 (1)ノードnからスタートする。 (2)待ち行列Qを作る。 (3)nに訪問済みのマークを付ける。 (4)nをQにエンキューする。 (5)Qが空でない間、以下の処理を繰り返す。 (6-1)Qからnをデキューする。 (6-2)nに隣接する未訪問の個々のniについて、 以下の処理を繰り返す。 (7-1)niに訪問済みのマークを付ける。 (7-2)niをQにエンキューする。
- 17. 単純路と通路 • 単純路：各ノードを１度だけ通るパス（通路） – 開いた／閉じた – 閉路（閉じた単純路） • ダイクストラのアルゴリズム（1959年） – もっともコストの低い単純路を見つける • Networkx：２つの最短単純路アルゴリズム – dijkstra_path – shortest_path
- 18. グラフの距離 • 指標が複数ある – 最短単純路 • ノードAからBまでのエッジの数 – コストに基づく最短単純路 • 重みつきグラフ – ユークリッド距離 • 隣接行列から計算
- 19. グラフの直径 • あるノードから別のノードへ移動 – 通過するノード数の最大値
- 20. なぜこれが重要なのか • グラフの距離 – グラフを量的に分析する手段 – ネットワーク参加者の影響力を評価
- 21. 6次の隔たりは神話に過ぎない • ミルグラムのスモールワールド実験（1969年） – ６次の隔たり • 神話？
- 22. スモールワールドネットワーク （格子） 直径＝５ 直径＝３ 17本のエッジのうち5本をランダムに置き換える →グラフの形は大きく変わらないが、直径が５→３に
- 23. 複雑ネットワークの歴史 • 1736年 オイラーがケーニヒスベル グの七つの橋の問題をグラフを用い て解決 （一筆書きが不可能であることを証明） → グラフ理論の誕生 • 1967年 ミルグラムのスモールワー ルド実験 • 1998年 ワッツとストロガッツのス モールワールド・ネットワーク • 1999年 バラバシとアルバートのス ケールフリー・ネットワーク
- 24. Python/Networkx • 後ほど演習にて • Networkx （http://networkx.lanl.gov/） • Ipython問題？