中心性

グラフ理論とネットワーク分析では、中心性の指標は、グラフ内のノードにネットワーク上の位置に対応する番号または順位を割り当てる。応用分野としては、ソーシャルネットワークで最も影響力のある人物、インターネットや都市ネットワークの重要なインフラノード、病気のスーパースプレッダー、脳ネットワークの特定などがある。^{[1] [2]中心性の概念は、}ソーシャルネットワーク分析で最初に開発され、中心性を測定するために使用される用語の多くは、その社会学的な起源を反映している。^[3]

中心性指標は、「重要な頂点の特徴は何か？」という質問に対する答えです。この答えはグラフの頂点上の実数値関数で与えられ、生成された値は最も重要なノードを識別するランキングを提供することが期待されます。^{[4] [5] [6]}

「重要性」という言葉には幅広い意味があり、中心性の定義も多種多様です。2 つの分類体系が提案されています。「重要性」は、ネットワークを介したフローまたは転送のタイプに関連して考えることができます。これにより、中心性は、重要とみなされるフローのタイプによって分類できます。^[5]「重要性」は、ネットワークの凝集性への関与として考えることができます。これにより、中心性は、凝集性の測定方法に基づいて分類できます。^[7]これらのアプローチはどちらも、中心性を明確なカテゴリに分類します。さらに、あるカテゴリに適した中心性は、別のカテゴリに適用すると「間違った」結果になることが多いという結論もあります。^[5]

すべてではないが、多くの中心性尺度は、特定の頂点を通過する何らかのタイプのパス（ウォークとも呼ばれる）の数を効果的にカウントします。これらの尺度は、関連するウォークの定義方法とカウント方法が異なります。このグループに限定すると、長さ 1 のウォーク（次数中心性）から無限ウォーク（固有ベクトル中心性）まで、さまざまな中心性をスペクトル上に配置する分類が可能になります。^{[4] [8]}媒介中心性などの他の中心性尺度は、全体的な接続性だけでなく、ネットワークの接続性にとって極めて重要な位置を占めることに焦点を当てています。

ネットワークは、何かが流れる経路の記述と考えることができます。これにより、フローの種類と中心性によってエンコードされた経路の種類に基づいた特徴付けが可能になります。フローは転送に基づくことができ、分割できない各アイテムが 1 つのノードから別のノードに移動します。これは、荷物が配達場所から顧客の家に届くのと同じです。2 番目のケースはシリアル複製です。これは、アイテムが複製され、ソースとターゲットの両方がそれを持つようになります。例としては、ゴシップによる情報の伝播があります。この場合は、情報はプライベートな方法で伝播され、ソース ノードとターゲット ノードの両方にプロセスの最後に通知されます。最後のケースは並列複製です。これは、アイテムが複数のリンクに同時に複製されるもので、ラジオ放送が一度に多くのリスナーに同じ情報を提供するのと同じです。^[5]

同様に、パスの種類は、測地線（最短パス）、パス （頂点を複数回訪問しない）、トレイル（頂点を複数回訪問でき、辺を複数回横断しない）、ウォーク（頂点と辺を複数回訪問/横断できる）に制限できます。^[5]

中心性の構築方法から別の分類を導き出すことができます。これもまた 2 つのクラスに分かれます。中心性は放射状中心性と中間中心性のいずれかです。放射状中心性は、指定された頂点から開始/終了するウォークを数えます。次数中心性と固有値中心性は放射状中心性の例で、長さ 1 または長さ無限大のウォークの数を数えます。中間中心性は、指定された頂点を通過するウォークの数を数えます。標準的な例は、フリーマンの媒介中心性で、指定された頂点を通過する最短経路の数です。^[7]

同様に、カウントはウォークのボリュームまたは長さのいずれかをキャプチャできます。ボリュームは、特定のタイプのウォークの合計数です。前の段落の3つの例はこのカテゴリに該当します。長さは、グラフ内の特定の頂点から残りの頂点までの距離をキャプチャします。近接中心性、つまり特定の頂点から他のすべての頂点までの合計測地距離は、最もよく知られている例です。^[7]この分類は、カウントされるウォークのタイプ（ウォーク、トレイル、パス、測地線）とは無関係であることに注意してください。

