😸

Python(NetworkX)でネットワークの中心性を求めたい

2022/06/04に公開

中心性とは?

ネットワークにおけるノードやリンクの重要性を表わす指標です。 例えば、ネットワーク中心にあるものに介入を行うことで、中心にないものと比較して、より介入効果が上がることなどが考えられます。


例題

基本的に、TJOさんのページの例を使用しました。

import pandas as pd
import networkx as nx

gd = nx.DiGraph()
gg = nx.Graph()

for node in ["A", "B", "C", "D", "E", "F", "G", "H"]:
  gd.add_node(node)
  gg.add_node(node)

edges = [
    ("A", "H"), ("C", "A"), ("A", "B"),
    ("F", "B"), ("C", "H"), ("E", "C"),
    ("F", "C"), ("H", "C"), ("C", "D"),
    ("H", "D"), ("B", "E"), ("D", "E"),
    ("H", "E"), ("A", "F"), ("B", "F"),
    ("D", "F"), ("E", "F"), ("F", "G"),
    ("D", "G"),
]
gd.add_edges_from(edges)
gg.add_edges_from(edges)

pos = nx.spring_layout(gd, seed=1)
nx.draw(gd, pos, with_labels=True, node_color="#cde1f5")
nx.draw(gg, pos, with_labels=True, node_color="#cde1f5")

【無向グラフ版】

【有向グラフ版】

なんとなくF,Hあたりが中心っぽい位置にいますね。


今回求める中心性

中心性指標もたくさんあります。先程のTJOさんのページに記載のものをまとめてみました。

名前 英語名 特徴
次数中心性 Degree centrality 多くのエッジ(=他ノードとの関係性)を持つノードを高く評価する指標
固有ベクトル中心性 Eigenvector centrality 次数中心性の高いノードとつながっているノードを評価するような指標
ページランク PageRank 固有ベクトル中心性の流入を重視するようにした上で、有向グラフにも簡易に適用できるようにした指標
媒介中心性 Betweeness centrality あるノードが他のノード間の最短経路上に位置する程度を中心性指標としたもの
情報中心性 Information centrality 精度の高い情報を受け取れる人(ノード)の評価を高くするような中心性 ※無向グラフのみ

ソースコード

import pandas as pd
import networkx as nx

gd = nx.DiGraph()
gg = nx.Graph()

for node in ["A", "B", "C", "D", "E", "F", "G", "H"]:
  gd.add_node(node)
  gg.add_node(node)

edges = [
    ("A", "H"), ("C", "A"), ("A", "B"),
    ("F", "B"), ("C", "H"), ("E", "C"),
    ("F", "C"), ("H", "C"), ("C", "D"),
    ("H", "D"), ("B", "E"), ("D", "E"),
    ("H", "E"), ("A", "F"), ("B", "F"),
    ("D", "F"), ("E", "F"), ("F", "G"),
    ("D", "G"),
]
gd.add_edges_from(edges)
gg.add_edges_from(edges)

# pos = nx.spring_layout(gd, seed=1)
# nx.draw(gd, pos, with_labels=True, node_color="#cde1f5")
# nx.draw(gg, pos, with_labels=True, node_color="#cde1f5")

# 次数中心性(degree centrality)
gd_degree_centrality = pd.Series(nx.degree_centrality(gd), name="次数中心性")
gg_degree_centrality = pd.Series(nx.degree_centrality(gg), name="次数中心性")

# 固有ベクトル中心性:Eigenvector centrality
gd_eigenvector_centrality = pd.Series(nx.eigenvector_centrality(gd), name="固有ベクトル中心性")
gg_eigenvector_centrality = pd.Series(nx.eigenvector_centrality(gg), name="固有ベクトル中心性")

# ページランク:PageRank
gd_pagerank = pd.Series(nx.pagerank(gd), name="ページランク")
gg_pagerank = pd.Series(nx.pagerank(gg), name="ページランク")

# 媒介中心性:Betweeness centrality
gd_betweenness_centrality = pd.Series(nx.betweenness_centrality(gd), name="媒介中心性")
gg_betweenness_centrality = pd.Series(nx.betweenness_centrality(gg), name="媒介中心性")

# 情報中心性:Information centrality
gg_information_centrality = pd.Series(nx.information_centrality(gg), name="情報中心性")

# 有向グラフ版ランキング(rankを外すと生値が出ます)
gd_centrality_rank = pd.concat([
  gd_degree_centrality,
  gd_eigenvector_centrality,
  gd_pagerank,
  gd_betweenness_centrality,
], axis=1).rank(ascending=False)

# 無向グラフ版ランキング(rankを外すと生値が出ます)
gg_centrality_rank = pd.concat([
  gg_degree_centrality,
  gg_eigenvector_centrality,
  gg_pagerank,
  gg_betweenness_centrality,
  gg_information_centrality
], axis=1).rank(ascending=False)

# 中心性が高い順にランキング。値が小さいほど中心に近い。
gd_centrality_rank.loc[gd_centrality_rank.mean(axis=1).sort_values().keys()]

# 中心性が高い順にランキング。値が小さいほど中心に近い。
gg_centrality_rank.loc[gg_centrality_rank.mean(axis=1).sort_values().keys()]

【無向グラフ版ランキング】

【有向グラフ版ランキング】

Colab版は以下
https://colab.research.google.com/drive/1Gx5TWahaJRAxqvdy3HV30nJSfFVGHXLr#scrollTo=PjUnTcZAAdWO

Fが一番高いのはほぼどの指標でも同じようです。次いで高いのは指標次第ですが、C,D,Eあたりが高い傾向にありますね。

Discussion