カッツ中心性

グラフ理論において、ノードのカッツ中心性またはアルファ中心性は、ネットワークの中心性を測る尺度である。これは1953年にレオ・カッツによって導入され、ソーシャルネットワーク内のアクター（またはノード）の相対的な影響力を測定するのに用いられる。^{[1]アクターのペア間の最短経路（}測地線）のみを考慮する一般的な中心性尺度とは異なり、カッツ中心性は、アクターのペア間の歩行の総数を考慮して影響力を測定する。 ^[2]

これはGoogleのPageRankや固有ベクトル中心性に似ています。^[3]

カッツ中心性は、ネットワーク内のノードの相対的な影響力を、直接の隣接ノード（第1次ノード）の数と、これらの直接の隣接ノードを介して検討中のノードに接続するネットワーク内の他のすべてのノードの数を測定することによって計算します。ただし、遠い隣接ノードとの接続には、減衰係数 によってペナルティが課せられます。^[4]ノードのペア間の各パスまたは接続には、 によって決定される重みが割り当てられ、ノード間の距離は として表されます。 ${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha ^{d}}$

たとえば、右の図では、ジョンの中心性が測定されており、 であると仮定します。ジョンと彼のすぐ隣にいるジェーンとボブを接続する各リンクに割り当てられる重みは になります。ホセはボブを介して間接的にジョンに接続しているため、この接続 (2 つのリンクで構成) に割り当てられる重みは になります。同様に、アジズとジェーンを介してアグネタとジョンの間の接続に割り当てられる重みは になり、ディエゴ、ホセ、ボブを介してアグネタとジョンの間の接続に割り当てられる重みは になります。 ${\displaystyle \alpha =0.5}$${\displaystyle (0.5)^{1}=0.5}$${\displaystyle (0.5)^{2}=0.25}$${\displaystyle (0.5)^{3}=0.125}$${\displaystyle (0.5)^{4}=0.0625}$

A を、検討中のネットワークの隣接行列とします。Aの要素は、ノードiがノードjに接続されている場合は値 1 を、そうでない場合は値 0 を取る変数です。A の累乗は、2 つのノード間に中継点を介したリンクが存在するかどうか (または存在しないかどうか) を示します。たとえば、行列 で要素 の場合、ノード 2 とノード 12 が長さ 3 のウォークを介して接続されていることを示します。 がノード iの Katz 中心性を表す場合、値 が与えられたとき、数学的には次のようになります。 ${\displaystyle (a_{ij})}$${\displaystyle A^{3}}$${\displaystyle (a_{2,12})=1}$${\displaystyle C_{\mathrm {Katz} }(i)}$${\displaystyle \alpha \in (0,1)}$

${\displaystyle C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}}$

上記の定義では、の位置にある要素がノードと の間の次数接続の総数を反映するという事実を利用していることに注意してください。減衰係数の値は、Aの最大固有値の絶対値の逆数よりも小さくなるように選択する必要があります。^[5]この場合、次の式を使用してカッツ中心性を計算することができます。 ${\displaystyle (i,j)}$${\displaystyle A^{k}}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle \alpha }$

${\displaystyle {\overrightarrow {C}}_{\mathrm {Katz} }=((I-\alpha A^{T})^{-1}-I){\overrightarrow {I}}}$

ここでは単位行列、は 1 からなるサイズn ( nはノードの数)のベクトルです。 はA の転置行列を表し、 は項の逆行列を表します。^[5]${\displaystyle I}$${\displaystyle {\overrightarrow {I}}}$${\displaystyle A^{T}}$${\displaystyle (I-\alpha A^{T})^{-1}}$${\displaystyle (I-\alpha A^{T})}$

このフレームワークを拡張すると、動的な設定でウォークを計算できるようになります。^{[6] [7]}一時的なエッジのネットワーク隣接スナップショットの時間依存シリーズを取得することで、ウォークが累積効果に貢献するための依存性が提示されます。時間の矢印は保存されるため、アクティビティの貢献は情報伝播の方向に非対称になります。

次の形式のデータを生成するネットワーク:

${\displaystyle \left\{A^{[k]}\in \mathbb {R} ^{N\times N}\right\}\qquad {\text{for}}\quad k=0,1,2,\ldots ,M,}$

