データマイニング - ノードの中心性

1. 近接中心性
2. 次数中心性
3. 固有ベクトル中心性
4. 媒介中心性

Transcript

1. ノードの中心性 ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 yusuke_yamamoto@acm.org 第11回 データマイニング （グラフ分析入門） ⼭本祐輔 クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
2. グラフを「把握したい」ケース グラフを把握したい ノード 単体 グラフの 部分構造 グラフ 全体 局所的特徴 ⼤局的特徴
3. グラフを「把握したい」ケース グラフを把握したい グラフ 全体 局所的特徴 ⼤局的特徴 ノードの重要性評価はグラフ分析の典型的タスク グラフの 部分構造 ノード 単体
4. ノードの中⼼性 § グラフにおける各ノードの重要度を⽰す指数 § 重要ノードの発⾒やノードの順序づけなどに利⽤ § 中⼼性の⼤きさはグラフ構造に基づき計算される どのくらい重要？ どちらが重要？
5. さまざまな中⼼性（⼀部） 近接中心性 他のノードに最も近いノードは？ 次数中心性 多くのノードと接続しているノードは？ 固有ベクトル中心性 重要なノードと多く接続しているノードは？ 媒介中心性 他のノードへの橋渡し役として重要なノードは？ グラフの何に注⽬したいかによって⽤いる中⼼性は変わる
6. さまざまな中⼼性（⼀部） 近接中心性 他のノードに最も近いノードは？ 次数中心性 多くのノードと接続しているノードは？ 固有ベクトル中心性 重要なノードと多く接続しているノードは？ 媒介中心性 他のノードへの橋渡し役として重要なノードは？ グラフの何に注⽬したいかによって⽤いる中⼼性は変わる
7. 近接中⼼性 (closeness centrality) (1/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 0 2 1 3 4 5 1 2 2 1 1 𝐶! 𝑣" = 1 𝑣" からの平均距離 = |𝑉| − 1 ∑#! 𝑑𝑖𝑠𝑡(𝑣" , 𝑣$ )
8. 近接中⼼性 (closeness centrality) (2/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 逆数をとって 距離が近いと 値が⼤きくなるように 0 2 1 3 4 5 1 2 2 1 1 𝐶! 𝑣" = 1 𝑣" からの平均距離 = |𝑉| − 1 ∑#! 𝑑𝑖𝑠𝑡(𝑣" , 𝑣$ )
9. 近接中⼼性 (closeness centrality) (3/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 ⾃分を除いたノードの数 0 2 1 3 4 5 1 2 2 1 1 近接中⼼性は連結グラフにしか定義ができないことに注意 𝐶! 𝑣" = 1 𝑣" からの平均距離 = |𝑉| − 1 ∑#! 𝑑𝑖𝑠𝑡(𝑣" , 𝑣$ )
10. 近接中⼼性 (closeness centrality) (4/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 0 2 1 3 4 5 1 2 2 1 1 0 2 1 3 4 5 1 2 3 4 3 𝐶! 𝑣% = 5 7 𝐶! 𝑣& = 5 13
11. 近接中⼼性 (closeness centrality) (5/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 0 2 1 3 4 5 1 2 2 1 1 𝐶! 𝑣% = 5 7 # 近接中⼼性 cc = nx.closeness_centrality(G) # ノード2の値 print(cc[2])
12. さまざまな中⼼性（⼀部） 近接中心性 他のノードに最も近いノードは？ 次数中心性 多くのノードと接続しているノードは？ 固有ベクトル中心性 重要なノードと多く接続しているノードは？ 媒介中心性 他のノードへの橋渡し役として重要なノードは？
13. 次数中⼼性 (degree centrality) (1/4) 注目ノードがいくつのノードと接しているか （どの程度エッジを持つか）を示す指標 0 2 1 3 4 5 𝐶' 𝑣" = deg(𝑣" ) 𝐶' 𝑣" = deg(𝑣" ) 𝑉 − 1 or ノードvi につながる エッジの数 𝐶' 𝑣% = 3
14. 次数中⼼性 (degree centrality) (2/4) 注目ノードがいくつのノードと接しているか （どの程度エッジを持つか）を示す指標 0 2 1 3 4 5 𝐶' 𝑣" = deg(𝑣" ) 𝐶' 𝑣" = deg(𝑣" ) 𝑉 − 1 or グラフに属するノードの数で 正規化することもある 𝐶' 𝑣% = 3
15. 次数中⼼性 (degree centrality) (3/4) 注目ノードがいくつのノードと接しているか （どの程度エッジを持つか）を示す指標 0 2 1 3 4 5 𝐶' 𝑣% = 3 # 次数中⼼性（正規化済み） nx.degree_centrality(G) # 次数中⼼性（正規化なし: 単なる次数） G.degree
16. 次数中⼼性 (degree centrality) (4/4) 有向グラフの場合、次数中心性を 入次数と出次数に分けて考えることもある ⼊次数 = 3 0 2 1 3 4 5 0 2 1 3 4 5 出次数 = 0 ⼊次数 = 1 出次数 = 2
17. エッジの本数が多い = 重要なノード？ 次数 = 3 次数 = 3 エッジの意味が友好関係としたとき、 影響力が強そうなはどちらのノードか？ ノードの数も重要だが，どんなノードとつながっているかも重要？
18. さまざまな中⼼性（⼀部） 近接中心性 他のノードに最も近いノードは？ 次数中心性 多くのノードと接続しているノードは？ 固有ベクトル中心性 重要なノードと多く接続しているノードは？ 媒介中心性 他のノードへの橋渡し役として重要なノードは？
19. 固有ベクトル中⼼性 (eigenvector centrality) (1/14) 堂々巡りの定義になっているけど，どうするの…？ 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2 重要度 = 1 重要度 = 1 重要度 = 1 重要度 = 1
20. 固有ベクトル中⼼性 (eigenvector centrality) (2/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2 重要度 = 1 重要度 = 1 重要度 = 1 重要度 = 1 とりあえず全てのノードの重要性を1として定義通り計算してみる…
21. 固有ベクトル中⼼性 (eigenvector centrality) (3/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2 重要度 = 1 重要度 = 1 重要度 = 1 𝑐( 𝑣) = 𝑐( 𝑣* + 𝑐( 𝑣% + 𝑐( 𝑣+ = 1 + 1 + 1 = 3 重要度 = 3 他のノードにも同じことをしてみる
22. 0 固有ベクトル中⼼性 (eigenvector centrality) (4/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 2 重要度 = 1 重要度 = 1 重要度 = 1 𝑐( 𝑣+ = 𝑐( 𝑣) + 𝑐( (𝑣% ) = 1 + 1 = 2
23. 固有ベクトル中⼼性 (eigenvector centrality) (5/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2 重要度 = 1→2 同じことを再度繰り返してみる 重要度 = 1→1 重要度 = 1→2 重要度 = 1→3
24. 固有ベクトル中⼼性 (eigenvector centrality) (6/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2 同じことを再度繰り返してみる そのまま繰り返すと重要度が無限に 増えていくので、各ノードの重要度の 二乗和が1になるよう制約を加える 重要度 = 1→2 重要度 = 1→1 重要度 = 1→2 重要度 = 1→3 𝟏𝟖 𝟏𝟖 𝟏𝟖 𝟏𝟖
25. 0 固有ベクトル中⼼性 (eigenvector centrality) (7/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 重要度 = 重要度 = 𝑐( 𝑣) = 𝑐( 𝑣* + 𝑐( 𝑣% + 𝑐( 𝑣+ = 2 18 + 2 18 + 1 18 = 5 18 重要度 = 2 18 2 18 1 18 5 18
26. 0 固有ベクトル中⼼性 (eigenvector centrality) (8/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 重要度 = 重要度 = 2 18 1 18 3 18 𝑐( 𝑣+ = 𝑐( 𝑣) + 𝑐( (𝑣% ) = 3 18 + 2 18 = 5 18 重要度 = 5 18
27. 0 固有ベクトル中⼼性 (eigenvector centrality) (9/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 重要度 = 重要度 = 2 18 → 5 18 2 18 → 5 18 1 18 → 3 18 重要度 = 3 18 → 5 18 同じことを延々と繰り返す
28. 0 固有ベクトル中⼼性 (eigenvector centrality) (10/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 重要度 = 重要度 = 𝑐( 23* 𝑣) = 𝑐( 2 𝑣* + 𝑐( 2 𝑣% + 𝑐( 2 𝑣+ 重要度 = 𝑐! " 𝑣# 𝑐! " 𝑣$ 𝑐! " 𝑣% 𝑐! "&% 𝑣' 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 隣接⾏列A 𝑐! "(𝑣' ) 𝑐! "(𝑣% ) 𝑐! "(𝑣$ ) 𝑐! "(𝑣# ) 重要度ベクトル cn E ⾏列Aとベクトルcn E の 積の⼀部になっている
29. 0 固有ベクトル中⼼性 (eigenvector centrality) (11/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 重要度 = 重要度 = 重要度 = 𝑐! "#$ = 𝐴𝑐! " 重要度 = 𝐶! " 𝑣# 𝐶! " 𝑣$ 𝐶! " 𝑣% 𝐶! "&% 𝑣' 繰り返しの計算は隣接行列ですっきり表現できる n回⽬の計算で得た 重要度のベクトル n+1回⽬の計算で得た 重要度のベクトル 隣接⾏列
30. 0 固有ベクトル中⼼性 (eigenvector centrality) (12/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 𝑐! " = 𝐴𝑐! # 𝑐! $ = 𝐴𝑐! " 𝑐! %&# = 𝐴𝑐! % … 無限に繰り返すと収束 𝑐! = 𝐴𝑐! 𝑐! ' = 𝐴𝑐! ' （つまり ）
31. 0 固有ベクトル中⼼性 (eigenvector centrality) (13/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 𝜆𝑐! = 𝐴𝑐! 実は上記中⼼性の定義に基づく 重要度の計算は、隣接⾏列Aの 固有ベクトルを求めることに相当 （最⼤固有値に対応する） 固有ベクトル中心性は隣接行列の固有ベクトルの要素値 𝜆𝑥 = 𝐴𝑥
32. 0 固有ベクトル中⼼性 (eigenvector centrality) (14/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2 # 固有ベクトル中⼼性 nx.eigenvector_centrality(G) # 上の結果は以下の計算で得られる # 第1番⽬の固有ベクトルと⼀致する import numpy as np A = nx.adjacency_matrix(G).toarray() np.linalg.eg(A).eigenvectors[:, 0]
33. 固有ベクトル中⼼性の⽐較 0 1 2 3 0 1 2 3 6 7 4 5 8 9 ノード0 = 0.612 ノード1 = 0.282 ノード2 = 0.523 ノード3 = 0.523 ノード0 = 0.416 ノード1 = 0.225 ノード2,3 = 0.491 ノード4,5 = 0.119 ノード6,7,8,9 = 0.258 中心性の値は相対的なものであること注意
34. 固有ベクトル中⼼性の限界 for 有向グラフ 1 0 4 2 3 5 1 0 4 2 3 5 強連結グラフ 計算可能 強連結グラフでない 計算不可能 ノード1 = 0 ノード4 = 0? 現実的には強連結でないグラフは多い…
35. さまざまな中⼼性（⼀部） 近接中心性 他のノードに最も近いノードは？ 次数中心性 多くのノードと接続しているノードは？ 固有ベクトル中心性 重要なノードと多く接続しているノードは？ 媒介中心性 他のノードへの橋渡し役として重要なノードは？
36. 媒介中⼼性 (betweenness centrality) (1/3) 3 6 5 4 1 2 0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか？ ココを通らなくても 他のノードに⾏ける グラフの左から右に ⾏くにはココを絶対 通る必要がある (例: コミュニティをつなぐ橋渡し役、交通の要衝etc..)
37. 媒介中⼼性 (betweenness centrality) (2/3) 3 6 5 4 1 2 0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか？ 媒介中⼼性= 9 15 媒介中⼼性= 0 15 媒介中⼼性= 8 15
38. 媒介中⼼性 (betweenness centrality) (3/3) 3 6 5 4 1 2 0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか？ 媒介中⼼性= 9 15 媒介中⼼性= 0 15 # 媒介中⼼性 cb = nx.betweenness_centrality(G) # ノード3の値 print(cb[3])
39. Hands-on タイム 以下のURLにアクセスして， 第11回のクイズを解いてみよう https://graphnote.hontolab.org/ 39
40. 回 実施日 トピック 9 06/13 グラフデータ 10 06/20 グラフ構造の諸指標 11 06/27 ノードの中心性 12 07/04 コミュニティ発見 13 07/11 ウェブグラフ 14 07/18 グラフ埋め込み 15 07/25 総合演習 – 社会ネットワーク分析 授業計画 40