Skip to content
検索結果に戻る

加重近接中心性

提唱者
Opsahl, T.; Agneessens, F.; Skvoretz, J.
年
2010
種類
Centrality measure (network analysis)
系統
Network science

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

加重近接中心性(Weighted closeness centrality)は、エッジが持つ数値的な重み――例えば、頻度、強度、あるいはコスト――を最短経路距離に組み込むことによって、エッジが重みを持たない(unweighted)ネットワークにおける従来の近接性指標を拡張したものである。他のノードへ、強い、あるいは効率的な接続を通じて迅速に到達できるノードは、より高いスコアを獲得し、これは二値的な(binary)指標よりも情報伝播の可能性を示す、より豊かな指標となる。

手法の背後にある直感

重みなしネットワークでは、近接中心性は、あるノードが他の全てのノードに到達するために何ステップ必要かを問う。重み付きネットワークでは、その論理は、結びつきが強いか弱いかを無視してしまう。加重近接性は、各エッジの重みを容量または逆距離として扱う。より強い結びつきは、より短いホップとしてカウントされる。高いスコアを持つノードは、単にトポロジカルな意味でよく接続されているだけでなく、高容量または低コストの経路を通じて、実際に他者に近いのである。Opsahlら(2010)は、分析者が経路長またはエッジ重みのいずれかを強調できるようにするチューニングパラメータαを導入し、重みなし近接性と純粋に重みベースの近接性との間を橋渡しした。

歴史学

古典的な近接中心性はSabidussi(1966)によって形式化され、後にFreeman(1978)によって普及した。加重ネットワークへの拡張は、チューニングパラメータαを用いた次数中心性と最短経路中心性の両方を一般化した2010年のSocial Networks誌における論文で、Opsahl、Agneessens、Skvoretzによって体系的に開発された。彼らのフレームワークは、ソーシャルネットワーク分析における加重中心性の標準的な参照となり、igraphやNetworkXを含む広く使用されているパッケージに実装されている。

使うべき場面

エッジの重み(共同作業の頻度、コミュニケーションの量、貨幣の流れ、輸送能力)が理論的に意味を持ち、どのノードが中心的と見なされるべきかに影響を与えるべき場合に、加重近接中心性を使用する。これは、ソーシャルネットワーク、貿易ネットワーク、輸送システム、共著グラフ、および到達効率が結びつきの強度に依存するあらゆる設定に適している。重みを無視すると中心性ランキングが歪む可能性がある場合は、重みなし近接性よりもこちらを優先する。重みが信頼できない、任意にスケーリングされている、あるいは存在しない場合。切断されたグラフで到達不能なペアを適切に処理しない場合。あるいは、研究課題が純粋な構造的トポロジではなく、フロー効率に関係する場合に使用しない。

限界と注意点

  • 完全で信頼性の高い重みデータが必要。欠損またはノイズの多いエッジ重みは、中心性スコアに直接伝播する。
  • 切断されたネットワークは特別な処理が必要(例:到達不能なペアを除外する、または調和近接性を使用する)。
  • αパラメータの選択には理論的な正当化が必要。任意のデフォルト値はランキングを歪める可能性がある。
  • 大規模疎ネットワークでは、次数中心性よりも計算コストが高い。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • エッジの重みを組み込み、強い、あるいは効率的な接続がノードの中心性スコアを適切に向上させるようにする。
  • αチューニングパラメータは、二値的な近接性と完全に重みベースの近接性との間に連続的な橋渡しを提供する。
  • 近接性の直感的な解釈を保持する:ノードが他者にどれだけ迅速に到達できるか、あるいは他者から到達されるか。
  • 重みなし近接性と直接比較可能であり、管理された感度分析を可能にする。
  • 入次数中心性(in-closeness)と出次数中心性(out-closeness)への分解と組み合わせた場合に、有向加重ネットワークに適している。

応用

  • 共著頻度に基づく科学共同作業ネットワークにおける主要な仲介者(broker)の特定。
  • 加重輸送または貿易ネットワークにおける到達効率による空港または物流ハブのランキング。
  • 加重コミュニケーションまたはソーシャルメディアネットワークにおける影響力のある拡散者(spreader)の検出。
  • 加重組織または知識共有ネットワークにおける情報拡散ポテンシャルの評価。
  • 異なるα値での中心性ランキングの比較による、結果の頑健性の評価。
  • 加重媒介中心性(weighted betweenness centrality)を補完し、効率的な到達可能性とフロー制御を区別する。

