Betweenness Centrality
- 提唱者
- Freeman, L. C.
- 年
- 1977
- 種類
- Centrality measure
- 系統
- Network science
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Betweenness centralityは、1977年にLinton C. Freemanによって形式化され、ネットワーク内の他のすべてのノードペアを結ぶ最短経路上にノードがどれだけ頻繁に位置するかを測定します。Betweennessが高いノードは、ブリッジまたはブローカーとして機能します。それらを削除すると、他のどのノードを削除するよりもネットワークをより深刻に切断されたコンポーネントに分割します。
手法の背後にある直感
都市の道路網を想像してください。そこでは、すべての長距離ルートが単一の交差点を通過します。その交差点は、たとえ道路の数が中程度であっても、最大のBetweennessを持ちます。ソーシャルネットワークでは、それ以外では接続されていない2つのクリック間で情報を日常的にやり取りする人は、同じ位置を占めます。彼らは直接多くの人を知らないかもしれませんが、ネットワークをまとめる重要な経路上に位置しています。Betweenness centralityは、生の接続数に関係なく、まさにその仲介者の役割を定量化します。
歴史学
Linton Freemanは、1977年のSociometry誌の画期的な論文でBetweenness centralityを形式化しました。これは、Bavelas (1948) によるコミュニケーション実験での以前の非公式な概念の使用に基づいています。Freemanの定式化は、ノードの重要性に関するいくつかの緩やかな直感を単一の計算可能な尺度に統合し、ネットワーク科学で使用される標準的な定義となりました。Ulrik Brandesの2001年のアルゴリズムは、計算をO(V^3)からO(VE)に削減し、Betweenness centralityを数千ノードを持つネットワークで実用的なものにし、ソーシャルネットワーク分析ソフトウェアにおける標準ツールとしての地位を確立しました。
使うべき場面
仲介、ゲートキーピング、またはブリッジノード(それらを削除すると情報フローやネットワークの結束が妨げられるアクター)に関する研究課題がある場合は、Betweenness centralityを使用してください。有向グラフと無向グラフ、およびエッジの重みが距離またはコストを表す重み付きグラフに適しています。特に通信ネットワーク、引用ネットワーク、共同作成グラフ、サプライチェーンで価値があります。仲介が理論的な焦点ではない場合に、唯一のCentrality尺度として使用しないでください。隣接Centralityは、純粋な接続性の質問にはより単純で十分であり、Eigenvector CentralityまたはPageRank Centralityは、名声の伝播をよりよく捉えます。単純な計算はO(V^2 E)であるため、効率的な実装なしでは非常に大きな疎ネットワークには避けてください。
限界と注意点
- Brandesアルゴリズムを使用しても、非常に密なネットワークでは計算コストが高くなります。Webスケールのグラフには近似アルゴリズムが必要になる場合があります。
- フローがより長い経路(例:電気ネットワークのランダムウォーク)を通過するネットワークでは非現実的である可能性がある、アクターが最短経路を使用するという仮定。
- 欠落またはノイズの多いエッジに敏感です。たとえ少数の観測されていないつながりであっても、Betweennessのランキングを劇的に変化させる可能性があります。
- エッジの容量または関係の強度が大きく異なる場合でも、すべての最短経路に等しい重みを与えます。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 隣接CentralityやEigenvector Centralityでは完全に捉えられない、構造的な仲介とブリッジの役割を捉えます。
- 有向、無向、重み付き、重みなしネットワークに同じ式で適用可能です。
- 正規化されたスコアにより、1つのネットワーク内のノード間および異なるサイズのネットワーク間のノード間での意味のある比較が可能になります。
- Brandesアルゴリズムにより、NetworkXやigraphのような最適化されたライブラリで実装された場合、数百万ノードを持つネットワークの計算が可能になります。
- 理論的な解釈がしっかりしています。高いBetweennessを持つノードは、組織および社会研究において、情報制御、権力、および構造的空隙と経験的に関連付けられています。
応用
- 組織コミュニケーションネットワークにおけるゲートキーパーおよび情報仲介者の特定。
- 輸送、電力網、インターネットトポロジーの研究における重要なインフラストラクチャノードの検出。
- 引用および共同作成ネットワークにおける主要な中間著者または論文の検索。
- 企業間アライアンスネットワークにおける構造的空隙および仲介者の位置のマッピング。
- 疫学および噂拡散モデルにおける影響力のある拡散者の特定。
- 公衆衛生およびセキュリティ研究における標的介入(例:ワクチン接種、破壊)のためのノードの優先順位付け。
使い方
使い方
ネットワーク内の各順序付けられたノードペア(s, t)について、それらの間のすべての最短経路(測地線)が特定されます。重み付きグラフの場合、最短経路は最小の合計エッジ重みによって定義されます。重みなしグラフの場合、最小ホップ数によって定義されます。このステップは、Betweennessが分散される経路の宇宙を確立します。
各ペア(s, t)について、最短経路の総数sigma(s, t)がカウントされます。複数の等しく短い経路が存在する場合、それぞれが個別にカウントされます。この分母は、ルーティングに関する制約なしに、sとtの間の最短経路トラフィックの合計を表します。
数式
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } t各候補ノードv(vはsでもtでもない)について、実際にvを通過するsigma(s, t)最短経路の数がsigma(s, t | v)として記録されます。比率sigma(s, t | v) / sigma(s, t)は、sとtの間の最短経路トラフィックのうち、vをルーティングされる割合を示します。
数式
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } vこれらの割合は、すべての有効なペア(s, t)について合計され、生のBetweennessスコアC_B(v)を生成します。多くのペア間の最短経路を切断するようなノードの削除は、高い合計を蓄積し、構造的に重要な仲介者の位置を示します。
数式
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}生のスコアはネットワークサイズとともに増加するため、異なるサイズのネットワーク間での比較は無意味になります。無向グラフの場合は(n-1)(n-2)/2で、有向グラフの場合は(n-1)(n-2)で正規化すると、スコアは[0, 1]にスケーリングされます。1.0はノードがすべての最短経路上にあることを意味し、0はノードがどの最短経路上にもないことを意味します。Brandes (2001)は、各ノードに対して検索を繰り返すのではなく、すべてのBetweennessスコアを同時に計算するO(VE)アルゴリズムを導入しました。
数式
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}よくある落とし穴
- 両方を確認せずに、高いBetweennessを高い隣接と同一視すること。周辺ノードはBetweennessで1位になる可能性がありますが、隣接では最下位になる可能性があります。
- 異なるサイズのネットワーク間で生の(正規化されていない)Betweennessスコアを比較すること。
- 有向ネットワークでエッジの方向を無視すること。これは、フローが非対称な場合に誤解を招く仲介者の特定につながる可能性があります。
- エッジの重みが類似性ではなくコストとして正しく解釈されていることを確認せずに、重み付きネットワークに標準的なBetweennessを適用すること。
- 大規模ネットワークの近似Betweenness法を見落とし、数百万ノードでの計算を停止すること。
よくある質問
Betweenness centralityは、隣接Centralityとどのように異なりますか?
隣接Centralityは直接的な接続を数えます。多くのつながりを持つハブは高いスコアを得ます。Betweenness centralityは、ノードが他のノード間の最短経路上にどれだけ頻繁に位置するかを数えます。2つの疎なクラスターを接続するブリッジは、直接のつながりが少なくても高いスコアを得ます。これら2つの尺度は、構造的重要性に関して直交する側面を捉えます。
正規化されたBetweennessスコアまたは生のスコアを使用すべきですか?
異なるサイズのネットワーク間でノードを比較する場合、またはネットワークの規模に慣れていない読者に結果を示す場合は、常に正規化されたスコアを使用してください。生のスコアは、分母が一定である単一の固定ネットワーク内での比較にのみ許容されます。
重み付きエッジをどのように扱いますか?
エッジの重みを類似性ではなく、距離またはコストを表すように設定してください。ほとんどの実装(NetworkX、igraph)は、距離として解釈される重みパラメータを受け入れます。重みが強度または類似性を表す場合は、Betweennessを計算する前に反転してください(例:weight = 1/similarity)。
Betweenness centralityは、切断されたネットワークでも意味がありますか?
切断されたグラフの場合、異なるコンポーネント内のノード間の最短経路は未定義(無限)です。ほとんどのソフトウェアは、それらのペアを合計にゼロを寄与するものとして扱いますが、これはスコアを低下させる可能性があります。各連結コンポーネントを個別に分析するか、切断されたペアの明示的な処理を伴うストレスCentralityのようなバリアントを使用してください。
私のネットワークには数百万ノードがありますが、Betweenness centralityを計算できますか?
Brandesアルゴリズムによる正確な計算はO(VE)であり、遅すぎる可能性があります。NetworkX(kパラメータ付きbetweenness_centrality)またはgraph-toolのようなグラフライブラリで利用可能なランダム化近似(例:k個のソースノードのサンプリング)を使用してください。これらは、近似されたスコアの信頼区間を提供します。