ネットワークマイニング（グラフ构造分析）
- 1. ネットワークの特徴量で Twitter の 友達リストを分析する Karubi Namuru Aug 22nd, 2010
- 2. 自己紹介 ● Karubi Namuru ● 博士（理学） ● Kauli 株式会社，代表 ● オンライン広告配信技術 ● Twitter: @karubi ● Facebook: http://facebook.com/karubi ● 出身：広島 , 居住：東京 , Seongnam
- 3. 学生时代の话 ● 在学中の研究 ● 統計的手法による日常行動分析 – 実世界：ライフログ – ウェブ：閲覧， clicks 200 200 180 180 160 160 140 140 120 120 100 100 80 80 60 60 40 40 20 20 0 0
- 4. 今日の内容 ● モチベーション ● 複数の方からグラフの話を聞きたいと DM が来た ● 初心者でも分かりやすい話がききたい ● ネット上の資源で遊ぶ Part II ● グラフの基礎 ● 分析方法の紹介 ● 分析結果の一例
- 5. グラフの概要 ● ある対象について，関連する事柄や出来事の関 係をあらわしたもの ● 数学的にはグラフ理論であつかわれている
- 6. 数学的なグラフ ● 構成要素 ● ノード – 頂点や節点で表現できる ● エッジ – 枝や辺で表現できる 引用： http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96
- 7. 辺の向き ● 問題によっては辺の向きを考慮する場合もあ ● ノード同士の繋がりのみを考慮する – → 向きが無いので「無向」 ● ノード同士について，どちらがどちらに繋がってい るかどうかも考慮する – → 向きがあるので「有向」
- 8. グラフ構造 ● グラフをコンピュータで扱えるようにする ● お絵かきした図については，人間が解釈できるがコ ンピュータが解釈できない表現 ● グラフ構造：データ構造としてグラフを表現 ● コンピュータが解釈できる表現 ● 一定の形式を導入する ● データ処理をおこなう際に，もっともやりやすくす ることが目的（深い話につながるのでここまで）
- 9. グラフ構造で記述できるもの ● 生活中のさまざまな自然現象 ● 日常生活で形成した知り合いの関係 ● 人の興味?嗜好と買い物の関係 ● 目的地までの移動方法 ● インターネット内の現象 ● ウェブページ同士の繋がり ● ウェブページの HTML コンテンツの配置 ● 電子メールの送受信履歴
- 10. グラフ構造の分析 ● グラフ構造を処理することで問題を解決する ● グラフ内の要素を分析する場合 – 個々の頂点で，最も多くの辺が張られる頂点はどれか ● グラフ同士を分析する場合 – ふたつのグラフが似ているかどうか 引用： http://www.weblio.jp/content/%E4%B8%80%E7%AD%86%E6%9B%B8%E3%81%8D
- 11. グラフの分析例 ● たとえば一筆書きの例 ● ケーニヒスベルクという大きな町 ● この町の中央にプレーゲル川という大きな川 ● 七つの橋が架けられている ● あるとき町の人が「この 7 つの橋 を 2 度通らず，全て渡って，元の 所に帰ってくることができるか 引用： http://www.weblio.jp/content/%E4%B8%80%E7%AD%86%E6%9B%B8%E3%81%8D
- 12. グラフマイニング ● 主にグラフに埋もれた知識や知見を発見するた めのグラフ構造の分析 ● 大量のデータ ● データ構造 ● 計算方法 ● 豊富な計算能力
- 13. 実際にマイニング ● 友達関係を分析してみる ● 問題 – 自分の友達のなかで，注目に値する友達を誰か特定した い ● たとえば，このように考えてみる – もっとも話をする友達が一番注目に値する！ ● TopTwitterFriend
- 14. マイニングの一例 参照： http://businessspeak.wordpress.com/2009/03/27/top-twitter-friends-map-brian-solis-pr-20
- 15. Karubi の考え ● 友達同士の繋がりに注目 ● 注目に値する友達は，自分の知っている友達が多く 友達関係をもちかけている人 ● もちろん友達関係をもちかけられる数が多ければ多 いほど，注目に値するのはないか ● ただし，一方的に見ず知らずの人でも，なんでもか んでも友人関係を大量にいろんな人にもちかけてい る人は注目に値しない
- 16. 実际に分析してみる ● PageRank ● 考え方：論文の引用関係のように，重要なウェブ ページがリンクを集める ● 計算方法は割愛；； ● ネットで調べればいくらでも出てきますよ
- 17. 実际に分析してみる
- 18. まとめ ● グラフマイニングの概要 ● Twitter の Following で実験 ● 人選はランダムなので結果は気にしないで☆ ● ご質問ございましたらメールください gogokarubi@gmail.com まで