Zenn
🔁

【ネットワークの中心性】vol.5 固有ベクトル中心性

2023/09/18に公開
network
グラフ理論
線形代数
ネットワーク分析
ネットワーク科学
tech

シリーズの目次

  1. Introduction
  2. 線形代数
  3. グラフ理論
  4. 次数中心性
  5. 固有ベクトル中心性
  6. Katz 中心性
  7. PageRank

ネットワーク構造をどう組み込むか

前回の記事では，次数中心性はシンプルで計算しやすい反面，自分の近傍のローカルな情報しか扱えず，ネットワーク全体の構造が持つグローバルな情報を無視してしまうため，ノードのランキング機能を果たせない，あるいはノードを正当に評価できないという問題があることを確認しました．

もう一つ次数中心性の粗さを挙げるとすれば，すべてのつながりを同等に評価している点があります．現実のネットワークにおいて，自分の近傍ノードの重要性がすべて等しいとは限りません．多くの場合，あるノードの重要性はその近傍ノード自体がどれだけ重要かに依存します．極端な例を挙げれば，世界にたった一人しか友達がいなかったとしても，その友達が首相や大統領レベルの人であれば，自分の重要性は比較的高くなるわけです．中心性を計算するには，友達が何人いるかだけでなく，誰を知っているかも加味すべきです．このように，中心性は重要なノードにつながっているノードほど重要であるという再帰性 (recursive property) を持つことになります．

この再帰性を考慮して次数中心性を拡張したものが固有ベクトル中心性 (eigenvector centrality) です [Bonacich, 1987]．単純に友達の数をスコアとして与えるのではなく，友達の持つ中心性に比例したスコアをノードに割り振っていきます．あるノードのスコアを計算するために，他すべてのノードのスコアをすでに知っている必要があるというのは一見堂々巡りに思えますが，それを綺麗に解決してくれるのが固有ベクトルです．

【無向グラフ】固有ベクトル中心性

固有ベクトル中心性の基本的なアイデアを理解するために，まずは無向グラフで固有ベクトル中心性を定義します．簡単のため，ここでは連結な無向グラフを考えます．無向グラフ G(V,E),|V|=n において，ノード i の固有ベクトル中心性を x_i とし，それを要素に持つベクトルを \bm{x} \in \R^{|V|} と表記します．A = (a_{ij})_{n \times n} は G の隣接行列です．


図1：固有ベクトル中心性の概念図

固有ベクトル中心性の再帰性から，x_i はノード i の近傍ノード N_G(i) が持つ固有ベクトル中心性の合計に比例すると考えられます．

\begin{align} x_i \propto \sum_{j \in N_G(i)} x_j \end{align}

無向グラフが連結であるとき隣接行列は既約なので，ひとまず比例定数をA のスペクトル半径 \rho(A) の逆数でおくと，

\begin{align} x_i = \frac{1}{\rho(A)}\sum_{j \in N_G(i)} x_j \end{align}

と書けます[1]．さらに，隣接行列を使えば

\begin{align} x_i = \frac{1}{\rho(A)}\sum_{j=1}^{n} a_{ij}x_j~~~~~~~~\forall i = 1,\dots,n \end{align}

となります[2]．(3) 式の右辺は a_{ij}\in\{0,1\} に重み x_j をかけて j についての和をとっており，エッジ (i,j) に中心性 x_j を重みとして付与した重み付きネットワーク（図1）としても解釈できます．このように x_i を定義することで，ノード i の中心性の値は，

  1. i の持つエッジの本数が多いとき
  2. i の隣接ノードの中心性が高いとき

に大きくなることがわかります．1つ目は次数中心性と変わりませんが，2つ目で重要なノードとつながっているほど重要であるというアイデアを回収しています．このように定義された固有ベクトル中心性では，控えめな中心性を持つ友達をたくさん持つか，高い中心性を持つ少数の友達を持つか（あるいはその両方）のどちらかによって，高い中心性を達成することができます．友達がたくさんいることで影響力を持つこともあれば，友達が少なくても友達の影響力が大きければ影響力があると見なせるため，固有ベクトル中心性の定義は妥当だと言えるでしょう．

ところで，(3) 式をベクトル形式で書くと