ボルガッティとエヴェレットは、この類型論が中心性尺度を比較する最良の方法への洞察を提供すると提案している。この2×2分類で同じボックスに配置された中心性は、妥当な代替案を作るのに十分なほど類似しており、特定のアプリケーションでどちらが優れているかを合理的に比較することができる。しかし、異なるボックスからの尺度はカテゴリ的に異なる。相対的な適合性の評価は、どのカテゴリがより適切であるかを事前に決定する文脈内でのみ行われるため、比較は無意味になる。^[7]

ウォーク構造による特徴付けは、広く使用されている中心性のほとんどすべてが放射状体積の尺度であることを示しています。これらは、頂点の中心性が、それが関連付けられている頂点の中心性の関数であるという信念をエンコードします。中心性は、関連付けの定義方法によって区別されます。

Bonacich は、関連性がウォークの観点から定義される場合、考慮されるウォークの長さに基づいて中心性のファミリーを定義できることを示しました。 ^[4]次数中心性は長さ 1 のウォークを数え、固有値中心性は長さ無限大のウォークを数えます。関連性の代替定義も妥当です。アルファ中心性では、頂点が外部の影響源を持つことが許されます。Estrada のサブグラフ中心性では、閉じたパス (三角形、四角形など) のみを数えることを提案しています。

このような測定法の核心は、グラフの隣接行列のべき乗がそのべき乗で与えられた長さの歩行回数を与えるという観察である。同様に、行列指数も与えられた長さの歩行回数と密接に関係している。隣接行列の初期変換により、カウントされる歩行の種類を異なる定義にすることができる。どちらのアプローチでも、頂点の中心性は、次の無限和として表現できる。

${\displaystyle \sum _{k=0}^{\infty }A_{R}^{k}\beta ^{k}}$

行列の累乗または

${\displaystyle \sum _{k=0}^{\infty }{\frac {(A_{R}\beta )^{k}}{k!}}}$

行列指数関数の場合、

• ${\displaystyle k}$歩行距離は
• ${\displaystyle A_{R}}$は変換された隣接行列であり、
• ${\displaystyle \beta }$合計の収束を保証する割引パラメータです。

ボナシッチの測度族は隣接行列を変換しません。アルファ中心性は隣接行列をそのレゾルベントに置き換えます。サブグラフ中心性は隣接行列をそのトレースに置き換えます。驚くべき結論は、隣接行列の初期変換に関係なく、このようなアプローチはすべて共通の限界動作を持つということです。 がゼロに近づくにつれて、インデックスは次数中心性に収束します。 が最大値に近づくにつれて、インデックスは固有値中心性に収束します。^[8]${\displaystyle \beta }$${\displaystyle \beta }$

前述の標準的な評価基準のほとんどに共通する特徴は、ノードが単独で果たす役割のみに焦点を当ててノードの重要性を評価することです。ただし、多くのアプリケーションでは、ノードの機能をグループで考慮すると相乗効果が生じる可能性があるため、このようなアプローチは不十分です。

たとえば、伝染病を食い止める問題を考えてみましょう。上のネットワークの画像を見て、どのノードにワクチンを接種すべきでしょうか。 前述の尺度に基づいて、病気の蔓延において最も重要なノードを認識したいと考えています。 ノードの個々の特徴に焦点を当てた中心性のみに基づいたアプローチは、良い考えではないかもしれません。 赤い四角の中のノードは、個別には病気の蔓延を止めることはできませんが、グループとして考えると、ノード、、 で病気が始まっていれば、病気を止めることができることは明らかです。 ゲーム理論的な中心性は、ゲーム理論のツールを使用して、記述された問題と機会を検討しようとします。^{[9]で提案されているアプローチでは、}シャプレー値を使用します。 シャプレー値の計算には時間計算量の難しさがあるため、この分野でのほとんどの取り組みは、ネットワークの特異なトポロジーまたは問題の特殊な特性に依存する新しいアルゴリズムと方法の実装に向けられています。 このようなアプローチは、時間計算量を指数関数から多項式に削減することにつながる可能性があります。 ${\displaystyle v_{1}}$${\displaystyle v_{4}}$${\displaystyle v_{5}}$

