中心性指標

グラフにおける中心性を表す指標として、

・次数中心性 (degree centrality)
・媒介中心性 (betweenness centrality)
・近接中心性 (closeness centrality)
・固有ベクトル中心性 (eigenvector centrality)
・カッツ中心性　(katz centrality)

があります。本記事では、これらの意味や性質と、Pythonによる実装例を紹介します。

各中心性の意味

次数中心性 (degree centrality)

ノードの次数。

*次数とは、そのノード（点）と隣接するノードの数。

例1）友好関係：多くの友達や知り合いを持っている人は影響力が大きい。

例2）論文の引用関係：有向グラフと捉え、多く引用されている論文は学術的貢献度が大きい。

媒介中心性 (betweenness centrality)

あるノードの媒介中心性とは、それ以外の2つのノード間の最短経路にどのくらいの割合で入っているか、を表す指標です。

ただし、下の図¹のようなネットワークの場合、Aは必要以上に中心性が大きく計算されてしまう、という特徴があります。

近接中心性 (closeness centrality)

近接中心性は、あるノードから他のノードへの平均距離を表した指標です。
2つのノード$i,j$間の距離を$d_{ij}$とすると、ノード$i$から他ノードへの平均距離$l_{i}$は、以下のようになります。

l_{i} = \frac{1}{n} \sum_{j} d_{ij}

そこで、ノード$i$の近接中心性$C_{i}$は、$l_{i}$の逆数として、

C_{i} = \frac{1}{l_{i}} = \frac{n}{\sum_{j} d_{ij}}

と表現されます。

例えば、社会ネットワークにおいては、近接中心性が低い人=自分の意見が他の人に通りにくい、拡散されにくいことを意味しています。

固有ベクトル中心性 (eigenvector centrality)

ノード$i$の媒介中心性とは、隣接行列$A$の固有ベクトル$x$の$i$番目の要素を指します。Bonacich(1987)²の中で初めて提案されました。

固有ベクトル中心性は、友達の数だけでなく、友達の多い友達を持っているのかを考慮に入れた指標です。例えば、友達の数が少なくても、そのうちの一人がアメリカの大統領であれば、ネットワークにおける影響力は大きいでしょう。

隣接行列を$A$として、

Ax= \kappa x

の解$x$が、固有ベクトル中心性を表します。

友達の多い友達を持っていれば大きくなる指標です。

ペロン=フロベニウスの定理により、非負行列は
１．最大固有値が存在し、その固有値は正。
２．最大固有値に対する固有ベクトルは、すべての成分が正の値を取ることができる。
３．最大固有値の重複度は１。（重根でない）
という特徴があります。隣接行列$\mathbf{A}$は非負行列であることから、固有ベクトル中心性の計算の妥当性が導けます。

なぜ、$Ax= \kappa x$の解を用いるか考えてみましょう。上式を少し変形し、

x_{i} = \kappa^{-1} \sum_{j=1}^{n}A_{ij} x_{j}

とします。$A_{ij}$はノード$j$がノード$i$と隣接していれば1、隣接していなければ0であるため、$\sum_{j=1}^{n}A_{ij} x_{j}$は、「ノード$i$と隣り合うノードの$x_{j}$を足し合わせたもの」です。

よって、$**x_{i}$は、ノード$i$に隣接するノードの$x_{j}$の和に比例ということから、友達の中心性が高いと自分の中心性も高いという中心性指標になります。

ここで、固有ベクトル中心性が高くなるのは、
・友達の数が多い　（$x_{j}$は小さくても次数が高ければ$x_{i}$は大きい）
・友達の中心性が高い　（$x_{j}$が大きい）
場合です。

しかし、Acyclic Networkと呼ばれる、サイクルを持たない有向グラフ（有向非巡回グラフともいう。文献引用など）の場合には、固有ベクトル中心性が0になってしまい、意味をなさないケースがあります。

入次数（いりじすう、in-degree）が0だと、固有ベクトル中心性は0です。

まだ、Webページのリンクのように、多くの人が見る有名なリンクと繋がっているからといって、そのサイトが重要であるかどうかは測れません。

そこで、提案されているのが、カッツ中心性です。

カッツ中心性 (katz centrality)

カッツ中心性は、最初からすべてのノードに、定数$\beta$の中心性を与えようというものです。定義は以下です。

x_{i} = \alpha \sum_{j} A_{ij} x_{j} +\beta

ただし、$\alpha$と$\beta$は正の値です。

上式を行列形式で表現すると、

\mathbf{x} = \alpha \mathbf{A} \mathbf{x} +\beta \mathbf{1}

となり、これを$\mathbf{x}$について解くと、以下のようになります。

