中心性

テンプレート:ネットワーク科学 中心性（ちゅうしんせい、テンプレート:Lang-en-short）とは、グラフ理論およびネットワーク分析において、グラフ内のノード（頂点）にそのネットワーク上の位置に対応する数値や順位を割り当てる指標である。応用例としては、社会的ネットワークにおける最も影響力のある人物の特定、インターネットやテンプレート:仮リンクにおける重要なインフラ節点の特定、疾病のスーパー・スプレッダーの特定、脳ネットワークの解析などが挙げられる。中心性の概念は当初社会ネットワーク分析において発展したため、中心性を測るために用いられる用語の多くにはその社会学的な起源が反映されている。時とともにこの概念は大幅に拡張され、何百もの異なる中心性尺度が発展してきた。その最も包括的な一覧は CentralityZoo オンラインカタログに文書化されている。

中心性指数の定義と特徴づけ

中心性指数とは、「重要な頂点を特徴づけるものは何か」という問いに対する答えである。その答えは、グラフの頂点集合上で定義された実数値関数という形で与えられ、その関数が生み出す値は、最も重要なノードを識別する順位付けを提供すると期待される。

「重要性」という語は非常に多くの意味を持つため、中心性には多くの異なる定義が生まれた。分類方式として2つの案が提案されている。1つ目は「重要性」を、ネットワーク上を横断するフロー（流れ）や転送の型との関連で捉える考え方であり、これにより中心性を、それが重要とみなすフローの型によって分類できる。もう1つは「重要性」を、ネットワークの結束性への関与として捉える考え方であり、これにより中心性を、結束性をどう測定するかに基づいて分類できる。これらのアプローチはいずれも中心性を異なるカテゴリに分ける。さらなる帰結として、あるカテゴリに適した中心性は、別のカテゴリに適用するとしばしば「間違った答え」を出すということが挙げられる。

多くの（ただしすべてではない）中心性尺度は、実質的に、ある頂点を通過する一定の型の経路（ウォークとも呼ばれる）の数を数えているものであり、尺度間の違いは、対象となるウォークがどのように定義され数えられるかにある。考察をこの一群の尺度に限定すれば、長さ1のウォークに関心を持つもの（次数中心性）から無限長のウォークに関心を持つもの（固有ベクトル中心性）まで、多くの中心性をスペクトル上に配置する分類が可能になる 一方、媒介中心性のようなその他の中心性尺度は、全体的な連結性そのものだけでなく、ネットワークの連結性にとって枢要な位置を占有していることに着目する。

ネットワークフローによる特徴づけ

ネットワークは、何かが流れる経路の記述であるとみなすことができる。これにより、中心性が符号化するフローの型と経路の型に基づいた特徴づけが可能になる。フローは転送（transfers）にも基づきうる。転送では、分割不可能な項目が1つのノードから別のノードへと移動する。たとえば、配達拠点から顧客の家へ届けられる小包配送がこれに当たる。2つ目のケースは逐次複製（serial duplication）であり、項目が複製されることでソースとターゲットの双方がその項目を持つ。一例は、うわさ話を通じた情報伝播であり、情報は私的な形で伝播し、プロセスの終了時点でソースとターゲットの両ノードが情報を知っている状態になる。最後のケースは並列複製（parallel duplication）であり、項目が同時に複数のリンクへ複製される。ラジオ放送が同じ情報を多数の聴取者へ同時に届けるのがこれである。

同様に、経路の型も制約できる。測地線（最短経路）、道（どの頂点も一度しか訪れない）、トレイル（頂点は複数回訪れてよいが、辺は一度しか通らない）、ウォーク（頂点も辺も複数回通ってよい）といった具合である。

ウォーク構造による特徴づけ

中心性の構成方法から導かれる別の分類もある。これも再び2つのクラスに分かれる。中心性は radial（放射型）と medial（中間型）のいずれかである。放射型中心性は、注目頂点から開始し終了するウォークを数える。次数中心性と固有値中心性は放射型中心性の例であり、それぞれ長さ1および長さ無限大のウォークの数を数える。中間型中心性は、注目頂点を通過するウォークを数える。その典型例が Freeman の媒介中心性であり、注目頂点を通過する最短経路の数を数えるものである。

