python(networkx)によるネットワーク分析メモ2 中心性

pythonによるネットワーク分析のメモ書きとなります。
networkxを使用します。

内容・コードがまとまっていないので、詳細については参考書の参照をお願いします。

機会があればしっかり勉強していこうと思います。

### 中心の定義
中心性には以下のような様々な定義がある。

- 他の多くの頂点とつながっている頂点
- その頂点が欠けるとグラフがばらばらになるような頂点
- 多くの経路上に現れる頂点
- 他の頂点に短い距離で到達できる頂点

### 次数中心性
多くの頂点と隣接している頂点は中心的とするものであり、頂点$v$の次数中心性は、その時数$k_v$で表される。
グラフ$G=(V,E)$の頂点数を$|V|=n$としたとき、すべての頂点の次数を表す次数ベクトル$k$は、隣接行列$A$と、各要素が1である列ベクトル$\boldsymbol{1}$を用いて、$k=A・\boldsymbol{1}$


```python
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
import networkx as nx

d = pd.read_csv('pos.csv', encoding='shift-jis')

# Graphオブジェクトの作成
G = nx.Graph()
G.add_nodes_from(np.unique([d.形態素1]+[d.形態素2]))
G.add_edges_from([(d.loc[i, '形態素1'], d.loc[i, '形態素2']) for i in range(len(d))])

# ネットワークの可視化
plt.figure(figsize=(6,6))
nx.draw(G, node_size=1500, node_color='lightblue', with_labels=True, font_family='MS Gothic')

print('degree centrality:')
for k, v in sorted(nx.degree_centrality(G).items(), key=lambda x: -x[1]):
    print(str(k)+":"+"{:.3f}".format(v)+" ", end="")
```

    degree centrality:
    サ変名詞:0.500 動詞:0.500 動詞性接尾辞:0.500 普通名詞:0.500 格助詞:0.500 接続助詞:0.375 副詞:0.250 副詞的名詞:0.250 句点:0.125 


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2358656/2172e645-c0a5-865a-ef1a-4ca52ec693d1.png)

    


### 固有ベクトル中心性
隣接する頂点の中心性も加味し、「他の中心的な頂点と隣接する頂点は中心的」とするものである。
周囲の頂点の中心性$x_i$から計算される$x_i'$は

```math
x_i'=\sum_iA_{ij}x_j
```

であり、列ベクトルと行列の積で表すと

```math
\boldsymbol{x}'=A\boldsymbol{x}
```

となる。
このような反復計算を繰り返すと、列ベクトルは最終的に$A$の最大固有値に対応する固有ベクトルに収束する。
得られた列ベクトルの$i$番目の成分が頂点$i$の固有ベクトル中心性である。


```python
print('eigenvector centrality')
for k, v in sorted(nx.eigenvector_centrality(G).items(), key=lambda x: -x[1]):
    print(str(k)+":"+"{:.3f}".format(v)+" ", end="")
```

    eigenvector centrality
    普通名詞:0.452 サ変名詞:0.451 格助詞:0.399 接続助詞:0.335 動詞性接尾辞:0.331 動詞:0.327 副詞的名詞:0.219 副詞:0.217 句点:0.097 

### Katz中心性
固有ベクトル中心性において、辺に向きがある有向グラフの場合に、他のどの頂点からも辺が入ってこない頂点は、中心性が0となります。
さらに、そのような頂点からしか辺が入ってこない頂点の中心性も0になってしまう問題がある。
Katz中心性は「固有ベクトル中心性に加えて、すべての頂点に一定量の中心性を与えたもの」である。

```math
x_i=\sum_iA_{ij}x_j+\beta
```

### PageRank
Katz中心性は、中心性の高い頂点が1つあると、それに隣接する頂点の中心性もすべて高くなってしまう。
そこで、頂点$i$の中心性を計算する際に、隣接する頂点$j$の中心性を、その頂点の次数$k_i$で割ったものを足すこととする。

```math
x_i=\sum_iA_{ij}\frac{x_j}{k_j}+\beta
```

### 媒介中心性
「2頂点間を結ぶ経路上にしばしば現れる頂点を中心的」とする考え方。
$n_{st}^i$を頂点$s$と$t$を結ぶパスが頂点$i$を通るときに1、そうでないときに0となるとしたとき、頂点$i$の媒介中心性は

```math
x_i=\sum_{st}n_{st}^i
```

と表せる。次数が小さい頂点であっても、媒介中心性が大きい場合がある。


```python
print('betweenness centrality')
for k, v in sorted(nx.betweenness_centrality(G).items(), key=lambda x: -x[1]):
    print(str(k)+":"+"{:.3f}".format(v)+" ", end="")
```

    betweenness centrality
    動詞:0.330 サ変名詞:0.220 格助詞:0.217 普通名詞:0.146 接続助詞:0.077 副詞:0.060 動詞性接尾辞:0.036 副詞的名詞:0.021 句点:0.000 

### 近接中心性
「ネットワークの他の頂点との平均距離が短い頂点を中心的」とするもの。
頂点$i$と頂点$j$の間の距離を$d_{ij}$とすると、$l_i=\frac{1}{n}\sum_jd_{ij}$が頂点$i$の中心性である。
値が小さいものの方がより中心的となる。


```python
print('closeness centrality')
for k, v in sorted(nx.closeness_centrality(G).items(), key=lambda x: -x[1]):
    print(str(k)+":"+"{:.3f}".format(v)+" ", end="")
```

    closeness centrality
    サ変名詞:0.667 動詞:0.615 普通名詞:0.615 格助詞:0.615 副詞:0.533 動詞性接尾辞:0.533 接続助詞:0.533 副詞的名詞:0.444 句点:0.400 

### 参考文献

https://www.amazon.co.jp/Python%E3%81%A7%E5%AD%A6%E3%81%B6%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E5%88%86%E6%9E%90-Colaboratory%E3%81%A8NetworkX%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F%E5%AE%9F%E8%B7%B5%E5%85%A5%E9%96%80-%E6%9D%91%E7%94%B0-%E5%89%9B%E5%BF%97/dp/4274224252/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=1MGFJGT5I662K&keywords=python+%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF&qid=1647165563&s=books&sprefix=python+%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%2Cstripbooks%2C215&sr=1-1