【ネットワークの中心性指標 】NetworkXでグラフの中心性を可視化

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

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

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

## 各中心性の意味
### 次数中心性 (degree centrality)
ノードの**次数**。

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

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

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

### 媒介中心性 (betweenness centrality)

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3753744/e9b8ed3a-c088-4bdd-bc41-6c6e36c6ccfe.png)




### 近接中心性 (closeness centrality)
近接中心性は、あるノードから他のノードへの**平均距離**を表した指標です。
2つのノード$i,j$間の距離を$d_{ij}$とすると、ノード$i$から他ノードへの平均距離$l_{i}$は、以下のようになります。
``` math
l_{i} = \frac{1}{n} \sum_{j} d_{ij}
```

そこで、ノード$i$の近接中心性$C_{i}$は、$l_{i}$の逆数として、
``` math
C_{i} = \frac{1}{l_{i}} = \frac{n}{\sum_{j} d_{ij}}
```
と表現されます。

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

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

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

隣接行列を$A$として、
``` math
Ax= \kappa x
```
の解$x$が、固有ベクトル中心性を表します。


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

::: note info
[ペロン=フロベニウスの定理](https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%AD%E3%83%B3%EF%BC%9D%E3%83%95%E3%83%AD%E3%83%99%E3%83%8B%E3%82%A6%E3%82%B9%E3%81%AE%E5%AE%9A%E7%90%86)により、**非負行列**は
１．最大固有値が存在し、その固有値は**正**。
２．最大固有値に対する固有ベクトルは、**すべての成分が正**の値を取ることができる。
３．最大固有値の**重複度は１**。（重根でない）
という特徴があります。隣接行列$\mathbf{A}$は非負行列であることから、固有ベクトル中心性の計算の妥当性が導けます。
:::

なぜ、$Ax= \kappa x$の解を用いるか考えてみましょう。上式を少し変形し、
``` math
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になってしまい、意味をなさないケースがあります。

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

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


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




### カッツ中心性 (katz centrality)
カッツ中心性は、最初からすべてのノードに、定数$\beta$の中心性を与えようというものです。定義は以下です。
``` math
x_{i} = \alpha \sum_{j} A_{ij} x_{j} +\beta
```
ただし、$\alpha$と$\beta$は正の値です。

上式を行列形式で表現すると、
``` math
\mathbf{x} = \alpha \mathbf{A} \mathbf{x} +\beta \mathbf{1}
```
となり、これを$\mathbf{x}$について解くと、以下のようになります。
``` math
\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**というライブラリを使います。

``` python
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)
``` python
# 次数中心性 (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)
``` python
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）を計算する場合は、**単純グラフに変換**する必要があります。 

#### 単純グラフへの変換
``` python
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つの中心性指標をまとめて計算し、描画するコードは以下の通りです。

``` python
# 固有ベクトル中心性の計算
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を定義
``` python
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()
```

以下は描画するコードです。
``` python
draw_centrality(G, pos, eigen, "Eigenvector Centrality (固有ベクトル中心性)")
draw_centrality(G, pos, closeness, "Closeness Centrality (近接中心性)")
draw_centrality(G, pos, katz, "Katz Centrality (カッツ中心性)")

```



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



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




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