同様に、数え上げではウォークの体積（volume）を取るか長さ（length）を取るかを区別できる。体積とは、指定された型のウォークの総数である。前段落の3つの例はこのカテゴリに入る。長さとは、注目頂点からグラフ内の残りの頂点までの距離を捉えるものである。近接中心性（注目頂点から他のすべての頂点への測地線距離の総和）はその最もよく知られた例である なお、この分類は数え上げるウォークの型（ウォーク、トレイル、道、測地線）とは独立である。

Borgatti と Everett は、この類型論が中心性尺度を比較する最良の方法について洞察を与えると提唱している。この 2×2 分類で同じ枠に置かれた中心性同士は、代替案として比較検討するのに十分な程度に類似しており、特定の用途にどちらが優れているかを合理的に比較できる。しかし、異なる枠に属する尺度はカテゴリ的に異質であり、相対的な適合性の評価は、どちらのカテゴリがより適切かをあらかじめ決定するという文脈の中でのみ行うことができ、それなしの比較は無意味となる。

放射型・体積型の中心性がスペクトル上に存在すること

ウォーク構造による特徴づけが示すのは、広く使われているほぼすべての中心性が放射型・体積型の尺度だということである。これは、ある頂点の中心性がその頂点と関連する頂点群の中心性の関数であるという信念を符号化したものである。中心性の違いは、「関連性」をどう定義するかにある。

Bonacich は、関連性をウォークの観点で定義すれば、考慮するウォークの長さに基づいて中心性の族を定義できることを示した 次数中心性は長さ1のウォークを数え、固有値中心性は長さ無限大のウォークを数える。関連性の別の定義もまた妥当である。テンプレート:仮リンクは頂点が外部からの影響源を持てるようにする。Estrada の部分グラフ中心性は閉じた経路（三角形、四角形など）のみを数えることを提案している。

こうした尺度の核心にあるのは、グラフの隣接行列の冪がその冪の指数で与えられる長さのウォークの数を表すという観察である。同様に、行列指数関数も与えられた長さのウォークの数と密接に関係している。隣接行列の初期変換を施せば、数え上げるウォークの型について異なる定義が可能になる。どちらのアプローチでも、頂点の中心性は無限級数として表現できる。すなわち行列冪の場合

$\sum _{k=0}^{\mathrm{\infty }}{A}_R^k{\beta }^k$

または行列指数の場合

$\sum _{k=0}^{\mathrm{\infty }}\frac{(A_R\beta {)}^k}{k!}$

ここで

• $k$ はウォークの長さ、
• $A_R$ は変換後の隣接行列、
• $\beta$ は級数の収束を保証する割引パラメータである。

Bonacich の族の尺度は隣接行列を変換しない。テンプレート:仮リンクは隣接行列をその予解式で置き換える。部分グラフ中心性は隣接行列をそのトレースで置き換える。驚くべき帰結は、隣接行列の初期変換にかかわらず、こうしたアプローチすべてが共通の極限挙動を持つということである。$\beta$ がゼロに近づくと各指数は次数中心性へ収束し、$\beta$ が最大値に近づくと固有値中心性へ収束する。

ゲーム理論的中心性

上述の標準的な尺度のほとんどに共通する特徴は、ノードそれ自体が果たす役割のみに着目してその重要性を評価する点である。しかし多くの応用では、ノードの機能を集団として考慮したときに生じうる相乗効果があるため、このようなアプローチは不十分である。

たとえば、感染症の流行を食い止める問題を考えてみよう。上のネットワーク図を見て、どのノードにワクチンを接種すべきだろうか。前に述べた尺度に基づけば、病気の蔓延において最も重要なノードを認識したい。ノード個々の特徴のみに焦点を当てる中心性だけに基づくアプローチは、良い判断にならないかもしれない。赤い正方形内のノードは個別には病気の蔓延を止められないが、集団として見ると、病気がノード $v_1$、$v_4$、$v_5$ で始まった場合に流行を止められることは明らかである。ゲーム理論的中心性は、ゲーム理論の道具立てを用いて、こうした問題や機会に対処しようとするものであり、そこで提案されたアプローチはシャープレイ値を用いる。シャープレイ値計算の時間計算量の困難さのため、この分野の取り組みの多くは、ネットワークの特異なトポロジーや問題の特殊な性質に依存する新しいアルゴリズムや手法の実装に向かっている。そのようなアプローチにより、時間計算量を指数関数的から多項式的に削減できる可能性がある。