\begin{align} \bm{x} = \frac{1}{\rho(A)}A\bm{x} \iff A\bm{x} = \rho(A)\bm{x} \end{align}

となります．これは固有ベクトルの定義そのものです．再帰性を考慮して次数中心性を拡張していくと，実は隣接行列の固有ベクトルを求める問題に帰着するというわけです．さらに，A は非負行列なのでペロン＝フロベニウスの定理から，\rho(A) に属する固有ベクトル \bm{x} は非負ベクトル \bm{x}\in\R_+ であることが保証されます．中心性が負の値や虚数になっては困りますから，中心性を考える上でこの性質は非常にありがたいことです．

また，今回のようにネットワークが連結であれば，隣接行列は既約ですので A の支配的な固有値 \rho(A) は正の単純固有値であり，したがって固有ベクトル中心性（支配的な固有ベクトル）は，厳密に正のベクトル \bm{x} \gg \bm{0} で正のスカラー倍の差を除いて一意に決まります[3]．ノードをランク付けしなければならないという実用上，連結な無向ネットワークであれば必ず固有ベクトル中心性が正の実数で求まるというのは嬉しいですよね．

中心性指標の目的は通常，ネットワーク内で最も重要なノードを選び出すか，あるいは最も重要なノードから最も重要でないノードにランク付けすることなので，重要なのは異なるノードの相対的なスコアであって，絶対的な数値ではありません．したがって，中心性指標自体は，それが隣接行列の固有ベクトルであるならば，スカラー倍の範囲内で任意にとられても構わないわけです．

ネットワーク全体の構造を反映しているか

再帰性を考慮した結果，隣接行列の支配的な固有ベクトルとして定義される固有ベクトル中心性ですが，ネットワーク構造が持つグローバルな情報を無視するという次数中心性の問題は解決できているのでしょうか．定義をもう一度確認すると，ノード i の固有ベクトル中心性は

\begin{align*} x_i = \frac{1}{\rho(A)}\sum_{j=1}^{n} a_{ij}x_j \end{align*}

でした．この関係が任意の i = 1,\dots,n について成り立つというわけです．i さんの中心性を計算するのに，i さんの友達全員の中心性を計算する必要があり，同じことがその友達にも言え，さらにその友達にも...（以下略）ということなので，固有ベクトル中心性の定義式は暗にネットワーク全体の構造の情報を使用していることがわかります．

【有向グラフ】固有ベクトル中心性

有向グラフではハブ中心性とオーソリティ中心性という2つの評価軸を持つ中心性を考えることができるのでした．固有ベクトルについてもハブベース固有ベクトル中心性 (hub-based eigenvector centrality) とオーソリティベース固有ベクトル中心性 (authority-based eigenvector centrality) を定義できます．以下，有向グラフ G(V,E),|V|=n を考え，A = (a_{ij})_{n \times n} を G の隣接行列とします．ノード i のハブベース固有ベクトル中心性を e_i とし，それを要素に持つベクトルを \bm{e} \in \R^n，ノード j のオーソリティベース固有ベクトル中心性を \varepsilon_j とし，それを要素に持つベクトルを \bm{\varepsilon} \in \R^n と表記します．

ハブベース固有ベクトル中心性


図2：ハブベース固有ベクトル中心性の概念図

ノード i のハブベース固有ベクトル中心性 e_i は，i の出近傍 N_G^{\text{out}}(i) が持つ中心性の合計に比例すると考えられるので，

\begin{align} e_i = \frac{1}{\rho(A)}\sum_{j \in N_G^{\text{out}}(i)} e_j \end{align}

と定義されます．このように e_i を定義することで，ノード i の中心性の値は，

  1. i から出るエッジの本数（出近傍 N_G^{\text{out}}(i) の数）が多いとき
  2. i の出近傍の中心性 e_j が高いとき

に大きくなります．(5) 式は隣接行列を使えば

\begin{align} e_i = \frac{1}{\rho(A)}\sum_{j=1}^{n} a_{ij}e_j~~~~~~~~\forall i = 1,\dots,n \end{align}

と書け，さらにこれをベクトル形式で書くと