同様に、ソリューションコンセプトの権威分布（^[10]）は、シャプレー値ではなくシャプレー・シュビックのパワーインデックスを適用して、プレーヤー間の双方向の直接的な影響を測定します。この分布は、確かに固有ベクトル中心性の一種です。これは、米国の大学のランキングなど 、Hu（2020） ^{[11]のビッグデータオブジェクトのソートに使用されています。}

中心性指標には、明白な限界と微妙な限界の 2 つの重要な限界があります。明白な限界は、あるアプリケーションに最適な中心性が、別のアプリケーションでは最適ではないことが多いということです。実際、そうでなかったら、これほど多くの異なる中心性は必要ないはずです。この現象の例として、クラックハート カイト グラフが挙げられます。このグラフでは、中心性の 3 つの異なる概念によって、最も中心となる頂点の 3 つの異なる選択肢が与えられます。^[12]

より微妙な制限は、頂点の中心性が頂点の相対的な重要性を示すという、よくある誤解です。中心性指標は、最も重要な頂点を示すランキングを生成するために明示的に設計されています。^{[4] [5]}中心性指標は、先ほど述べた制限の下では、これをうまく実行します。それらは、一般的なノードの影響を測定するようには設計されていません。最近、ネットワーク物理学者は、この問題に対処するために ノードの影響測定基準の開発を開始しました 。

この誤りは2つあります。第一に、ランキングは頂点を重要度で順序付けるだけで、ランキングの異なるレベル間の重要度の差を定量化しません。この問題は、問題の中心性測定にフリーマン集中化を適用することで軽減できます。フリーマン集中化は、集中化スコアの違いに応じてノードの重要性についてある程度の洞察を提供します。さらに、フリーマン集中化により、最高の集中化スコアを比較することで、複数のネットワークを比較することができます。^[13]

第二に、特定のネットワーク/アプリケーションで最も重要な頂点を（正しく）識別する特徴は、必ずしも残りの頂点に一般化されるわけではありません。他のネットワークノードの大部分にとって、ランキングは無意味である可能性があります。^{[14] [15] [16] [17]}これは、たとえば、Google画像検索の最初の数件の結果のみが適切な順序で表示される理由を説明しています。ページランクは非常に不安定な指標であり、ジャンプパラメータを少し調整すると、頻繁にランクが逆転します。^[18]

中心性指標がネットワークの残りの部分に一般化できないことは、一見直感に反するように思えるかもしれないが、それは上記の定義から直接導かれるものである。複雑なネットワークは異質なトポロジーを持っている。最適な尺度が最も重要な頂点のネットワーク構造に依存する限り、そのような頂点に最適な尺度は、ネットワークの残りの部分にとっては最適ではない。^[14]

歴史的に最初で概念的に最も単純なのは次数中心性で、これはノードに関連するリンクの数（つまり、ノードが持つつながりの数）として定義されます。次数は、ネットワークを流れるもの（ウイルスや情報など）にノードが直接感染するリスクの観点から解釈できます。有向ネットワーク（つながりに方向性がある）の場合、通常、次数中心性の 2 つの別個の尺度、つまり入次数と出次数を定義します。したがって、入次数はノードに向けられたつながりの数であり、出次数はノードが他のノードに向けるつながりの数です。つながりが友情や協力などの肯定的な側面に関連付けられている場合、入次数は人気の形として、出次数は社交性として解釈されることがよくあります。

頂点と辺を持つグラフにおいて、頂点の次数中心性は次のように定義される。 ${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$

${\displaystyle C_{D}(v)=\deg(v)}$

グラフ内のすべてのノードの次数中心性を計算するには、グラフの密な隣接行列表現を使用し、エッジの場合は疎行列表現を使用します。 ${\displaystyle \Theta (V^{2})}$ ${\displaystyle \Theta (E)}$

ノードレベルでの中心性の定義はグラフ全体に拡張することができ、その場合にはグラフの集中化について話している。^[19]が における最高次中心性を持つノードであるとする。が以下の量を最大化する -ノード接続グラフであるとする（における最高次中心性を持つノードは である）。 ${\displaystyle v*}$${\displaystyle G}$${\displaystyle X:=(Y,Z)}$${\displaystyle |Y|}$${\displaystyle y*}$${\displaystyle X}$

${\displaystyle H=\sum _{j=1}^{|Y|}[C_{D}(y*)-C_{D}(y_{j})]}$

それに応じて、グラフの次数集中化は次のようになります。 ${\displaystyle G}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{H}}}$