同様に、解概念であるテンプレート:仮リンクは、プレイヤー間の双方向的な直接影響を測定するために、シャープレイ値ではなくシャープレイ＝シュービック投票力指数を適用する。この分布は実際のところ一種の固有ベクトル中心性である。Hu (2020) では米国の大学ランキングのようにビッグデータのオブジェクトをソートするために用いられている。

重要な限界

中心性指数には2つの重要な限界があり、1つは明白で、もう1つは微妙である。明白な限界は、ある用途に最適な中心性が別の用途にはしばしば最適ではないことである。もし違うならば、これほど多くの異なる中心性は必要なかったはずである。この現象を例示するのがテンプレート:仮リンクであり、3つの異なる中心性の概念が3つの異なる最中心頂点を選ぶ。

より微妙な限界は、頂点の中心性が頂点の相対的重要性を示すという、しばしば信じられている誤謬である。中心性指数は、最も重要な頂点を示す順位付けを生成するよう明示的に設計されており、先述の限界の範囲内であればそれはうまく機能する。しかしノード全般の影響力を測定するようには設計されていない。近年、ネットワーク物理学者たちはこの問題に対処するため、テンプレート:仮リンクの開発を始めている。

この誤りは二重である。第一に、順位付けは頂点を重要性で順序付けるだけであり、順位の異なる水準間の重要性の差を定量化しない。これは、問題の中心性尺度にフリーマンの集中度を適用することで緩和できる。集中度スコアの差に応じてノードの重要性についてある程度の洞察が得られるからである。さらに、フリーマンの集中度を用いれば、最高集中度スコアを互いに比較することで複数のネットワークを比較することも可能になる。

第二に、所与のネットワーク／用途において最も重要な頂点を（正しく）識別する特徴は、必ずしも残りの頂点に一般化されない。他の大多数のネットワークノードについては、順位は無意味かもしれない これが説明するのは、たとえば Google の画像検索で妥当な順序で表示されるのが最初の数件だけであるような現象である。PageRank は非常に不安定な尺度であり、ジャンプパラメータの小さな調整の後に頻繁に順位逆転が生じる。

中心性指数がネットワークの残りの部分に一般化できないという失敗は、一見直観に反するように思われるかもしれないが、上述の定義から直接導かれる。複雑ネットワークは異質なトポロジーを持つ。最適な尺度が最重要頂点たちのネットワーク構造に依存する限り、そうした頂点に最適な尺度はネットワークの残りの部分には最適ではない。

中心性尺度のもう1つの限界は、通常、ネットワーク内の個々の頂点に数値や順位を割り当てるよう設計されており、頂点の集合には割り当てられないことである。しかし一部の応用では、たとえば組織のネットワークにおいて特定の人々の集団がどれほど中心的あるいは周縁的であるかに関心があるかもしれない。これが、中心性を頂点の集団へ一般化するテンプレート:仮リンクにつながった。

次数中心性

同一のランダム幾何グラフにおける A) 媒介中心性、B) 近接中心性、C) 固有ベクトル中心性、D) 次数中心性、E) 調和中心性、F) テンプレート:仮リンク の例。

歴史的に最も古く、概念的に最も単純なのが次数中心性であり、ノードに入射するリンクの数（すなわちノードが持つ結びつきの数）として定義される。次数は、ネットワーク内を流れるもの（ウイルスや情報など）にノードが感染する即時のリスクという観点で解釈できる。有向ネットワーク（結びつきに向きがある場合）では、通常2つの別個の次数中心性、すなわち入次数（indegree）と出次数（outdegree）を定義する。それに応じて、入次数はそのノードに向けられた結びつきの数、出次数はそのノードが他者に向ける結びつきの数である。結びつきが友情や協働のような肯定的な側面と結び付く場合、入次数は人気度の一種として、出次数は社交性として解釈されることが多い。