\begin{align} \bm{e} = \frac{1}{\rho(A)}A\bm{e} \iff A\bm{e} = \rho(A)\bm{e} \end{align}

と変形でき，ハブベース固有ベクトル中心性の計算は，隣接行列の支配的な右固有ベクトルを求める問題に帰着します．G が強連結であるときは，ハブベース固有ベクトル中心性は厳密に正のベクトル \bm{e}\in\R^n_{++} で，正のスカラー倍の差を除いて一意に決まります．

証明

G が強連結であるとき，連立方程式 (6) は正のスカラー倍の差を除いて一意な解 \bm{e}\in\R^n_{++} を持つことを示せば良い．G が強連結なので，隣接行列 A は既約の非負行列である．ペロン＝フロべニウスの定理より，A のスペクトル半径 \rho(A) は正の単純固有値であり，\rho(A) に属する右固有ベクトル \bm{e} は厳密に正のベクトル \bm{e} \gg \bm{0} である．単純固有値はスカラー倍の差を除いて一意の固有ベクトルを持つため，A\bm{e} = \rho(A)\bm{e} で定義される固有ベクトル \bm{e} は正のスカラー倍の差を除いて一意に定まる．したがって，\bm{e}を要素で書き下した連立方程式 (6) も正のスカラー倍の差を除いて一意な解 \bm{e}\in\R^n_{++} を持つ．

オーソリティベース固有ベクトル中心性


図3：オーソリティベース固有ベクトル中心性の概念図

ノード j のオーソリティベース固有ベクトル中心性 \varepsilon_j は，j の入近傍 N_G^{\text{in}}(j) が持つ中心性の合計に比例すると考えられるので，

\begin{align} \varepsilon_j = \frac{1}{\rho(A)}\sum_{i \in N_G^{\text{in}}(j)} \varepsilon_i \end{align}

と定義されます．このように \varepsilon_j を定義することで，ノード j の中心性の値は，

  1. j に入ってくるエッジの本数（入近傍 N_G^{\text{in}}(j) の数）が多いとき
  2. j の入近傍の中心性 \varepsilon_i が高いとき

に大きくなります．(8) 式は隣接行列を使えば

\begin{align} \varepsilon_j = \frac{1}{\rho(A)}\sum_{i=1}^{n} a_{ij}\varepsilon_i~~~~~~~~\forall j = 1,\dots,n \end{align}

と書け，さらにこれをベクトル形式で書くと

\begin{align} \bm{\varepsilon} = \frac{1}{\rho(A)}A^\top\bm{\varepsilon} \iff A^\top\bm{\varepsilon} = \rho(A)\bm{\varepsilon} \end{align}

と変形でき，オーソリティベース固有ベクトル中心性の計算は，隣接行列の支配的な左固有ベクトルを求める問題に帰着します．G が強連結であるときは，オーソリティベース固有ベクトル中心性は厳密に正のベクトル \bm{\varepsilon}\in\R^n_{++} で，正のスカラー倍の差を除いて一意に決まります．このことはハブベース固有ベクトル中心性と同様に示すことができます．

Python による実装

隣接行列 A について既約性よりも強い条件である原始性が成り立つ時は，原始性のもとで成り立つペロン＝フロベニウスの定理：

\begin{align} \left[\frac{A}{\rho(A)}\right]^m \to ~\bm{e}\bm{\varepsilon}^\top~~~~(m \to \infty)~~~~\text{where } \left< \bm{\varepsilon}, \bm{e} \right> = 1 \end{align}

を活用して固有ベクトル中心性を計算することができます．(11) 式より c\equiv\bm{\varepsilon}^\top \bm{1} とすると

\begin{align} \left[\frac{A}{\rho(A)}\right]^m \bm{1} \to ~c\bm{e}~~~~(m \to \infty) \end{align}

が成り立ちます．\rho(A) が求められるという条件のもとでは，\rho(A)^{-m}A^m\bm{1} を十分大きな m で評価すれば，支配的な右固有ベクトルのスカラー倍を得ることができます．左固有ベクトルが欲しい場合も，(11) 式で左から \bm{1}^\top を作用させれば支配的な左固有ベクトルのスカラー倍を得ることができます．