各時刻における隣接行列を表します。したがって、 ${\displaystyle t_{k}}$

${\displaystyle \left(A^{[k]}\right)_{ij}={\begin{cases}1&{\text{there is an edge from node }}i{\text{ to node }}j{\text{ at time }}t_{k}\\0&{\text{otherwise}}\end{cases}}}$

時点は順序付けられていますが、必ずしも等間隔である必要はありません。は、ノードからノードまでの長さの動的ウォークの数の加重カウントです。参加ノード間の動的通信可能性の形式は次のとおりです。 ${\displaystyle t_{0}<t_{1}<\cdots <t_{M}}$${\displaystyle Q\in \mathbb {R} ^{N\times N}}$${\displaystyle (Q)_{ij}}$${\displaystyle w}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle {\mathcal {Q}}=\left(I-\alpha A^{[0]}\right)^{-1}\cdots \left(I-\alpha A^{[M]}\right)^{-1}.}$

これは次のように正規化できます。

${\displaystyle {\hat {\mathcal {Q}}}^{[k]}={\frac {{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}}{\left\|{\hat {\mathcal {Q}}}^{[k-1]}\left(I-\alpha A^{[k]}\right)^{-1}\right\|}}.}$

したがって、中心性は、ノードがネットワーク全体で動的メッセージを どれだけ効率的に「ブロードキャスト」および「受信」できるかを定量化します。${\displaystyle n}$

${\displaystyle C_{n}^{\mathrm {broadcast} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{nk}\quad \mathrm {and} \quad C_{n}^{\mathrm {receive} }:=\sum _{k=1}^{N}{\mathcal {Q}}_{kn}}$。

隣接行列 を持つグラフが与えられた場合、カッツ中心性は次のように定義されます。 ${\displaystyle A_{i,j}}$

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}-{\vec {e}}\,}$

ここで、 はノード に与えられた外部重要度であり、 は非負の減衰係数であり、のスペクトル半径の逆数よりも小さくなければなりません。Katz ^[8]による元の定義では、 定数ベクトル が使用されていました。Hubbell ^[9]は、 一般的な の使用法を導入しました。 ${\displaystyle e_{j}}$${\displaystyle j}$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle {\vec {e}}}$${\displaystyle {\vec {e}}}$

半世紀後、ボナシッチとロイド^[10]はアルファ中心性を次のように定義しました。

${\displaystyle {\vec {x}}=(I-\alpha A^{T})^{-1}{\vec {e}}\,}$

これは本質的にカッツ中心性と同一です。より正確には、ノードのスコアはだけ異なるため、 が定数であれば、ノードに誘導される順序は同一です。 ${\displaystyle j}$${\displaystyle e_{j}}$${\displaystyle {\vec {e}}}$

カッツ中心性は、引用ネットワークやワールドワイドウェブなどの有向ネットワークにおける中心性を計算するために使用できます。^[11]

カッツ中心性は、固有ベクトル中心性のような従来使用されてきた尺度が役に立たなくなる有向非巡回グラフの解析に適しています。 ^[11]

カッツ中心性は、ソーシャルネットワーク内のアクターの相対的な地位や影響力を推定するのにも使用できます。^[12]で紹介されている研究では、Twitterのデータにカッツ中心性の動的バージョンを適用したケーススタディを示しており、安定したディスカッションリーダーを持つ特定のブランドに焦点を当てています。このアプリケーションにより、この方法論をその分野の人間の専門家の方法論と比較し、その結果がソーシャルメディアの専門家のパネルとどの程度一致するかを確認できます。

神経科学では、カッツ中心性は神経ネットワーク内のニューロンの相対的な発火率と相関していることがわかっています。 ^{[13]カッツ中心性の時間的拡張は、 [14]}の音楽学習実験から得られたfMRIデータに適用され、学習プロセスの前後に被験者からデータが収集されます。結果は、音楽への露出によるネットワーク構造の変化が、各セッションで学習の成功に沿ってクラスターを生成する相互伝達性の定量化を生み出したことを示しています。

カッツ中心性の一般化された形は、大学フットボールなどのスポーツチームの直感的なランキングシステムとして使用することができます。^[15]

アルファ中心性は、ネットワーク分析と可視化のためのigraphライブラリに実装されています。^[16]