頂点 $v$ の次数中心性は、$|V|$ 個の頂点と $|E|$ 本の辺を持つグラフ $G:=(V,E)$ に対して次のように定義される。

$C_D(v)=\mathrm{deg}(v)$

グラフの全ノードの次数中心性の計算は、グラフの密な行列表現では$\mathrm{\Theta }(V^2)$、疎行列表現では辺数について $\mathrm{\Theta }(E)$ かかる。

ノードレベルの中心性の定義はグラフ全体に拡張でき、この場合はグラフの集中度（graph centralization）について語っていることになる $v\ast$ を $G$ で最高の次数中心性を持つノードとする。$X:=(Y,Z)$ を以下の量を最大化する $|Y|$-ノード連結グラフとする（$y\ast$ は $X$ で最高の次数中心性を持つノード）。

$H=\sum _{j=1}^{|Y|}[C_D(y\ast )-C_D(y_j)]$

対応して、グラフ $G$ の次数集中度は以下のようになる。

$C_D(G)=\frac{\sum _{i=1}^{|V|}[C_D(v\ast )-C_D(v_i)]}{H}$

$H$ の値は、グラフ $X$ が他のすべてのノードが接続された1つの中心ノードを含む（スターグラフである）ときに最大化され、この場合

$H=(n-1)\cdot ((n-1)-1)=n^2-3n+2.$

ゆえに、任意のグラフ $G:=(V,E)$ に対して、

$C_D(G)=\frac{\sum _{i=1}^{|V|}[C_D(v\ast )-C_D(v_i)]}{|V{|}^2-3|V|+2}$

また、ハブ形成傾向（Tendency to Make Hub, TMH）と名付けられた新しい大域的な次数中心性の拡張尺度は次のように定義される:

$\text{TMH}=\frac{\sum _{i=1}^{|V|}\mathrm{deg}(v{)}^2}{\sum _{i=1}^{|V|}\mathrm{deg}(v)}$

TMH はネットワークにおける次数中心性の出現とともに増加する。

近接中心性

連結なグラフにおいて、正規化された近接中心性（closeness centrality、あるいは近接性）とは、ノードとグラフ内の他のすべてのノードとの最短経路の平均長である。したがって、より中心的なノードほど、他のすべてのノードに近い。

近接性は逆数の概念を用いて、テンプレート:仮リンク (1950) により farness（遠さ）の逆数として定義された すなわち $C_B(v)=({\sum }_{u}d(u,v){)}^{-1}$。ここで $d(u,v)$ は頂点 u と v の間の距離である。ただし、近接中心性と言う場合、通常はその正規化形式を指し、前述の式に $N$（グラフ内のノード数）を乗じて得られる。

$C(v)=\frac{N-1}{\sum _{u}d(u,v)}.$

この正規化により、異なるサイズのグラフ間でノードを比較できるようになる。多くのグラフでは、近接性の逆数と次数の対数との間に強い相関がある すなわち $(C(v){)}^{-1}\approx -\alpha \ln (k_v)+\beta$。ここで $k_v$ は頂点 v の次数であり、α と β は各ネットワークごとの定数である。

他のすべてのノードからの距離を取るかへの距離を取るかは、無向グラフでは問題にならないが、有向グラフではまったく異なる結果をもたらしうる（たとえばウェブサイトは、外向きリンクからは高い近接中心性を持つが、内向きリンクからは低い近接中心性しか持たないことがありうる）。

調和中心性

（必ずしも連結でない）グラフにおいて、調和中心性（harmonic centrality）は近接中心性の定義における総和と逆数の操作を入れ替えたものである。

$H(v)=\sum _{u|u\ne v}\frac{1}{d(u,v)}$

ここで、u から v への経路が存在しない場合 $1/d(u,v)=0$ とする。調和中心性は $N-1$（グラフ内のノード数）で割ることで正規化できる。

調和中心性は テンプレート:仮リンク とテンプレート:仮リンク (2000) によって提案され、その後 Dekker (2005) によって「valued centrality」という名前で、さらに Rochat (2009) によって独立に提案された。

媒介中心性

色相（赤 = 0 から青 = 最大まで）はノードの媒介性を示す。

