【Python】NetworkXでさまざまなネットワーク中心性を計算してみた

　ネットワークにおける中心的な頂点を見つけるという問題は、SNSにおける影響力の高い人を見つけたり、数多くの論文の中から重要なものを選んだり、災害発生時にどの現場でもたどり着ける適切な消防施設の場所を決めたりするために重要です。僕は仕事でネットワーク解析をしているわけではないのですが、いつか使うかもしれないと心の準備をしているのと、個人的に興味があったので勉強してみました。

中心性の定義

　以下のようにさまざまな定義がある。

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

中心性の定義の仕方によって、さまざまな種類の中心性が存在する。代表的なものに、次数中心性(Degree Centrality)、固有ベクトル中心性(Eigenvector Centrality)、Katz中心性, PageRank、近接中心性(Closeness Centrality)、媒介中心性(Betweenness Centrality)などがある。

次数中心性(Degree Centrality)

・多くの頂点と隣接している頂点 (Twitterのフォロワー数)

　次数中心性には、特定の頂点につながる新たなダミー頂点を大量に作るなどの局所的な操作で中心性をコントロールできてしまうという問題がある。

↓次数中心性の高いひとびと(meyou 2020/5/18)

固有ベクトル中心性(Eigenvector Centrality)

・多くの中心的な頂点とつながっている頂点（周辺の頂点の中心性も加味）。
・あるノードの中心性はそのノードに対してエッジを張っている全ノードの中心性の総和。

・上式の遷移を繰り返して収束したとき、以下が成り立つ。つまり、固有ベクトル中心性は隣接行列Aの最大固有値に対する固有ベクトルで与えられる。ただし、初期ベクトルが0ベクトルであったり、他の固有ベクトルの定数倍だったり、主固有ベクトルに直行したりしていた場合はこの限りではない。

・収束に必要な反復計算の回数は、ネットワークの頂点数に比較して非常に少ないことが知られている。
・有向グラフの場合、入次数0の頂点は中心性が0になってしまい、さらにそのような頂点からしか辺が入ってこない頂点の中心性も0になるという問題がある。

Katz中心性

・固有ベクトル中心性に加えて、全ての頂点に一定量の中心性を加えたもの。これにより固有ベクトル中心性において中心性が0になる問題を回避。

PageRank

・固有ベクトル中心性およびKatz中心性は、中心性の高い頂点が1つあるとそれに隣接する頂点の中心性もすべて高くなってしまう。これを解決するために、隣接する頂点jの中心性をその頂点jの次数で割ったものを足す。

・Googleの初期の検索エンジンにおいて、ハイパーリンクで結ばれたWebページのネットワークのなかから中心的なページを選ぶためのランキングアルゴリズムとして使用された。

媒介中心性(Betweenness Centrality)

・2頂点間を結ぶ経路上によく現れる頂点。
・2つのグループとその間を結ぶブリッジから構成されるネットワークなどは、次数が小さくても媒介中心性が大きい場合がある。

近接中心性(Closeness Centrality)

・他の頂点との平均距離が近い頂点で、以下の式の値が小さいほど中心的。
・ノードiの近接中心性　＝　(ノードの数 - 1) / (他ノードとノードiの距離の総和)

Zachary's karate clubで練習

Pythonとnetworkxで練習した。Jupyter Notebookで以下のコードを実行した。

まずはグラフを可視化した。

import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd

G = nx.karate_club_graph()
plt.figure(figsize=(8, 8))
nx.draw_spring(G, node_size=400, node_color='pink', with_labels=True, font_weight='bold')

次に各中心性を計算して、分析しやすいようにDataFrameにした。ふむふむ。

degree_centralities = list(nx.degree_centrality(G).values())
eigenvector_centralities = list(nx.eigenvector_centrality(G).values())
katz_centralities = list(nx.katz_centrality(G).values())
pagerank = list(nx.pagerank(G).values())
betweenness_centralities = list(nx.betweenness_centrality(G).values())
closeness_centralities = list(nx.closeness_centrality(G).values())

centralities = pd.DataFrame({"degree centrality":degree_centralities,
                            "eigenvector centrality":eigenvector_centralities,
                            "katz centrality":katz_centralities,
                            "pagerank":pagerank,
                            "betweenness centrality":betweenness_centralities,
                            "closeness centrality":closeness_centralities,
                            })

centralities

最も中心性の高いノードを調べた。ふむふむ。

centralities.idxmax()

参考

村田 剛志 (2019) 『Pythonで学ぶネットワーク分析』 株式会社 オーム社
ネットワークの中心性の話
次数中心性からPageRankからまた次数中心性