の値は、グラフに1つの中心ノードがあり、他のすべてのノードが接続されているときに最大になります（スターグラフ）。この場合、 ${\displaystyle H}$${\displaystyle X}$

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

つまり、どんなグラフでも${\displaystyle G:=(V,E),}$

${\displaystyle C_{D}(G)={\frac {\sum _{i=1}^{|V|}[C_{D}(v*)-C_{D}(v_{i})]}{|V|^{2}-3|V|+2}}}$

また、次数中心性に関する新たな広範なグローバル尺度であるTendency to Make Hub (TMH)は次のように定義します。^[2]

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

ここで、TMH はネットワーク内の次数中心性の出現によって増加します。

接続された グラフでは、ノードの正規化された 近接中心性（または近さ）は、そのノードとグラフ内の他のすべてのノード間の最短経路の平均長さです。したがって、ノードが中心にあるほど、他のすべてのノードに近くなります。

近さはアレックス・バベラス（1950）によって遠さの逆数として定義され、^{[20] [21]}は頂点uとvの間の距離である。しかし、近さ中心性について話すとき、人々は通常、前の式にグラフ内のノードの数を 掛けた正規化された形式を参照する。${\textstyle C_{B}(v)=(\sum _{u}d(u,v))^{-1}}$${\displaystyle d(u,v)}$${\displaystyle N-1}$${\displaystyle N}$

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

この正規化により、異なるサイズのグラフのノード間の比較が可能になります。多くのグラフでは、近さの逆数と次数の対数の間には強い相関関係があります。^[22] ここで、は頂点vの次数であり、αとβは各ネットワークの定数です。 ${\displaystyle (C(v))^{-1}\approx -\alpha \ln(k_{v})+\beta }$${\displaystyle k_{v}}$

他のすべてのノードからまたは他のすべてのノードまでの距離を取ることは、無向グラフでは無関係ですが、有向グラフではまったく異なる結果が生じる可能性があります(たとえば、Web サイトは発信リンクからの近接中心性が高くても、着信リンクからの近接中心性は低くなる可能性があります)。

（必ずしも接続されているとは限らない）グラフでは、調和中心性は近接中心性の定義における合計と逆数の演算を逆にします。

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

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

調和中心性は、 MarchioriとLatora（2000）^[23]によって提案され、その後Dekker（2005）によって「価値中心性」という名前で独立して提案され^{[24] 、Rochat（2009）によっても提案されました[25]}。

媒介度はグラフ内の頂点の中心性の尺度です（辺の媒介度もありますが、ここでは説明しません）。媒介度中心性は、2 つの他のノード間の最短経路に沿ってノードがブリッジとして機能する回数を定量化します。これは、ソーシャル ネットワーク内の他の人間同士のコミュニケーションに対する人間の制御を定量化する尺度として、リントン フリーマンによって導入されました。^{[26]彼の概念では、ランダムに選択された 2 つの頂点間のランダムに選択された}最短経路上に出現する確率が高い頂点は、媒介度が高くなります。

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

1. 各頂点のペア ( s、t ) について、それらの間の最短経路を計算します。
2. 各頂点のペア ( s、t ) について、問題の頂点 (ここでは頂点v ) を通過する最短経路の割合を決定します。
3. この分数をすべての頂点ペア ( s、t ) にわたって合計します。

より簡潔に中間性は次のように表現できる: ^[27]