しかし，現実のネットワークで原始性という強い条件を満たすのは難しいため，ここでは代替案として固有値問題を解くアルゴリズムであるべき乗法 (power method) を使用します．まず，隣接行列 A のスペクトル半径 \rho(A) を計算する spectral_radius() 関数を定義します．

import numpy as np

def spectral_radius(M):
    """
    Compute the spectral radius of M.
    """
    return np.max(np.abs(np.linalg.eigvals(M)))

この spectral_radius() 関数を使って固有ベクトル中心性を計算する eigenvector_centrality() 関数を定義します．計算される支配的な固有ベクトルは，和が 1 になるよう規格化します．前回と同様，隣接行列の転置を取ってハブ中心性からオーソリティ中心性に変換するテクニックを使って，有向グラフにも無向グラフにも使用できる関数にしておきます．

def eigenvector_centrality(A, k=40, authority=False):
    """
    Computes the dominant eigenvector of A using the power method.

    Parameters
    ----------
    A : NumPy ndarray
        Adjacency matrix representation of graph.
    
    k : int (default: 40)
        How many times A is to be "powered".

    authority : bool (default: False)
        If authority = True, A is replaced by its transpose.

    Returns
    -------
    k : NumPy ndarray
        Eigenvector centrality of A.
    """
    A_temp = A.T if authority else A
    n = len(A_temp)
    r = spectral_radius(A_temp)
    e = r**(-k) * (np.linalg.matrix_power(A_temp, k) @ np.ones(n))
    return e / np.sum(e)

前回の記事で次数中心性の粗さを指摘するために例示したネットワークは，図4のように辺境の名士（1,2,3番）が真の名士（0番）を中心につながったネットワークでした．0,1,2,3番のノードの次数はすべて3ですから，本当は他3つのノードをまとめる0番を高く評価したいのに，次数中心性はそれらすべてを同等に扱ってしまうという問題があったのでした．


図4: 辺境の名士が真の名士を中心につながったネットワーク

再びこのネットワークを用いて，固有ベクトル中心性でこの問題を解決できるか確認します．


図5：次数中心性（左）と固有ベクトル中心性（右）

code
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches

次数中心性の計算には，前回定義した degree_centrality() 関数を使用しています．

def degree_centrality(A, authority=False):
    A_temp = A.T if authority else A
    N = len(A_temp)
    return A_temp@np.ones(N)

中心性を格納するデータフレームを作成する centrality_plot_data() 関数を定義します．

def centrality_plot_data(nodes, centrality_measures):
    df = pd.DataFrame({'node': nodes,
                       'centrality':centrality_measures,
                       'color': '#69b3a2'
                       })
    return df

次数中心性と固有ベクトル中心性を比較します．

