ネットワークの中心性指標
どうも、DeNAでマーケティングリサーチャー／データマイナー／データサイエンティストなどをやってる森本と申します。
ネットワークの中で中心的な役割を果たすノードの発見はネットワーク分析の大きな関心の一つです。それぞれのノードがネットワーク全体にどのように影響を与えるか、その答えを示すのが中心性指標です。今回は、この中心性指標の基本について解説します。
中心性（centrarity）はネットワーク分析の中でよく使われる指標の一つです。ネットワークを構成する各ノードがそのネットワークの中でどれくらい重要であるかを示す指標です。
鉄道の路線であれば多くの路線が乗り入れている駅が重要な駅と言えます。ウェブページであればより多くのページからリンクされているページが重要であるとみなされます。Twitter（現X）などのソーシャルネットワークであればフォロワー数が多いほど影響力が大きく重要なアカウントであると考えられます。
シンプルなネットワークで中心性の考え方を見てみましょう。ネットワーク内のすべてのノードがつながり合っている完全グラフの場合、各ノードの中心性はすべて等しくなります。すべてのノードが同じ重要性を持つためです。一方で、あるノードだけがすべてのノードとつながっているスターグラフでは、すべてのノードとつながっている特定のノードの中心性が高くなります。この特定のノードだけが他のノードとつながっていて重要性が高いためです。
中心性はネットワークの構造のみから決まるもので、ノードの属性は直接関係しません。社会ネットワークで言えば各個人の肩書や性格などは中心性と直接関係を持たないということになります。
もちろん、ノードの属性が中心性に影響を与えることはあります。社交的な人であれば中心性も大きくなるでしょう。しかし、中心性指標の算出にそれらの属性は使われません。
別記事で紹介されているPageRankも中心性の一種です。
代表的な中心性指標
中心性を評価する指標はいくつも提案されており、それぞれに特徴や注意すべき点がります。
ここから代表的な中心性指標を４つ挙げ、それぞれについて図解を紹介します。
- 近接中心性(closeness centrality)
- 次数中心性(degree centrality)
- 固有ベクトル中心性(eigenvector centrality)
- 媒介中心性(betweenness centrality))
近接中心性
近接中心性はノード間の距離に注目した指標です。「他のノードとの距離が小さいノードほど中心的である」というのが近接中心性です。
ここでいう距離とはあるノードからあるノードへ到着するために通過するエッジの数を指します。以下のグラフでは各ノードの数値はがゼロのノードからの最短距離を表しています。
あるノードについて他の各ノードとの最短距離の合計の逆数が近接中心性となります。
近接中心性（Closeness Centrality）は、あるノードが他の全てのノードにどれだけ「近い」かを測る指標です。具体的には、あるノードから他の全てのノードへの最短経路の長さの平均を計算します。数学的には以下のように定義されます。
ネットワークを G=(V,E) とし、V はノードの集合、E はエッジの集合とします。あるノード v の近接中心性 C(v) は以下のように定義されます。
ここで、d(v, u) はノード v からノード u への最短経路の長さを表します。この定義により、他の全てのノードに近いノードほど、近接中心性が高くなります。
次数中心性
ノードに接続されているエッジの数が次数中心性です。
有向グラフの場合、入ってくるエッジの数と出て行くエッジの数を区別する場合もあります。
Twitter（現X）であればフォロー数とフォロワー数に相当します。
固有ベクトル中心性
次数中心性はノードに接続されたエッジを単に数え上げただけでしたが、それぞれのエッジに固有の重みづけをしようとするのが固有ベクトル中心性です。
例えばウェブページの重要性を考えるとき、より多くのリンクを集めているページからのリンクはそうでないページからのリンクよりも重要だと考えるわけです。
ページランクはこの固有ベクトル中心性を発展させたもので、分離したグラフや有向グラフでも使えるように拡張されています。
数学的には以下のように定義されます。
ネットワークを G=(V,E) とし、V はノードの集合、E はエッジの集合とします。あるノード v の固有ベクトル中心性 E(v) は以下のように定義されます。
ここで、Auv は隣接行列の要素、λ は最大固有値、E(u) はノード u の固有ベクトル中心性を表します。
媒介中心性
ここまでの中心性指標は距離や次数に注目していましたが、媒介中心性はネットワークにおける経路に注目した中心性です。
すべてのノード間の経路を考えたとき、該当のノードを通過する頻度が媒介中心性になります。
次数が小さくとも媒介中心性が大きくなることはあります。例えばいくつかのネットワークと、それらのネットワークをつなぐ橋の役割を果たすノードで構成されるネットワークの場合、橋の役割を果たすノードの媒介中心性が高くなります。
媒介中心性の高いノードを取り除くとネットワークがバラバラになってしまうことが分かると思います。媒介中心性はネットワークとネットワークを結び付ける力の強さを表します。
数学的には以下のように定義されます。
ネットワークを G=(V,E) とし、V はノードの集合、E はエッジの集合とします。あるノード v の固有ベクトル中心性 E(v) は以下のように定義されます。
ここで、Auv は隣接行列の要素、λ は最大固有値、E(u) はノード u の固有ベクトル中心性を表します。
中心性指標の違い
有名な空手クラブのネットワークを例に各中心性指標の違いを見てみましょう。
下図では各中心性指標をノードの大きさと色で表しています。
近接中心性はバラツキが小さく、媒介中心性はバラツキが大きいことが分かります。
指標間の関係を確認します。
このケースでは次数中心性と媒介中心性がほとんど同じになっているようです。
経験的には、次数を基にした固有ベクトル中心性やページランクと、経路を基にした媒介中心性の両方に注目して解釈を行うと理解がしやすいようです。
コード例
最後に中心性指標を算出するR言語とPythonのコード例を掲載します。R言語については「中心性指標の違い」の項で示した各中心性指標のネットワーク図を描くコードも載せています。
# Python
import pandas as pd
import networkx as nx
# 空手クラブのデータを呼び出す
G = nx.karate_club_graph()
# 各中心性指標を算出し格納する
closeness = list(nx.closeness_centrality(G).values()) # 近接中心性
degree = list(nx.degree_centrality(G).values()) # 次数中心性
eigen = list(nx.eigenvector_centrality(G).values()) # 固有ベクトル中心性
pagerank = list(nx.pagerank(G).values()) # ページランク
between = list(nx.betweenness_centrality(G).values()) # 媒介中心性
# 算出された中心性指標の確認
dict1 = dict(
closeness = closeness,
degree = degree,
eigen = eigen,
pagerank = pagerank,
between = between
)
pd.DataFrame(data = dict1)# R
library(igraph)
library(tidygraph)
library(ggraph)
library(patchwork)
# 空手クラブのデータを呼び出す
karate <- create_notable("Zachary")
# 各中心性指標を算出し格納する
g <- karate |>
mutate(
closeness = centrality_closeness(), # 近接中心性
degree = centrality_degree(mode = "all"), # 次数中心性
eigen = centrality_eigen(), # 固有ベクトル中心性
pagerank = centrality_pagerank(), # ページランク
between = centrality_betweenness() # 媒介中心性
)
# 算出された中心性指標の確認
g |>
activate(nodes) |>
as_tibble()
# 描画関数の定義
my_plot <- function(g, centrality, title) {
set.seed(1)
g |>
ggraph(layout = "fr") +
geom_edge_link(color = "gray") +
geom_node_point(aes(size = centrality, fill = centrality), shape = 21, color = "black") +
scale_size_continuous(range = c(3, 12)) +
scale_fill_gradient(low = "#005aff", high = "#ff4b00") +
theme_graph() +
theme(aspect.ratio = 1, legend.position = "none") +
labs(title = title)
}
# 描画
p1 <- my_plot(g, V(g)$closeness, "近接中心性")
p2 <- my_plot(g, V(g)$degree, "次数中心性")
p3 <- my_plot(g, V(g)$eigen, "固有ベクトル中心性")
p4 <- my_plot(g, V(g)$pagerank, "ページランク")
p5 <- my_plot(g, V(g)$between, "媒介中心性")
# 配置
p1 + p2 + p3 + p4 + p5 + plot_layout(ncol = 3)参考文献
Stanford CS224W Analysis of Networks Lecture 15 — Network Centrality
