近接中心性
- 提唱者
- Bavelas, A.; formalized by Freeman, L. C.
- 年
- 1950 (formalized 1979)
- 種類
- Node-level centrality index
- 系統
- Network science
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
近接中心性は、ネットワーク内の他のすべてのノードへの平均最短経路距離の逆数を計算することにより、ノードが他のすべてのノードにどれだけ迅速に到達できるかを測定します。1950年にBavelasによって最初に説明され、1979年にFreemanによって正式に統一されたこの指標は、単に多くの直接的な接触を持つノードだけでなく、グラフ全体に情報やリソースを効率的に広めることができるノードを特定します。
手法の背後にある直感
ノードにメッセージをドロップし、それがネットワークの隅々にどれだけ速く到達するかを観察することを想像してください。近接性が高いノードは接続のウェブの中心近くに位置します。つまり、他の誰かに到達するために平均して少ないホップで済みます。周辺ノードは、多くの隣接ノードを持っていても、ネットワークの大部分から遠い場合があります。近接性は、このネットワークの地理という考え方を捉えています。平均距離が短いほど近接性が高く、近接性が高いほど効率的なブロードキャストまたはグラフを流れる情報への迅速なアクセスが可能になります。
歴史学
アレックス・バベラスは、1950年にMITでグループ問題解決の効率性を研究していた際に、最短経路に基づいたコミュニケーション中心性の概念を導入しました。リントン・フリーマンは、1979年の画期的なソーシャルネットワーク誌で、次数中心性や媒介中心性と並んで、近接中心性を3つの標準的なノードレベル中心性指標の1つとして正式に定義し、現代のソーシャルネットワーク分析の基礎となった統一的な数学的フレームワークを提供しました。
使うべき場面
情報、リソースを最も効率的にブロードキャストしたり、最小限の中継でネットワークの残りにアクセスしたりできるノードを特定したい場合に使用します。例えば、最適な拡散シード、影響力のあるコミュニケーション担当者、またはトランジットハブの特定などです。あらゆるサイズの連結またはほぼ連結のグラフに適しています。ネットワークが高度に断片化している(多くの非連結コンポーネントがある)場合は、主要な中心性指標として使用しないでください。生の近接スコアがゼロに近くなり無意味になるためです。Wasserman-Faust正規化を適用するか、コンポーネントを個別に分析してください。近接性と次数中心性を混同しないでください。ノードは多くの直接的なつながりを持っていても、グローバルな到達範囲では周辺的である可能性があります。
限界と注意点
- グラフの接続性に敏感です。非連結ネットワークでは、生の尺度がつぶれてしまい、正規化の調整が必要になります。
- すべての最短経路を同等に重要とみなします。トラフィックの量や特定の経路が実際に使用される確率を考慮しません。
- 近似アルゴリズムなしでは全ペア最短経路計算のスケーリングが悪いため、非常に大規模なグラフ(数百万ノード)では計算コストが高くなります。
- 多くの弱い結びつきに近いノードと、少数の強力で戦略的に重要な結びつきに近いノードを区別しません。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- ローカルな接続性だけでなく、グローバルな到達可能性を捉えるため、情報フローと拡散の研究に理想的です。
- 正規化されたスコア(0から1)により、異なるサイズのネットワーク間で比較が可能になります。
- 社会学、疫学、コンピュータサイエンスで数十年にわたる検証を経た、確立された理論的基盤。
- 次数中心性や媒介中心性と補完し合い、ノードの役割についてより豊かな視点を提供します。
- ほとんどの実証的ネットワークにおいて、BFS(無重量)またはDijkstra(重み付き)で効率的に計算可能。
応用
- 組織的および社会的なネットワークにおける主要な情報仲介者またはオピニオンリーダーの特定。
- 情報または疾患の拡散速度を最大化するための最適なシードノードの選択。
- 交通ネットワークにおける全体的なアクセス可能性によるトランジット駅または交差点のランキング。
- 生物学的相互作用ネットワークにおける影響力のあるタンパク質または遺伝子の特定。
- 技術普及研究における影響力のある早期採用者の検出。
- 疫病の拡散を遅らせるための公衆衛生接触ネットワークにおける介入ターゲットの優先順位付け。
使い方
使い方
ノードをアクター(人々、組織、ウェブページ、遺伝子など)とし、エッジを関係または相互作用としてエンコードするグラフとしてネットワークを表します。グラフは無向または有向の場合があり、エッジは無重量(各ホップは1)、または重み付き(コストはエッジの重みに等しく、距離または逆強度として解釈される)の場合があります。
各ノードvについて、無重量グラフの場合は幅優先探索、重み付きグラフの場合はダイクストラ法を使用して、到達可能な他のすべてのノードuへの最短経路距離d(u, v)を計算します。有向グラフの場合、エッジの方向に従うパスのみが有効であるため、流入近接性と流出近接性は異なる場合があります。
数式
d(u,v) = \text{shortest path length between nodes } u \text{ and } vvから他のすべてのノードへのすべての最短経路距離を合計して、vの遠さ(farness)を取得します。遠さが小さいほど、vはネットワークの残りの部分に平均して近いことを意味します。遠サが大きいほど、周辺性が高いことを示します。
数式
\text{farness}(v) = \sum_{u \neq v} d(u, v)平均最短経路距離の逆数を取ります。C(v) = (n-1) / sum of d(u,v)。(n-1)を掛けることで、(0, 1]の正規化されたスコアが得られ、異なるサイズのネットワークのノードを比較できます。値が高いほど、より中央的で到達可能な位置を示します。
数式
C(v) = \frac{n-1}{\sum_{u \neq v} d(u, v)}非連結グラフでは、ノードは他のすべてに到達できないため、到達不可能なペアの生の近接性はゼロまたは未定義になります。Wasserman-Faust正規化は、到達可能なノードのみを合計し、到達可能なグラフの割合で再スケーリングすることにより、非連結グラフに近接性を拡張し、孤立したコンポーネントの偽のゼロに近いスコアを防ぎます。
よくある落とし穴
- Wasserman-Faust正規化を適用せずに、非連結コンポーネントを持つネットワークで生の近接性を報告すること。これにより、誤解を招くゼロに近いスコアが生成されます。
- 近接中心性と次数中心性を交換可能とみなすこと。次数が高いからといって近接性が高いとは限らず、その逆も同様です。
- エッジが有向であるかどうかを無視すること。有向ネットワークでは、近接性は流入方向と流出方向で個別に計算する必要があります。
- エッジの重みが意味のある距離をエンコードしている重み付きネットワークに無重量の近接性を適用すること。関係の強さに関する情報を失います。
- nを考慮せずに、異なるサイズのネットワーク間で生の(正規化されていない)近接スコアを比較すること。
よくある質問
近接中心性は次数中心性とどのように異なりますか?
次数中心性は直接の隣接ノードのみをカウントするため、それらの接続がすべてネットワークの一方の隅に集中していても、ノードは多くの接続があれば高いスコアを獲得できます。近接中心性はグラフ内のすべてのノードへの最短経路を考慮するため、グローバルな到達可能性を重視します。周辺的なクリップハブは高い次数を持つかもしれませんが、近接性は低い可能性があります。
ネットワークに非連結コンポーネントがある場合はどうすればよいですか?
Wasserman-Faust(1994)の調和正規化または到達可能性調整正規化を適用します。これは、到達可能なペアのみを合計し、到達可能なネットワークの割合で再スケーリングします。あるいは、最大の連結コンポーネントを個別に分析するか、調和中心性(逆距離の合計)を使用します。これは、到達不可能なペアにゼロの寄与を割り当てることで、自然に処理します。
近接中心性は重み付きネットワークで機能しますか?
はい。BFSを、エッジの重みを距離として使用するダイクストラ法(または、重みが大きいほど近い場合は、強度/類似性重みの逆数)に置き換えます。結果として得られる重み付き近接性は、トポロジーと接続の品質の両方を反映します。
正規化された近接スコアをどのように解釈しますか?
1に近いスコアは、ノードが平均して約1ホップで他のすべてのノードに到達できることを意味します。つまり、ネットワークの中心に位置します。0に近いスコアは、ノードが非常に周辺的であることを意味します。通常、約0.6を超えるスコアは、ほとんどの実証的ネットワークで真に中心的な位置を示します。
近接中心性は有向ネットワークに適していますか?
はい、ただし各方向で個別に計算してください。流入近接性は、他のノードがフォーカルノードにどれだけ容易に到達できるか(ノードの名声や受容性の研究に役立ちます)を測定し、流出近接性は、フォーカルノードが他のノードにどれだけ容易に到達できるか(ブロードキャスト能力の研究に役立ちます)を測定します。