## 辺境の名士
# エッジリスト
edge_lst = [(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (2, 6), (2, 7), (3, 8), (3, 9)]

g = gt.Graph(directed=False) # グラフを生成
g.add_edge_list(edge_lst)    # グラフにエッジを追加

# グラフを隣接行列に変換
A = gt.adjacency(g).toarray().T # graph-tool の隣接行列の定義は j --> i で a_{ij} = 1 

degree = degree_centrality(A) # 次数中心性
eigenvector = eigenvector_centrality(A, authority=False) # 固有ベクトル中心性

nodes = [i for i in range(len(A))] # ノードリスト

centrality_measures = [degree, eigenvector] # 中心性リスト

ylabels = ['degree',  'eigenvector'] # 中心性名リスト

ylims = [(0, 5), (0, 0.25)]

fig, axes = plt.subplots(1, 2, figsize=(12,5))
axes = axes.flatten()

for i, ax in enumerate(axes):
    df = centrality_plot_data(nodes, centrality_measures[i])

    ax.bar('node', 'centrality', data=df, color=df["color"])

    patch = mpatches.Patch(color=None, label=ylabels[i], visible=False)
    ax.legend(handles=[patch], fontsize=18, loc="upper left", handlelength=0, frameon=False)
    ax.set_xlabel("node", fontsize=18)

    ax.tick_params(labelsize=14)
    ax.set_xticks([i for i in range(10)])
    
    if ylims[i] is not None:
        ax.set_ylim(ylims[i])


fig.tight_layout()

図5が示すように，固有ベクトル中心性は次数中心性では捉えられなかった0番の重要性をしっかり評価しており，次数中心性の問題点を解決できていることがわかります．また，ネットワークが完全グラフに近い場合はどのノードも同じような次数になりランキング機能を果たせないという問題点も，図6が示す通り固有ベクトル中心性を使えば解決します．


図6：出／入次数中心性（上段）とハブ／オーソリティベース固有ベクトル中心性（下段）
出所）Stachurski et al. (2022)

固有ベクトル中心性の限界

実は固有ベクトル中心性にも致命的な欠点が存在します．固有ベクトル中心性は有向グラフが強連結であれば必ず定義できますが，多くの現実の有向ネットワークにおいて強連結性は満たされません．この強連結性の破れが望ましくない結果をもたらします．


図7：ハブ（左）とオーソリティ（右）
出所）Stachurski et al. (2022)

図7は中心性の2つの考え方を説明するために使用したものです．ハブ中心性で評価すると左のハブは高く評価され，オーソリティ中心性で評価すると右のオーソリティは高く評価されるということでした．ここで，少し見方を変えてみます．ハブはたくさんの出近傍を持っていますが，入近傍はないので，入次数が 0 のソースということになります．逆にオーソリティはたくさんの入近傍を持っていますが，出近傍はないので出次数が 0 のシンクです．

では，シンクをハブベース固有ベクトル中心性で，ソースをオーソリティベース固有ベクトル中心性で評価するとどうなるのでしょうか．シンクのハブベース固有ベクトル中心性は常に 0 ですから，オーソリティを正反対の指標であるハブ中心性で評価すると無価値と判断されます[4]．逆に，ソースのオーソリティベース固有ベクトル中心性は常に 0 ですから，ハブも正反対の指標であるオーソリティ中心性で評価すると無価値になります[5]．

相手の気持ちを考えずにアピールばかりしていても，誰からも見向きもされなければオーソリティとしては評価されず，いくら自分が人気だからといって，集まってくる人たちに全く手を差し伸べないとハブとしては評価されないということです．使用した評価軸が自分の性質の真逆なので，評価されないのは当然といえば当然です．しかし実は，固有ベクトル中心性において，ハブは相手からのエッジが1本もなければハブとしても評価されず，オーソリティは相手にエッジを1本も張らなければオーソリティとしても評価されないという事態が起こりえます．例として図8の強連結でない有向グラフを考えます．

import graph_tool.all as gt

edge_lst = [(0, 1), (0, 2), (0, 3), (1, 2)] # エッジリスト
g = gt.Graph(directed=True) # グラフを生成
g.add_edge_list(edge_lst)    # グラフにエッジを追加
gt.graph_draw(g, vertex_text=g.vertex_index, output_size=(300, 300)); # グラフを可視化


図8：強連結でない有向グラフ

図8でハブベース固有ベクトル中心性を考えます．明らかに0番のノードはハブなのでグラフ内で最高のハブ中心性を持っていそうです．まず，シンクである2番と3番のノードの中心性は 0 になります．ハブ中心性は外向きのつながりを評価するので，2番と3番のノードの中心性が 0 （e_2=e_3=0）であることは問題ないように思えます．一方1番のノードを見てみると，2番に対してエッジを張っており出次数は k_1^{\text{out}}=1 なので，正の中心性を持つかと思われます．ところが，定義 (6) 式に従うと a_{12}e_2 = 1\cdot 0 = 0 より中心性は e_1=0 になってしまいます．すると，グラフ上でハブであるはずの0番のノードの中心性も同様に，

\sum_{j=0}^3 a_{0j}e_j = 0\cdot e_0+1\cdot 0+1\cdot 0+1\cdot 0 = 0

で e_0=0 になってしまいます．結果，e_0=e_1=e_2=e_3=0 という直感に反するケースが生じます．

オーソリティベースの固有ベクトル中心性についても考えてみます．2番のノードはオーソリティなので，グラフ内で最高のオーソリティ中心性を持っていて欲しいところです．ソースである0番のノードの中心性は \varepsilon_0=0 です．すると，\varepsilon_1=a_{01}\varepsilon_0=0,~~\varepsilon_3=a_{03}\varepsilon_0=0 となり，それに伴い \varepsilon_2 = a_{02}\varepsilon_0+a_{12}\varepsilon_1 = 0 となり，こちらも \varepsilon_0=\varepsilon_1=\varepsilon_2=\varepsilon_3=0 という結果になります．

当然，図7の有向グラフに対して先ほど実装した eigenvector_centrality() 関数を使っても欠損値が返ってきます．

import pandas as pd

# グラフを隣接行列に変換
A = gt.adjacency(g).toarray().T # graph-tool の隣接行列の定義は j --> i で a_{ij} = 1

out_degree = degree_centrality(A) # 出次数
in_degree = degree_centrality(A, True) # 入次数

eigen_hub = eigenvector_centrality(A, authority=False) # ハブ固有ベクトル
eigen_authority = eigenvector_centrality(A, authority=True) # オーソリティ固有ベクトル

# データフレームにまとめる
df = pd.DataFrame({"out_degree": out_degree, 
                     "eigen_hub": eigen_hub, 
                     "in_degree": in_degree, 
                     "eigen_authority": eigen_authority})
df
index out_degree eigen_hub in_degree eigen_authority
0 3.0 NaN 0.0 NaN
1 1.0 NaN 1.0 NaN
2 0.0 NaN 2.0 NaN
3 0.0 NaN 1.0 NaN

以上から，固有ベクトル中心性ではハブベースであれオーソリティベースであれ，ソースやシンクが存在するような強連結でない有向グラフに対しては，エッジをたくさん持つのに中心性が 0 になるノードが生じる可能性があることがわかりました[6]．次数中心性を改良した固有ベクトル中心性でもなお，特定のネットワークに対してはノードのランク付けができないという問題に再び立ち返ってしまいました．

次回予告

本記事では，固有ベクトル中心性の定義と特徴を確認し，Python で無向グラフ（有向グラフ）の（ハブ／オーソリティベース）固有ベクトル中心性を計算する eigenvector_centrality() 関数を実装しました．実装した関数を使って，真の名士の周りに辺境の名士が集まった無向ネットワークの固有ベクトル中心性を計算した結果，固有ベクトル中心性は次数中心性の問題点を解決していることが確認できました．しかし，強連結でない有向グラフに対しては，他とつながっているのに中心性が 0 になるノードが生じるという致命的な欠点も存在することがわかりました．

次回第6回は，固有ベクトル中心性の欠陥をある簡単なアイデアで解決する Katz 中心性を見ていきます．

参考文献

  • Bonacich, P. (1987). Power and centrality: A family of measures. American journal of sociology, 92(5), 1170-1182.
  • John Stachurski and Thomas J. Sargent. Economic Networks: Theory and Computation (QuantEcon, 2022). URL https://networks.quantecon.org/ .
脚注

  1. 隣接行列が既約であれば，ペロン＝フロベニウスの定理より \rho(A)>0 なので定義可能です． ↩︎

  2. どうしてこのように書けるかは，上の概念図で仮に新たなノード 4 が孤立した状態で参入したとき，エッジ (i,4) が存在せず a_{i4} = 0 となることからわかると思います． ↩︎

  3. 証明は有向グラフのハブベース固有ベクトル中心性で行なっています． ↩︎

  4. 出次数が 0 のノード（シンク）のハブベース固有ベクトル中心性が常に 0 であることは容易に示せます．任意のノード i の出次数が 0 であるとき，k_i^{\text{out}}=\sum_j a_{ij}=0 が成り立ちます．a_{ij}\geqslant0 より a_{ij}=0~~\forall j．よって，e_j = \rho(A)^{-1}\sum_ja_{ij}e_j=0． ↩︎

  5. 任意のノード j の入次数が 0 であるとき，|N_G^{\text{in}}(j)|=0 より(8) 式の右辺が 0 となるため，\varepsilon_j = 0.シンクについてもこの方法で示せば早かったですね... ↩︎

  6. 逆に，グラフが強連結であれば固有ベクトル中心性が必ず定義できるのは，どのノードも出ていくエッジと入ってくるエッジを少なくとも1本ずつ持っているからだということがわかります． ↩︎

GitHubで編集を提案

Discussion