${\displaystyle C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

ここで、 はノードからノードへの最短経路の総数であり、 はを通過する経路の数です。媒介性は、v を含まない頂点のペアの数で割ることで正規化できます。有向グラフの場合は、無向グラフの場合は です。たとえば、無向の星型グラフでは、中心の頂点 (考えられるすべての最短経路に含まれる) の媒介性は(正規化した場合、1) になりますが、葉 (どの最短経路にも含まれない) の媒介性は 0 になります。 ${\displaystyle \sigma _{st}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle \sigma _{st}(v)}$${\displaystyle v}$${\displaystyle (n-1)(n-2)}$${\displaystyle (n-1)(n-2)/2}$${\displaystyle (n-1)(n-2)/2}$

計算面から見ると、グラフ内のすべての頂点の媒介中心性と近接中心性はどちらも、グラフ上のすべての頂点ペア間の最短経路を計算することを含み、これにはフロイド・ワーシャルアルゴリズムで時間がかかります。ただし、スパースグラフでは、ジョンソンのアルゴリズムの方が効率的ですが、時間がかかります。重み付けされていないグラフの場合、計算はブランデスのアルゴリズム^[27]で実行できますが、時間がかかります。通常、これらのアルゴリズムは、グラフが無向であり、ループと複数のエッジを許容して接続されていることを前提としています。特にネットワークグラフを扱う場合、単純な関係 (エッジが2人または2つの頂点間の接続を表す) を維持するために、グラフにはループや複数のエッジがないことがよくあります。この場合、ブランデスのアルゴリズムを使用すると、各最短経路が2回カウントされることを考慮して、最終的な中心性スコアが2で割られます。^[27]${\displaystyle O(V^{3})}$${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$${\displaystyle O(|V||E|)}$

固有ベクトル中心性（または固有中心性）は、ネットワーク内のノードの影響力を測る尺度である。高スコアのノードへの接続は、低スコアのノードへの同等の接続よりも、問題のノードのスコアに大きく貢献するという概念に基づいて、ネットワーク内のすべてのノードに相対的なスコアを割り当てる。^{[28] [6]} GoogleのPageRankとKatz中心性は、固有ベクトル中心性の変種である。^[29]

頂点数を持つグラフが与えられた場合、 は隣接行列、つまり頂点 が頂点 にリンクされている場合、 となり、それ以外の場合は となります。頂点 の相対中心性スコアは、次の方程式の頂点集合に対する非負の解として定義できます。 ${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle A=(a_{v,t})}$${\displaystyle a_{v,t}=1}$${\displaystyle v}$${\displaystyle t}$${\displaystyle a_{v,t}=0}$${\displaystyle x_{v}}$${\displaystyle v}$${\displaystyle v\in V}$

${\displaystyle x_{v}={\frac {1}{\lambda }}\sum _{t\in M(v)}x_{t}={\frac {1}{\lambda }}\sum _{t\in G}a_{v,t}x_{t}}$

ここで は の近傍の集合であり、 は定数である。少し整理すると、これはベクトル表記で固有ベクトル方程式 として書き直すことができる。${\displaystyle M(v)}$${\displaystyle v}$${\displaystyle \lambda }$

${\displaystyle \mathbf {Ax} ={\lambda }\mathbf {x} }$。

一般に、非ゼロの固有ベクトル解が存在するさまざまな固有値 があります。隣接行列の要素は非負なので、ペロン-フロベニウスの定理により、実数で正の唯一の最大固有値が存在します。この最大固有値が、目的の中心性尺度になります。^[28]次に、関連する固有ベクトルの要素が、ネットワーク内の頂点の相対的な中心性スコアを与えます。固有ベクトルは共通因子までしか定義されないため、頂点の中心性の比率のみが明確に定義されます。絶対スコアを定義するには、たとえば、すべての頂点の合計が 1 または頂点の総数nになるように、固有ベクトルを正規化する必要があります。べき乗反復法は、この主要な固有ベクトルを見つけるために使用できる多くの固有値アルゴリズムの 1 つです。 ^{[29]さらに、これを一般化して、} Aの要素を確率行列のように接続強度を表す実数にすることもできる。 ${\displaystyle \lambda }$${\displaystyle v^{th}}$${\displaystyle v}$

カッツ中心性^[30]は次数中心性の一般化である。次数中心性は直接隣接ノードの数を測定し、カッツ中心性はパスを介して接続できるすべてのノードの数を測定し、遠方のノードの貢献はペナルティを受ける。数学的には次のように定義される。

${\displaystyle x_{i}=\sum _{k=1}^{\infty }\sum _{j=1}^{N}\alpha ^{k}(A^{k})_{ji}}$

ここで、は の減衰係数です 。 ${\displaystyle \alpha }$${\displaystyle (0,1)}$

カッツ中心性は、固有ベクトル中心性の変形として考えることができる。カッツ中心性の別の形式は、

${\displaystyle x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j}+1).}$

固有ベクトル中心性の表現と 比較すると、${\displaystyle x_{j}}$${\displaystyle x_{j}+1.}$