媒介中心性（betweenness centrality）は、グラフ内の頂点の中心性尺度である（辺の媒介中心性もあるが、ここでは扱わない）。媒介中心性は、あるノードが他の2つのノード間の最短経路上で橋渡し役を務める回数を定量化する。テンプレート:仮リンク により、社会的ネットワークにおける人間同士のコミュニケーションに対する人間の支配力を定量化する尺度として導入された 彼の構想では、ランダムに選んだ2つの頂点間のランダムに選んだ最短経路上に出現する確率が高い頂点が高い媒介性を持つ。

頂点 $V$ 個を持つグラフ $G:=(V,E)$ 内の頂点 $v$ の媒介性は次のように計算される。

1. 各頂点対 (s,t) について、その間の最短経路を求める。
2. 各頂点対 (s,t) について、注目頂点（ここでは頂点 v）を通過する最短経路の割合を求める。
3. この割合をすべての頂点対 (s,t) について合計する。

より簡潔には、媒介性は次のように表せる:

$C_B(v)=\sum _{s\ne v\ne t\in V}\frac{{\sigma }_{st}(v)}{{\sigma }_{st}}$

ここで ${\sigma }_{st}$ はノード $s$ からノード $t$ への最短経路の総数、${\sigma }_{st}(v)$ はそのうち $v$ を通過する経路の数である。媒介性は、v を含まない頂点対の数で割ることで正規化できる。この数は有向グラフでは $(n-1)(n-2)$、無向グラフでは $(n-1)(n-2)/2$ である。たとえば無向スターグラフでは、中心頂点（可能なすべての最短経路に含まれる）の媒介性は $(n-1)(n-2)/2$（正規化すれば1）となり、葉（最短経路に一切含まれない）の媒介性は0となる。

計算の観点からは、グラフ内の全頂点の媒介中心性と近接中心性はいずれも、グラフ上の全頂点対間の最短経路の計算を伴い、ワーシャル–フロイド法では$O(V^3)$ の時間を要する。しかし疎グラフではジョンソン法の方が効率的な場合があり、$O(|V||E|+|V{|}^2\log |V|)$ の時間で計算できる。重みなしグラフの場合はテンプレート:仮リンクで計算でき、$O(|V||E|)$ の時間で済む。通常、これらのアルゴリズムは、ループや多重辺を許容する無向連結グラフを想定している。ネットワークグラフを扱う場合、（辺が2人の人間や頂点間の接続を表す）単純な関係を維持するために、ループや多重辺のないグラフがしばしば前提となる。この場合、各最短経路が2回数え上げられる分を補正するため、ブランデスのアルゴリズムを用いる際には最終的な中心性スコアを2で割る必要がある。

固有ベクトル中心性

固有ベクトル中心性（eigenvector centrality、固有中心性とも）は、ネットワーク内のノードの影響力を測る尺度である。高スコアのノードとの接続は低スコアのノードとの等しい接続よりも当該ノードのスコアに大きく寄与するという考えに基づき、ネットワーク内のすべてのノードに相対スコアを割り当てる GoogleのPageRankやテンプレート:仮リンクは固有ベクトル中心性の変種である。

隣接行列を用いた固有ベクトル中心性の計算

頂点数 $|V|$ のグラフ $G:=(V,E)$ に対し、$A=(a_{v,t})$ を隣接行列、すなわち頂点 $v$ が頂点 $t$ にリンクしていれば $a_{v,t}=1$、そうでなければ $a_{v,t}=0$ であるような行列とする。頂点 $v$ の相対中心性スコア $x_v$ は、頂点集合 $v\in V$ 上の次の方程式系の非負解として定義できる。

$x_v=\frac{1}{\lambda }\sum _{t\in M(v)}{x}_t=\frac{1}{\lambda }\sum _{t\in G}{a}_{v,t}{x}_t$

ここで $M(v)$ は $v$ の近傍集合、$\lambda$ は定数である。少し整理し直すと、これは固有ベクトル方程式

$𝐀𝐱=\lambda 𝐱$.

として書ける。

