媒介中心性

グラフ理論において、媒介中心性は、最短経路に基づくグラフの中心性の尺度です。連結グラフのすべての頂点ペアには、頂点間に少なくとも 1 つの最短経路が存在します。つまり、経路が通過する辺の数 (重みなしグラフの場合) または辺の重みの合計 (重み付きグラフの場合) が最小になる経路が少なくとも 1 つ存在します。各頂点の媒介中心性は、頂点を通過するこれらの最短経路の数です。

媒介中心性は、中心性の一般的な尺度として考案されました。^{[1]これは、ソーシャル}ネットワーク、生物学、輸送、科学的協力に関連する問題を含む、ネットワーク理論の幅広い問題に適用されます。初期の著者は、中心性は媒介に基づいていると直感的に説明していましたが、媒介中心性の最初の正式な定義を与えたのはフリーマン（1977）でした。

媒介中心性はネットワーク理論で幅広く応用されており、ノードが互いの間に立つ度合いを表します。たとえば、電気通信ネットワークでは、媒介中心性が高いノードは、より多くの情報がそのノードを通過するため、ネットワークをより強力に制御できます。

ノードの媒介中心性は次の式で表されます。 ${\displaystyle v}$

${\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

ここで、はノードからノードへの最短経路の総数であり、は通過する経路の数です（ は終点ではありません）。^[2]${\displaystyle \sigma_{st}}$${\displaystyle s}$${\displaystyle t}$${\displaystyle \sigma _{st}(v)}$${\displaystyle v}$${\displaystyle v}$

ノードの媒介中心性は、総和インデックスが示すように、ノードのペアの数に応じて変化することに注意してください。したがって、 を を含まないノードのペアの数で割ることで、計算を再スケールできます。有向グラフの場合は で、無向グラフの場合はで割ります。ここで、 は巨大コンポーネント内のノードの数です。 これは、1 つのノードをすべての最短経路が横切る、可能な限り高い値にスケールすることに注意してください。 これは多くの場合当てはまらないため、精度を落とさずに正規化を実行できます。 ${\displaystyle v}$${\displaystyle g\in [0,1]}$${\displaystyle (N-1)(N-2)}$${\displaystyle (N-1)(N-2)/2}$${\displaystyle N}$

${\displaystyle {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

その結果は次のようになります:

${\displaystyle \max({\mbox{normal}})=1}$

${\displaystyle \min({\mbox{normal}})=0}$

これは常に小さい範囲から大きい範囲へのスケーリングとなるため、精度が失われないことに注意してください。

重み付けされたネットワークでは、ノードを接続するリンクはバイナリ相互作用として扱われなくなり、容量、影響、頻度などに比例して重み付けされます。これにより、トポロジ効果を超えて、ネットワーク内に別の異質性の次元が追加されます。重み付けされたネットワーク内のノードの強度は、隣接するエッジの重みの合計によって決まります。

${\displaystyle s_{i}=\sum _{j=1}^{N}a_{ij}w_{ij}}$

および は、それぞれノードと間の隣接行列と重み行列です。スケールフリー ネットワークに見られる次数のべき乗分布と同様に、特定のノードの強度もべき乗分布に従います。 ${\displaystyle a_{ij}}$${\displaystyle w_{ij}}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle s(k)\approx k^{\beta }}$

中間点を持つ頂点の強度の平均値の研究では、関数の振る舞いはスケーリング形式で近似できることが示されている：^[3]${\displaystyle s(b)}$${\displaystyle b}$

${\displaystyle s(b)\approx b^{\alpha }}$

浸透中心性は重み付き媒介中心性の一種ですが、この重みを計算する際に各最短経路のソース ノードとターゲット ノードの「状態」を考慮します。複雑なネットワークでは、さまざまなシナリオで「伝染」の浸透が発生します。たとえば、ウイルスや細菌の感染は、接触ネットワークと呼ばれる人々のソーシャル ネットワークを介して広がる可能性があります。病気の拡散は、道路、鉄道、または航空リンクで接続された町や人口密集地のネットワークを考慮することで、より高い抽象レベルで考えることもできます。コンピューター ウイルスはコンピューター ネットワークを介して広がる可能性があります。ビジネスのオファーや取引に関する噂やニュースも、人々のソーシャル ネットワークを介して広がる可能性があります。これらのシナリオのすべてで、「伝染」は複雑なネットワークのリンクを介して広がり、回復可能かどうかにかかわらず、広がるにつれてノードの「状態」を変更します。たとえば、疫学のシナリオでは、感染が広がるにつれて、個人は「感受性」状態から「感染」状態になります。上記の例で個々のノードがとり得る状態は、伝染が広がるにつれて、バイナリ（ニュースを受け取った/受け取っていないなど）、離散（感染しやすい/感染している/回復している）、または連続（町内の感染者の割合など）になる可能性があります。これらすべてのシナリオに共通する特徴は、伝染が広がるとネットワーク内のノードの状態が変化するということです。パーコレーション中心性（PC）はこれを念頭に置いて提案されたもので、ネットワークを通じたパーコレーションを支援するという観点からノードの重要性を具体的に測定します。この尺度は、Piraveenan、Prokopenko、Hossain（2013）によって提案されました。^[4]

パーコレーション中心性は、特定のノードの特定の時点において、そのノードを通過する「パーコレーション パス」の割合として定義されます。「パーコレーション パス」とは、ソース ノードがパーコレーションされている (感染しているなど) 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(|V||E|)}$${\displaystyle O(|V|^{3})}$

グラフ内のすべての頂点の媒介中心性と近接中心性を計算するには、グラフ上のすべての頂点ペア間の最短経路を計算する必要があり、これは、1つの最短経路を見つけるだけでなく、2つのノード間のすべての最短経路を数えるように修正されたフロイド-ワーシャルアルゴリズムでは時間がかかります。疎なグラフでは、ジョンソンのアルゴリズムまたはブランデスのアルゴリズムの方が効率的かもしれませんが、どちらも時間がかかります。重み付けされていないグラフでは、ブランデスのアルゴリズムを使用して媒介中心性を計算するのに時間がかかります。 ^[5]${\displaystyle \Theta (|V|^{3})}$${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$${\displaystyle O(|V||E|)}$

グラフ内のすべての頂点の媒介中心性と近接中心性を計算する際、グラフは無向であり、ループと複数のエッジを許容して接続されているものと想定されます。特にネットワーク グラフを扱う場合、単純な関係 (エッジは 2 人の人物または頂点間の接続を表します) を維持するために、グラフにはループや複数のエッジがないことがよくあります。この場合、ブランデスのアルゴリズムを使用すると、最終的な中心性スコアが 2 で割られ、各最短パスが 2 回カウントされることが考慮されます。^[6]

別のアルゴリズムは、探索と利用のトレードオフを制御するハイパーパラメータを導入することで、測地線上で計算されるフリーマンの媒介性とすべてのパス上で計算されるニューマンの媒介性を一般化します。時間計算量は、グラフ内のエッジの数とノードの数を掛け合わせたものです。^[7]

双方向幅優先探索を用いてパスをサンプリングすることで、媒介中心性の近似的確率的推定をはるかに速く得ることができる。^[8]

ソーシャルネットワーク分析では、媒介中心性はさまざまな意味合いを持つことがあります。マクロ的な視点から見ると、橋渡し役または「構造的穴」（高い媒介中心性で示される）は権力を反映しています。なぜなら、橋渡し役の人は、橋渡し役が繋ぐ人々に対して制御（情報を共有するかどうかの決定など）を行えるからです。^[9]エゴネットワークのミクロな視点（つまり、1次接続のみを考慮）から見ると、オンラインソーシャルネットワークでは、媒介中心性が高いことは、最も親しい友人の指名（つまり、強い対人関係のつながり）と一致します。これは、遠い社会的サークル（家族や大学など）が橋渡しされるとき（多くの場合、エゴによる紹介の結果）に関係に投資される社会資本を反映しているためです。^[10]

媒介中心性は、河川網の位相的複雑性や海上貿易におけるその利用を分析するために使用されてきた。 ^{[11] [12]}

媒介中心性はネットワークの接続性と関連しており、媒介性の高い頂点は削除されるとグラフが切断される可能性があります (カット セットを参照)。

• 中心性