Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

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

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

Y. Yamamoto PRO

June 27, 2025

Transcript

41 slides
  1. 近接中⼼性 (closeness centrality) (1/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 0 2 1 3

    4 5 1 2 2 1 1 𝐶! 𝑣" = 1 𝑣" からの平均距離 = |𝑉| − 1 ∑#! 𝑑𝑖𝑠𝑡(𝑣" , 𝑣$ )
  2. 近接中⼼性 (closeness centrality) (3/5) 注目ノードとグラフ中の他のノードとの 距離が平均的にどの程度近いかを示す指標 ⾃分を除いたノードの数 0 2 1

    3 4 5 1 2 2 1 1 近接中⼼性は連結グラフにしか定義ができないことに注意 𝐶! 𝑣" = 1 𝑣" からの平均距離 = |𝑉| − 1 ∑#! 𝑑𝑖𝑠𝑡(𝑣" , 𝑣$ )
  3. 近接中⼼性 (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])
  4. 次数中⼼性 (degree centrality) (1/4) 注目ノードがいくつのノードと接しているか (どの程度エッジを持つか)を示す指標 0 2 1 3

    4 5 𝐶' 𝑣" = deg(𝑣" ) 𝐶' 𝑣" = deg(𝑣" ) 𝑉 − 1 or ノードvi につながる エッジの数 𝐶' 𝑣% = 3
  5. 次数中⼼性 (degree centrality) (2/4) 注目ノードがいくつのノードと接しているか (どの程度エッジを持つか)を示す指標 0 2 1 3

    4 5 𝐶' 𝑣" = deg(𝑣" ) 𝐶' 𝑣" = deg(𝑣" ) 𝑉 − 1 or グラフに属するノードの数で 正規化することもある 𝐶' 𝑣% = 3
  6. 次数中⼼性 (degree centrality) (3/4) 注目ノードがいくつのノードと接しているか (どの程度エッジを持つか)を示す指標 0 2 1 3

    4 5 𝐶' 𝑣% = 3 # 次数中⼼性(正規化済み) nx.degree_centrality(G) # 次数中⼼性(正規化なし: 単なる次数) G.degree
  7. エッジの本数が多い = 重要なノード? 次数 = 3 次数 = 3 エッジの意味が友好関係としたとき、

    影響力が強そうなはどちらのノードか? ノードの数も重要だが,どんなノードとつながっているかも重要?
  8. 固有ベクトル中⼼性 (eigenvector centrality) (2/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2

    重要度 = 1 重要度 = 1 重要度 = 1 重要度 = 1 とりあえず全てのノードの重要性を1として定義通り計算してみる…
  9. 固有ベクトル中⼼性 (eigenvector centrality) (3/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2

    重要度 = 1 重要度 = 1 重要度 = 1 𝑐( 𝑣) = 𝑐( 𝑣* + 𝑐( 𝑣% + 𝑐( 𝑣+ = 1 + 1 + 1 = 3 重要度 = 3 他のノードにも同じことをしてみる
  10. 0 固有ベクトル中⼼性 (eigenvector centrality) (4/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    重要度 = 2 重要度 = 1 重要度 = 1 重要度 = 1 𝑐( 𝑣+ = 𝑐( 𝑣) + 𝑐( (𝑣% ) = 1 + 1 = 2
  11. 固有ベクトル中⼼性 (eigenvector centrality) (5/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2

    重要度 = 1→2 同じことを再度繰り返してみる 重要度 = 1→1 重要度 = 1→2 重要度 = 1→3
  12. 固有ベクトル中⼼性 (eigenvector centrality) (6/14) 重要なノードに多く接しているノードほど 重要であるとする指標 0 3 1 2

    同じことを再度繰り返してみる そのまま繰り返すと重要度が無限に 増えていくので、各ノードの重要度の 二乗和が1になるよう制約を加える 重要度 = 1→2 重要度 = 1→1 重要度 = 1→2 重要度 = 1→3 𝟏𝟖 𝟏𝟖 𝟏𝟖 𝟏𝟖
  13. 0 固有ベクトル中⼼性 (eigenvector centrality) (7/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    重要度 = 重要度 = 重要度 = 𝑐( 𝑣) = 𝑐( 𝑣* + 𝑐( 𝑣% + 𝑐( 𝑣+ = 2 18 + 2 18 + 1 18 = 5 18 重要度 = 2 18 2 18 1 18 5 18
  14. 0 固有ベクトル中⼼性 (eigenvector centrality) (8/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    重要度 = 重要度 = 重要度 = 2 18 1 18 3 18 𝑐( 𝑣+ = 𝑐( 𝑣) + 𝑐( (𝑣% ) = 3 18 + 2 18 = 5 18 重要度 = 5 18
  15. 0 固有ベクトル中⼼性 (eigenvector centrality) (9/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    重要度 = 重要度 = 重要度 = 2 18 → 5 18 2 18 → 5 18 1 18 → 3 18 重要度 = 3 18 → 5 18 同じことを延々と繰り返す
  16. 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 の 積の⼀部になっている
  17. 0 固有ベクトル中⼼性 (eigenvector centrality) (11/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    重要度 = 重要度 = 重要度 = 𝑐! "#$ = 𝐴𝑐! " 重要度 = 𝐶# $ 𝑣% 𝐶# $ 𝑣& 𝐶# $ 𝑣' 𝐶# $(' 𝑣) 繰り返しの計算は隣接行列ですっきり表現できる n回⽬の計算で得た 重要度のベクトル n+1回⽬の計算で得た 重要度のベクトル 隣接⾏列
  18. 0 固有ベクトル中⼼性 (eigenvector centrality) (12/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    𝑐! " = 𝐴𝑐! # 𝑐! $ = 𝐴𝑐! " 𝑐! %&# = 𝐴𝑐! % … 無限に繰り返すと収束 𝑐! = 𝐴𝑐! 𝑐! ' = 𝐴𝑐! ' (つまり )
  19. 0 固有ベクトル中⼼性 (eigenvector centrality) (13/14) 重要なノードに多く接しているノードほど 重要であるとする指標 3 1 2

    𝜆𝑐! = 𝐴𝑐! 実は上記中⼼性の定義に基づく 重要度の計算は、隣接⾏列Aの 固有ベクトルを求めることに相当 (最⼤固有値に対応する) 固有ベクトル中心性は隣接行列の固有ベクトルの要素値 𝜆𝑥 = 𝐴𝑥
  20. 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]
  21. 固有ベクトル中⼼性の⽐較 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 中心性の値は相対的なものであること注意
  22. 固有ベクトル中⼼性の限界 for 有向グラフ 1 0 4 2 3 5 1

    0 4 2 3 5 強連結グラフ 計算可能 強連結グラフでない 計算不可能 ノード1 = 0 ノード4 = 0? 現実的には強連結でないグラフは多い…
  23. 媒介中⼼性 (betweenness centrality) (1/3) 3 6 5 4 1 2

    0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか? ココを通らなくても 他のノードに⾏ける グラフの左から右に ⾏くにはココを絶対 通る必要がある (例: コミュニティをつなぐ橋渡し役、交通の要衝etc..)
  24. 媒介中⼼性 (betweenness centrality) (2/3) 3 6 5 4 1 2

    0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか? 媒介中⼼性= 9 15 媒介中⼼性= 0 15 媒介中⼼性= 8 15
  25. 媒介中⼼性 (betweenness centrality) (3/3) 3 6 5 4 1 2

    0 注目ノードがそれ以外のノード間の経路に 含まれる割合を示す指標 → ノードがどの程度「経路上の要所」になっているか? 媒介中⼼性= 9 15 媒介中⼼性= 0 15 # 媒介中⼼性 cb = nx.betweenness_centrality(G) # ノード3の値 print(cb[3])
  26. 授業計画 41 回 トピック 9 グラフデータ 10 グラフ構造の諸指標 11 ノードの中心性

    12 コミュニティ発見 13 ウェブとグラフ 14 グラフ埋め込み 15 総合演習 – 社会ネットワーク分析

More Decks by Y. Yamamoto

Other Decks in Science