一般に、非ゼロの固有ベクトル解が存在する固有値 $\lambda$ は多数ありうる。隣接行列の成分は非負なので、ペロン＝フロベニウスの定理により、実で正の唯一の最大固有値が存在する。この最大固有値が所望の中心性尺度をもたらす 関連する固有ベクトルの $v^{th}$ 成分が、ネットワークにおける頂点 $v$ の相対中心性スコアを与える。固有ベクトルは共通因子を除いてのみ定義されるので、 well-defined なのは頂点間の中心性の比のみである。絶対スコアを定義するには固有ベクトルを正規化しなければならない。たとえば全頂点にわたる総和が1、または頂点の総数 n となるようにする。べき乗法は、この支配的な固有ベクトルを見つけるために使用できる多くの固有値アルゴリズムの1つである さらに、A の成分を接続強度を表す実数に一般化することもできる。確率行列がその例である。

Katz 中心性

Katz 中心性は次数中心性の一般化である。次数中心性は直接の近傍の数を測るが、Katz 中心性は経路を介して接続しうるすべてのノードの数を測り、遠方のノードの寄与には減衰を課す。数学的には次のように定義される。

$x_i=\sum _{k=1}^{\mathrm{\infty }}\sum _{j=1}^N{\alpha }^k(A^k{)}_{ji}$

ここで $\alpha$ は $(0,1)$ の減衰係数である。

Katz 中心性は固有ベクトル中心性の変種とみなせる。Katz 中心性のもう一つの形式は

$x_i=\alpha \sum _{j=1}^N{a}_{ij}(x_j+1).$

固有ベクトル中心性の式と比較して、$x_j$ が $x_j+1$ に置き換えられている。

$\alpha$ が下から $\frac{1}{\lambda }$ に近づくときの Katz 中心性の極限が主固有ベクトル（隣接行列 $A$ の最大固有値に対応する固有ベクトル）であることが示されている。

PageRank 中心性

PageRank は次の方程式を満たす。

$x_i=\alpha \sum _j{a}_{ji}\frac{x_j}{L(j)}+\frac{1-\alpha }{N},$

ここで

$L(j)=\sum _i{a}_{ji}$

はノード $j$ の近傍の数（有向グラフでは外向きリンクの数）である。固有ベクトル中心性や Katz 中心性と比較して大きな違いはスケーリング因子 $L(j)$ である。PageRank と固有ベクトル中心性のもう1つの違いは、PageRank ベクトルが左固有ベクトルである点である（因子 $a_{ji}$ の添字が入れ替わっていることに注意）。

パーコレーション中心性

複雑ネットワークにおける単一ノードの「重要性」を判定するための多数の中心性尺度が存在する。しかし、これらの尺度はノードの重要性を純粋にトポロジカルな観点で定量化しており、ノードの値はいかなる意味でもノードの「状態」に依存しない。それはネットワークダイナミクスにかかわらず一定に保たれる。これは重み付き媒介性尺度についても同様である。しかし、ノードは媒介中心性などの尺度の観点では中央に位置していても、パーコレーション（浸透）が起きているネットワークの文脈では「中央」に位置しないことが十分ありうる。「コンテージョン」（感染）のパーコレーションは、複雑ネットワーク上でさまざまなシナリオで発生する。たとえば、ウイルスや細菌の感染は人々の社会的ネットワーク（接触ネットワークと呼ばれる）上を広がりうる。疾病の蔓延は、道路・鉄道・航空路線で接続された町や人口密集地のネットワークを想定することで、より高い抽象度でも考えられる。コンピュータウイルスはコンピュータネットワーク上を広がりうる。商談や取引に関するうわさやニュースも人々の社会的ネットワークを通じて広がりうる。これらのシナリオすべてにおいて、「コンテージョン」は複雑ネットワークのリンク上を広がりながら、ノードの「状態」を回復可能か否かにかかわらず変化させていく。たとえば疫学のシナリオでは、感染が広がるにつれて個人は「感受性あり」から「感染」状態へ移行する。上の例で個々のノードが取りうる状態は、二値（ニュースを受け取った／受け取っていない）、離散（感受性あり／感染／回復）、あるいは連続（町の感染人口の割合など）でありうる。これらすべてのシナリオに共通するのは、コンテージョンの蔓延がネットワーク内のノード状態の変化をもたらすことである。パーコレーション中心性（PC）はこの着想をもとに提案されたもので、ネットワークを通じたパーコレーションを助けるという観点からノードの重要性を特に測定する。この尺度は Piraveenan らによって提案された。