使い方

使い方

1

エッジの重みは距離に変換される。共同作業や頻度のネットワークでは、重みwは逆数(距離 = 1/w)にされ、より強い結びつきがより短い距離をもたらすようにする。コストや遅延のネットワークでは、重みは既に距離となっている。その後、Dijkstraのアルゴリズムが、ノードのペア間の最小加重距離d^w(i,j)を見つける。

数式
d^w(i,j) = \min_{\text{paths}} \sum_{e \in \text{path}} w_e^{-1}
2

各ノードiについて、他の到達可能なn-1個の全てのノードへの加重距離が合計される。ネットワークの大部分に対して弱く接続されている、あるいは切断されているノードは、大きな合計値を蓄積し、それらの中心性スコアを低下させる。

3

ノードiの加重近接性は、他の全てのノードへの加重距離の合計で割った(n-1)であり、これはホップ数ではなくd^wで置き換えられた点を除けば、古典的な近接性と同じ代数形式である。これにより、スコアは区間(0, 1]に正規化され、異なるサイズのネットワークを比較可能に保つことができる。

数式
C^w(i) = \frac{n-1}{\sum_{j \neq i} d^w(i,j)}
4

Opsahlら(2010)は、純粋なトポロジカル距離(α = 0、重みなし近接性に相当)と純粋な重み情報(α = 1)をブレンドするパラメータα(0から1)を導入した。中間値は、研究者が経路構造に対する結びつきの強さの重要度を制御することを可能にし、この尺度を多様な経験的設定に適応させる。

数式
C^{w,\alpha}(i) = \frac{n-1}{\sum_{j \neq i} d^{w,\alpha}(i,j)}

よくある落とし穴

  • 頻度重みなどを逆数に変換する適切な重みから距離への変換を確認せずに、生のカウントを重みとして使用すること。
  • 到達不能なペアを調整せずに切断されたグラフに尺度を適用すること。これは孤立したノードの距離合計を過大評価する。
  • 中心性ランキングを、αパラメータに対する感度をテストせずに安定していると見なすこと。
  • 加重近接性と媒介中心性(betweenness centrality)との混同。近接性は到達効率を反映し、フロー制御を反映しない。
  • 異なるサイズのネットワーク間でノードを比較する際に、正規化を無視すること。

よくある質問

αパラメータはどのように選択すべきか?

α = 0 は重みなし近接性(トポロジのみ)を回復し、α = 1 は重みを支配的にする。一般的なアプローチは、α = 0, 0.5, 1 でランキングを計算し、感度を報告することである。理論が結びつきの強さが主要なメカニズムであることを示唆している場合、α = 1 は正当化可能であり、トポロジがより重要である場合は、α = 0 または 0.5 を使用する。

どのような重みから距離への変換を使用すべきか?

頻度、強度、または容量の重み(値が高いほど強い)の場合、重みを逆数にする:距離 = 1/w。コスト、遅延、または抵抗の重み(値が高いほど弱い)の場合、重みを直接距離として使用する。これらの規約を不注意に混合すると、中心性ランキングが逆転する。

切断されたコンポーネントをどのように処理するか?

標準的なアプローチは、合計を到達可能なノードに制限し、(n - 1)ではなく(n_reachable - 1)で正規化すること、または到達不能なペアを自然に処理する調和近接性中心性(harmonic closeness centrality)を使用して距離の逆数を合計することである。

加重近接性は重みなし近接性よりも優れているか?

重みが実質的な意味を持つ場合(例:接触頻度、貿易量)、加重近接性は到達効率のより正確な像を提供する。重みが信頼できない場合、または重みとトポロジがほとんど相関しない場合、追加の複雑さは推論を改善しない可能性がある。

これは加重媒介中心性とどう違うか?

加重近接性は、ノードが強い経路を通じて他者にどれだけ効率的に到達できるかを測定する。加重媒介中心性は、ノードが他のペア間の最短経路上にどれだけ頻繁に位置するかを測定する。ノードは、重要な橋(高い媒介中心性)でなくても近い(高い近接性)場合があり、その逆も同様である。

関連する手法

参考文献

  1. Opsahl, T., Agneessens, F. & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.

    DOI 文献を開く
    コピーしました。
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    DOI 文献を開く
    コピーしました。