^[31]によれば、主固有ベクトル（隣接行列の最大固有値に関連付けられている）は、下から 近づくにつれてカッツ中心性の極限となることが示されています。${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle {\tfrac {1}{\lambda }}}$

PageRankは次の式を満たす

${\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}$

どこ

${\displaystyle L(j)=\sum _{i}a_{ji}}$

はノードの近傍の数（または有向グラフのアウトバウンドリンクの数）です。固有ベクトル中心性やカッツ中心性と比較した場合、大きな違いの1つはスケーリング係数です。Pag​​eRankと固有ベクトル中心性のもう1つの違いは、PageRankベクトルが左手固有ベクトルであることです（係数のインデックスが逆になっていることに注意してください）。^[32]${\displaystyle j}$${\displaystyle L(j)}$${\displaystyle a_{ji}}$

複雑なネットワーク内の単一ノードの「重要性」を判断するための中心性尺度は多数存在します。しかし、これらの尺度は、純粋に位相的な観点からノードの重要性を定量化するものであり、ノードの値はノードの「状態」にはまったく依存しません。ノードの値は、ネットワークのダイナミクスに関係なく一定のままです。これは、重み付けされた媒介性尺度にも当てはまります。ただし、媒介性中心性または別の中心性尺度の観点からはノードが中心に位置する可能性は十分にありますが、浸透があるネットワークのコンテキストでは「中心」に位置しない可能性があります。「伝染」の浸透は、複雑なネットワークでさまざまなシナリオで発生します。たとえば、ウイルスまたは細菌感染は、接触ネットワークと呼ばれる人々のソーシャル ネットワークを介して広がる可能性があります。病気の蔓延は、道路、鉄道、または航空リンクで接続された町や人口密集地のネットワークを考慮することで、より高い抽象レベルで考えることもできます。コンピューター ウイルスは、コンピューター ネットワークを介して広がる可能性があります。ビジネスのオファーや取引に関する噂やニュースも、人々のソーシャル ネットワークを通じて広がる可能性があります。これらのシナリオのすべてにおいて、「伝染」は複雑なネットワークのリンクを介して広がり、広がるにつれて、回復可能かどうかにかかわらず、ノードの「状態」が変化します。たとえば、疫学シナリオでは、感染が広がるにつれて、個人は「感染しやすい」状態から「感染した」状態になります。上記の例で個々のノードがとる可能性のある状態は、伝染が広がるにつれて、バイナリ (ニュースを受け取った/受け取っていないなど)、離散的 (感染しやすい/感染した/回復した)、または連続的 (町内の感染者の割合など) になる可能性があります。これらすべてのシナリオに共通する特徴は、伝染が広がると、ネットワーク内のノードの状態が変化するということです。これを念頭に置いて、浸透中心性 (PC) が提案されました。これは、ネットワークを通じた浸透を支援するという観点から、ノードの重要性を具体的に測定します。この測定基準は、Piraveenan らによって提案されました。^[33]

パーコレーション中心性は、特定のノードの特定の時点において、そのノードを通過する「パーコレーション パス」の割合として定義されます。「パーコレーション パス」とは、ソース ノードがパーコレーションされている (感染しているなど) 2 つのノード間の最短パスです。ターゲット ノードは、パーコレーションされているか、パーコレーションされていないか、部分的にパーコレーションされた状態です。

${\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}}{\frac {{x^{t}}_{s}}{{\sum {[{x^{t}}_{i}}]}-{x^{t}}_{v}}}}$

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

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

複雑なグラフ内の単一ノードのクリーク間中心性は、ノードと異なるクリークとの接続性を決定します。クリーク間接続性が高いノードは、グラフ内での情報や病気の伝播を促進します。クリークは、すべてのノードがクリーク内の他のすべてのノードに接続されているサブグラフです。頂点とエッジを持つ特定のグラフのノードのクリーク間接続性は、次のように定義されます。ここでは、頂点が属するクリークの数です。この指標は、2013 年に Faghani によって使用されました^[34]が、最初に提案したのは、1998 年に Everett と Borgatti によって、当時はクリーク重複中心性と呼ばれていました。 ${\displaystyle v}$${\displaystyle G:=(V,E)}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle X(v)}$${\displaystyle X(v)}$${\displaystyle v}$