\mathbf{x} = \beta (\mathbf{I} - \alpha \mathbf{A})^{-1} \mathbf{1}

ここで、カッツ中心性はパラメータ$\alpha, \beta$に依存しますが、$\alpha$は、$1/\kappa_{1}$以下に設定すると良いと言われています。ただし、$\kappa_{1}$は、隣接行列$\mathbf{A}$の最大固有値です。

実装例

では、実際に中心性を計算してみましょう。せっかくなので、仮想のネットワークではなく、実際の道路・街路網を使ってみましょう。PythonのNetworkxというライブラリを使うと、ネットワークの描画から中心性の計算まですべて簡単にできます。

今回は、私が単純に好きで興味のあった新宿御苑の園路でやってみます。

新宿御苑の園路ネットワークを取得

実際の道路網の取得には、Open Street Map、osmnxというライブラリを使います。

import osmnx as ox
import networkx as nx

# 新宿御苑の歩行ネットワーク取得
place = "Shinjuku Gyoen, Tokyo, Japan"
G = ox.graph_from_place(place, network_type='walk')

ox.plot_graph(G)

中心性指標を計算し可視化

NetworkXは、すでに中心性指標を計算するライブラリとして用意されています。nx.○○_centrality(G)とすれば、○○に入れた各中心性を求めることができます。

次数中心性 (degree centrality)

# 次数中心性 (degree_centrality) を計算
centrality = nx.degree_centrality(G)

# 可視化：中心性に応じてノードの色を変える
nc = [centrality[node] for node in G.nodes]

fig, ax = ox.plot_graph(
    G,
    node_color=nc,
    node_size=20,
    edge_linewidth=0.5,
    edge_color="gray",
    bgcolor="white"
)

媒介中心性 (betweeness centrality)

import matplotlib.pyplot as plt

# 媒介中心性を計算
centrality = nx.betweenness_centrality(G)

# 可視化：中心性に応じてノードの色を変える
nc = [centrality[node] for node in G.nodes]

fig, ax = ox.plot_graph(
    G,
    node_color=nc,
    node_size=20,
    edge_linewidth=0.5,
    edge_color="gray",
    bgcolor="white"
)

ここで、OpenStreetMapによって取得したグラフ（ネットワーク）は、MultiGraph / MultiDiGraph（多重辺グラフ）として扱われます。

NetworkXで、固有ベクトル中心性(Eigenvector Centrality)とカッツ中心性（Katz Centrality）、近接中心性（Closeness Centrality）を計算する場合は、単純グラフに変換する必要があります。

単純グラフへの変換

import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt

# ネットワーク取得（例：新宿御苑）
G_multi = ox.graph_from_place("Shinjuku Gyoen, Tokyo, Japan", network_type="walk")

# 無向単純グラフに変換（多重辺を単一エッジに統合）
G = nx.Graph(G_multi)

固有ベクトル中心性・近接中心性・カッツ中心性

単純グラフに変換したのち、これら3つの中心性指標をまとめて計算し、描画するコードは以下の通りです。

# 固有ベクトル中心性の計算
eigen = nx.eigenvector_centrality(G, max_iter=1000)

# 近接中心性
closeness = nx.closeness_centrality(G)

# カッツ中心性
katz = nx.katz_centrality(G, alpha=0.005, beta=1.0, max_iter=1000)

中心性を計算する関数draw_centralityを定義

def draw_centrality(G, pos, centrality, title):
    plt.figure(figsize=(10, 10))
    nodes = nx.draw_networkx_nodes(
        G,
        pos,
        node_color=list(centrality.values()),
        cmap=plt.cm.viridis,
        node_size=20
    )
    nx.draw_networkx_edges(G, pos, edge_color="lightgray", width=0.5)
    plt.colorbar(nodes, label="Centrality")
    plt.title(title)
    plt.axis("off")
    plt.show()

以下は描画するコードです。

draw_centrality(G, pos, eigen, "Eigenvector Centrality (固有ベクトル中心性)")
draw_centrality(G, pos, closeness, "Closeness Centrality (近接中心性)")
draw_centrality(G, pos, katz, "Katz Centrality (カッツ中心性)")

まとめ

今回は、NetworkXを用いて、ネットワークの様々なネットワークの中心性を計算しました。今回のように、OpenStreetMapを用いることで、実際の街路ネットワークに適用することができます。

この記事が少しでも参考になると思っていただけたら、いいねやフォローをしていただけると大変力になります。

Mark Newman (2018)：Networks Second Edition, Oxford Press. ↩
Phillip Bonacich (1987)：Power and Centrality: A Family of Measures,American Journal of Sociology. ↩