社会ネットワーク勉强会第３回発表
- 1. 「オープンソースで学ぶ社会ネットワーク分析」 第３章 中心性、権力、ボトルネック 近藤しげ @shigex 2012.7.20
- 2. 自己紹介 だれ：近藤しげ 仕事：WEB系フリープログラマー 学校：電気通信大学 ゼミ：自然言語処理 会社：虹なう 好き：一週間後に迫ったフジロック ツイ：@shigex
- 3. いろいろと間違い この本、誤植がちょっと多いです。読むときは気をつけて！ ?? Degree(次数) を「次元」と訳している箇所がある ?? "Betweenness centrality(媒介中心性)"を「媒介近接性」 ?? 「エゴのつながりは代えが効く。世界は彼の横をすり抜けていく」 →正誤情報のためのwikiつくりました http://tokyosna.kondou.com →次回以降の発表者の方は、@shigexまでご連絡を。原著あり
- 4. 原著の目次@USオライリー 翻訳版の目次は章節までだけど、原著の目次は章節項まで 書いてあるので、照らしあわせて読むとわかりやすいです。 「Social ?Network ?Analysis ?for ?Startups」 USのオライリーのサイトの原著の公式ページから目次をみることができます
- 5. 3章 中心性、権力、ボトルネック 3-1.サンプルデータ:ロシア人がやってくる i.? PythonとNetworkXについて 原著の目次より。 ? 少し補足を入れてます。 ii.? LievJournalからノードとエッジを読み出す iii.? スノーボールサンプリング iv.? サンプルデータセットのファイルへの保存、ファイルからのロード 3-2.中心性 i.? このネットワークでより重要なのは誰か ii.? 「セレブ」を見つける ? 次数中心性 iii.? ゴシップモンガー（ゴシップ屋）を探す ? 近接中心性 iv.? コミュニケーションのボトルネック、コミュニティの架け橋を見つける ? 媒介中心性 v.? 中心性指標の組み合わせ vi.? 誰が「灰色の枢機卿」か ? 固有ベクトル中心性 vii.? Kloutスコア viii.? PageRank-Googleの中心性計測のアルゴリズム ? PageRankアルゴリズム 3-3.中心性指標ではわからないこと
- 6. 第３章の全体の流れ 3-1. サンプルデータ取得 3-2. 4つの中心性指標の紹介+k,g 3-3. 中心性指标の问题点
- 7. 3-1. サンプルデータ取得 Live Journal 1999 ? ? ? ? ? ? ? ? ? ? ?2002 ? ? ? ? ? ? ? ? ? ?2003 ? ? ? ? ? ?2003 ? ? ? ? ? ? ?2004 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2006 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2011 ? サービス開始年
- 8. 3-1. サンプルデータ取得 スノーボールサンプリング アルゴリズム –? 中央のノードからスタート –? 中央のノードの友人を取得 –? 友人１人１人について ?? 友人の友人を取得 ?? 友人の友人の１人１人について –? 友人の友人の友人を取得 –? 続く
- 9. 3-2. 4+k+gの中心性指標の紹介 i. 重要なのはだれ？ 社会ネットワーク分析の第一歩 権力、影響力、その他個人的な特性 インフルエンサーを調べる前の第一歩
- 10. 3-2. 4+k+gの中心性指標の紹介 ii. 次数中心性 ?? degree centrality ?? 次数とはノードが持っている接続の数 ?? 次数中心性が高い ＝たくさんの人とつながってる、ハブ ＝入りの矢印が多いと、人気の高さ ?出る矢印が多いと、情報発信/収集力 ?? セレブ（＝有名人） ?? Twitter : フォロワーの数
- 11. 3-2. 4+k+gの中心性指標の紹介 ii. 次数中心性 ?? 日本のツイッター有名人は？ 1位 169万 2位 150万 3位 118万 2012年7月現在 meyou.jp調べ
- 12. 3-2. 4+k+gの中心性指標の紹介 iii. 近接中心性 ?? closeness centrality ?? 全ての他ノードとの距離の平均 ?? 近接中心性が高い ＝少ないリンクで他のノードにたどりつける ＝情報伝搬効率が良い ?? ゴシップモンガー（＝おしゃべり）
- 13. 3-2. 4+k+gの中心性指標の紹介 iii. 近接中心性 計算方法 a.? 他のすべてのノードへの平均距離を計算 b.? 最大の距離で割る N: ?ノード数 ? c.? 近接中心性 = 1 ÷ 平均距離 d(vi, ?vｊ): ?ノードvi,vｊの距離 ? Li ?: ?viから他のN-?‐1点への平均距離 F E C D A B
- 14. 3-2. 4+k+gの中心性指標の紹介 iii. 近接中心性 ロシア人ネットワークの 近接中心性のtop10 図3-6.ロシア人ネットワークの近接中心性の分布 これは、かなり密なネットワークであるにもかかわらず、このLJネットワークのコアは、それぞれのメン バーから3ステップ以上離れたところにローカルなサブセットをもっているということを示している。 つまり、コアに属している人々でも、ネットワークのコアのなかにまったく見えない部分が含まれていると いうことだ。
- 15. 3-2. 4+k+gの中心性指標の紹介 iv. 媒介中心性 ?? betweenness centrality ?? 最も使われている ?? コミュニティのボトルネック、架け橋 ?? どれだけ最短経路上にいるかを計る
- 16. 3-2. 4+k+gの中心性指標の紹介 0 iv. 媒介中心性 0 0.6 0 計算方法 1.? すべてのノードペアの最短単純路を計算 2.? 全てのノード i について i が含まれている 最短単順路の数を数える 3.? 0≦b≦1になるように正規化
- 17. 3-2. 4+k+gの中心性指標の紹介 iv. 媒介中心性 ?? 予防接種などに応用 ?? 「流れ」は最短路を通ると仮定 ?? 媒介中心性が高くなるためには、 ノードが貴重な最短路の上にいることが重要 ?? 複雑ネットワークでは媒介中心性を 「負荷」と呼ぶこともある
- 18. 3-2. 4+k+gの中心性指標の紹介 v. 3つの中心性指標の組み合わせ 次数中心性と媒介中心性は だいたい相関するが、 媒 そうではない場合もある 介 次数 増田?今野(2010)「複雑ネットワーク」p35 表3-1. 中心性指標の組み合わせ
- 19. 3-2. 4+k+gの中心性指標の紹介 v. 3つの中心性指標の組み合わせ ?? 3指標のtop10をマージした表 ?? ネットワークのエリートリスト ?? 全部で18人 ?? 媒介性が目立つのはvalerois
- 20. 3-2. 4+k+gの中心性指標の紹介 vi. 固有ベクトル中心性 ?? ゴッドファーザーは表にでてこない ?? 実力者につながってるとエラくなる ?? eigenvector centrality ?? リンク先のノードの次数によって、 リンクを重み付けする ?? 「灰色の枢機 」(影の実力者)
- 21. 3-2. 4+k+gの中心性指標の紹介 vi. 固有ベクトル中心性 計算方法 1.? まず、すべてのノードに1という中心性スコアを与える 2.? ノードの隣にある全てのノードの中心性の合計として 各ノードのスコアを再計算する 3.? ここの値を最大値で割って、vを正規化する 4.? vの値が変化をやめるまでステップ2と3を繰り返す
- 22. 3-2. 4+k+gの中心性指標の紹介 補. 4つの中心性指標を比較 増田?今野(2010)「复雑ネットワーク」辫33より
- 23. 3-2. 4+k+gの中心性指標の紹介 vii. クラウトスコア ?? SNSでの影響力を計るスカウター ?? 2010年にサービス開始 ?? 当初は、Twitterのみを基に算出していた ?? 現在はTwitter, Facebook, Google+
- 24. 3-2. 4+k+gの中心性指標の紹介 vii. クラウトスコア ?? Klout Score : 総合スコア ?? True Reach : 実際に届いている数 ?? Ampli?cation : リアクションの起きる確率 ?? Network Impact : ネットワークの影響力
- 25. 3-2. 4+k+gの中心性指標の紹介 vii. クラウトスコア ?? 単一の指標ではノードの中心性を表現できない ?? ノードの評価基準はいろいろある →クラウトスタイルってのも…
- 26. 3-2. 4+k+gの中心性指標の紹介 viii. PageRank(google) ?? 外からのリンクで中心性を計る ?? 有向グラフ 計算式 ?? 収束するには時間がかかるけど、途中でも使える ?? スケーラビリティがある
- 27. 3-3. 中心性指标の问题点 中心性指标の问题点 ?? 単なる静的な点（ノード）の観察 ?? エッジの分析や、ネットワークの動的な分析 はできない ?? 4章は、ノードを超えて三者間の関係トライ アドについて考える
- 28. 書籍情報 ?? オープンソースで学ぶ社会ネットワーク分析 –? Maksim Tsvetovat,Alexander Kouznetsov著 –? 長尾高弘訳 –? オライリー社 –? 2012年5月 –? 誤植が多いので、原著も買うはめに(泣) ?? 「複雑ネットワーク―基礎から応用まで」 –? 増田直紀,今野紀雄 –? 近代科学社 –? 2010年4月 –? 理論書。このスライドでも、これから図を引用しました。 オススメです。テキストが終わったら、次はこれでレベルアップを！