あらゆるネットワークの集中化とは、そのネットワークの最も中心的なノードが、他のすべてのノードの中心性と比較して、どの程度中心的であるかを測る尺度である。^[13]集中化の尺度は、(a) ネットワーク内の最も中心的なノードと他のすべてのノードとの中心性の差の合計を計算し、(b) この量を、同じサイズのネットワーク内で理論上最大のそのような差の合計で割ります。^[13] したがって、すべての中心性尺度は、独自の集中化尺度を持つことができます。正式に定義すると、が点 の任意の中心性尺度である場合、がネットワーク内で最大のそのような尺度である場合、および次の場合: ${\displaystyle C_{x}(p_{i})}$${\displaystyle i}$${\displaystyle C_{x}(p_{*})}$

${\displaystyle \max \sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}$

同じ数のノードを持つ任意のグラフの点中心性の差の最大の合計がネットワークの中心化であるとき、ネットワークの中心化は次のようになる：^[13]${\displaystyle C_{x}}$

${\displaystyle C_{x}={\frac {\sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}{\max \sum _{i=1}^{N}(C_{x}(p_{*})-C_{x}(p_{i}))}}.}$

このコンセプトはリントン・フリーマンによるものです。

与えられたネットワークのノードのランキングにおいてより良い結果を得るために、^[35]では、複雑なネットワークにおける中心性指標を強化するために、非類似度指標（分類とデータマイニングの理論に特有）が使用されている。これは、固有値問題の解決を通じて各ノードの中心性を計算する 固有ベクトル中心性で説明される。

${\displaystyle W\mathbf {c} =\lambda \mathbf {c} }$

ここで、（座標間の積）は任意の非類似度行列であり、非類似度尺度（例えば、ジャカード非類似度） によって定義され、${\displaystyle W_{ij}=A_{ij}D_{ij}}$${\displaystyle D_{ij}}$

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

この尺度により、特定のノードの中心性に対する各ノードの位相的な貢献度 (貢献の中心性と呼ばれる理由) を定量化できます。非類似度が高いノードは、それ自体が直接アクセスできないノードにアクセスできるため、重み/関連性が高くなります。

は非負であることに注目してください。なぜなら、およびは非負行列であるためです。したがって、ペロン・フロベニウスの定理を使用して、上記の問題がλ  =  λ _maxでcが非負の場合に一意の解を持つことを保証できます。これにより、ネットワーク内の各ノードの中心性を推測できます。したがって、i番目のノードの中心性は ${\displaystyle W}$${\displaystyle A}$${\displaystyle D}$

${\displaystyle c_{i}={\dfrac {1}{n}}\sum _{j=1}^{n}W_{ij}c_{j},\,\,\,\,\,\,i=1,\cdots ,n}$

ここで、はネットワーク内のノードの数です。^[36]ではいくつかの非類似度尺度とネットワークがテストされ、研究対象となったケースでは改善された結果が得られました。 ${\displaystyle n}$

道路網や鉄道網などの交通ネットワークは、交通科学や都市計画の分野で広く研究されています。最近の多くの研究では、交通ネットワークを分析するために中心性指標を使用することに焦点を当てています。これらの研究の多くは、媒介中心性などの一般的な中心性指標を単純に使用していますが、交通ネットワーク分析に特化したカスタム中心性指標も定義されています。その中でも有名なのは交通中心性です。^[37]

輸送中心性は、ネットワーク内のノードのペアから、検討中のノードを通過するパスの割合の合計を測定します。この点では、媒介中心性と似ています。ただし、最短パスのみを考慮する媒介中心性とは異なり、輸送中心性は、ノードのペア間のすべての可能なパスを考慮します。したがって、輸送中心性は媒介中心性の汎用バージョンであり、特定の条件下では、媒介中心性に縮小されます。

与えられたノードvの交通中心性は次のように定義される: ^[37]

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

• アルファ中心性
• コア・周辺構造
• グラフ上の距離

• Koschützki, D.; Lehmann, KA; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. および Zlotowski, O. (2005) 中心性指標。Brandes, U. および Erlebach, T. (編) Network Analysis: Methodological Foundations、pp. 16–61、LNCS 3418、Springer-Verlag。