パーコレーション中心性は、所与のノードについて、所与の時刻に、そのノードを通過する「パーコレートした経路」の割合として定義される。「パーコレートした経路」とは、ノード対の間の最短経路であって、ソースノードがパーコレートしている（たとえば感染している）ものである。ターゲットノードはパーコレートしていてもいなくても、部分的にパーコレートした状態でもよい。

$P{C}^t(v)=\frac{1}{N-2}\sum _{s\ne v\ne r}\frac{{\sigma }_{sr}(v)}{{\sigma }_{sr}}\frac{{x^t}_s}{\sum [{x^t}_i]-{x^t}_v}$

ここで ${\sigma }_{sr}$ はノード $s$ からノード $r$ への最短経路の総数、${\sigma }_{sr}(v)$ はそのうち $v$ を通過する経路の数である。時刻 $t$ におけるノード $i$ のパーコレーション状態は ${x^t}_i$ と表記され、2つの特殊ケースとして、${x^t}_i=0$ は時刻 $t$ で非パーコレート状態を、${x^t}_i=1$ は時刻 $t$ で完全パーコレート状態を示す。中間の値は部分的なパーコレート状態を表す（たとえば町のネットワークでは、その町の感染者の割合に相当する）。

パーコレーション経路に付与される重みは、ソースノードに割り当てられたパーコレーションレベルに依存する。ソースノードのパーコレーションレベルが高いほど、そのノードから始まる経路がより重要になるという前提に基づく。したがって、高度にパーコレートしたノードから始まる最短経路上にあるノードは、パーコレーションにとって潜在的に重要である。PC の定義はターゲットノードの重みも含むように拡張できる。パーコレーション中心性の計算は、ブランデスの高速アルゴリズムを採用した効率的な実装により$O(NM)$ の時間で実行でき、ターゲットノードの重みを考慮する必要がある場合、最悪計算時間は$O(N^3)$ である。

クロス・クリーク中心性

複雑グラフ内の単一ノードのクロス・クリーク中心性（cross-clique centrality）は、異なるクリークへのノードの連結性を決定する。高いクロス・クリーク連結性を持つノードは、グラフ内での情報や病気の伝播を促進する。クリークとは、クリーク内のすべてのノードが互いに接続している部分グラフである。 $|V|$ 個の頂点と $|E|$ 本の辺を持つグラフ $G:=(V,E)$ に対するノード $v$ のクロス・クリーク連結性は $X(v)$ として定義される。ここで $X(v)$ は頂点 $v$ が属するクリークの数である。 この尺度は Faghani (2013) によって用いられたが、初出は Everett と Borgatti (1998) であり、彼らはこれをクリーク重複中心性（clique-overlap centrality）と呼んだ。

フリーマンの集中度

任意のネットワークの集中度（centralization）とは、そのネットワークの最も中心的なノードがどれほど中心的であるかを、他のすべてのノードの中心性との関係で測る尺度である 集中度尺度は(a)ネットワークの最も中心的なノードと他のすべてのノードとの中心性の差の総和を計算し、(b)この量を、同サイズの任意のネットワークにおけるその差の理論上の最大総和で割る したがって、すべての中心性尺度はそれぞれ自身の集中度尺度を持ちうる。形式的に定義すると、$C_x(p_i)$ を点 $i$ の任意の中心性尺度、$C_x(p_{\ast })$ をネットワーク内での最大値とし、次の式

$max\sum _{i=1}^N(C_x(p_{\ast })-C_x(p_i))$

が同じノード数の任意のグラフに対する点中心性 $C_x$ の差の最大総和であるとき、ネットワークの集中度は次のようになる

$C_x=\frac{\sum _{i=1}^N(C_x(p_{\ast })-C_x(p_i))}{max\sum _{i=1}^N(C_x(p_{\ast })-C_x(p_i))}.$

この概念はテンプレート:仮リンクによる。

非類似性に基づく中心性尺度

図示されたネットワークにおいて、緑と赤のノードは互いに近傍を共有しないため最も非類似である。したがって、緑のノードは灰色のノードよりも赤のノードの中心性に大きく寄与する。灰色のノードは仲介者なしで各青いノードに直接アクセスできるため、赤のノードにとって冗長である。

所与のネットワークのノードのランキングでより良い結果を得るために、Alvarez-Socorro らは非類似性尺度（分類理論とデータマイニングに特有のもの）を用いて複雑ネットワークにおける中心性尺度を拡張した。これは固有ベクトル中心性で例示され、固有値問題

$W𝐜=\lambda 𝐜$

の解を通じて各ノードの中心性を計算する。ここで $W_{ij}=A_{ij}{D}_{ij}$（座標ごとの積）であり、$D_{ij}$ は非類似性尺度、たとえば次で与えられるテンプレート:仮リンク非類似性を通じて定義される任意の非類似性行列である。

$D_{ij}=1-\frac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}$

この尺度により、各ノードが所与のノードの中心性に与えるトポロジカルな寄与（寄与中心性と呼ばれる所以である）を定量化でき、非類似性が大きいノードほど大きな重み・関連性を持つ。これらのノードは、自分自身では直接アクセスできないノードへのアクセスを当該ノードに可能にするからである。

$W$ が非負であることは注目に値する。$A$ と $D$ が非負行列だからであり、したがってペロン＝フロベニウスの定理を用いて、上記の問題が c 非負で λ = λ_max に対して唯一の解を持つことを保証できる。それにより、各ノードの中心性は

$c_i=\frac{1}{n}\sum _{j=1}^n{W}_{ij}{c}_j,i=1,\cdots ,n$

と推論できる。ここで $n$ はネットワーク内のノード数である。いくつかの非類似性尺度とネットワークがでテストされ、研究されたケースで改善された結果が得られている。

交通ネットワークで用いられる中心性尺度

道路網や鉄道網のような交通ネットワークは、交通科学や都市計画で広く研究されている。近年の研究の多くは、中心性尺度を交通ネットワークの分析に用いることに焦点を当てている。これらの研究の多くは媒介中心性のような汎用的な中心性尺度を単に用いるだけであるが、交通ネットワーク分析のために特別に定義された独自の中心性尺度もある。その中で著名なのが交通中心性（Transportation Centrality）である。

交通中心性は、ネットワーク内のノード対間の経路のうち、着目ノードを通過するものの割合の総和を測る。この点で媒介中心性と類似している。ただし最短経路のみを考慮する媒介中心性とは異なり、交通中心性はノード対間のすべての可能な経路を考慮する。したがって交通中心性は媒介中心性の汎用版であり、特定の条件下では実際に媒介中心性へ帰着する。

所与のノード v の交通中心性は次のように定義される:

$TC(v)=1/((N-1)(N-2)){\mathrm{\Sigma }}_{s\ne v\ne t}\frac{{\mathrm{\Sigma }}_{i\in P_{s,t}^v}{e}^{-\beta C_{s,t}^i}}{{\mathrm{\Sigma }}_{j\in P_{s,t}^v}{e}^{-\beta C_{s,t}^j}}$

グループ中心性

中心性尺度がノードのネットワーク上の位置に基づいて数値や順位を割り当てられるのと同様に、ノードの集合についても同様のことが興味の対象となりうる。そこで、中心性尺度をノードの集団へ一般化する案が提案されている。単集合の場合、これらのグループ中心性尺度は通常、対応する個々のノード中心性と一致する。 たとえば、サイズ $k$ のノード集合 $S$ のグループ近接中心性は次のように定義される。

$C(S)=\frac{N-k}{\sum _u\underset{s\in S}{min}d(u,s)}$

ここで $N$ はグラフ内のノード数である。 この定義は $k=1$ のとき近接中心性に簡約される。

しかし、個々のノードの中心性尺度では中心性を最大化するノードが通常多項式時間で見つかるのに対し、多くの尺度について、グループ中心性を最大化するサイズ $k$ の集合を見つけることはNP困難である。

関連項目

• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク
• グラフにおける距離

参考文献

• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16–61, LNCS 3418, Springer-Verlag.