ノード影響度メトリック

グラフ理論とネットワーク分析において、ノード影響度指標は、グラフ内のすべてのノード(頂点とも呼ばれる)の影響度をランク付けまたは定量化する尺度です。これらは中心性指標に関連しています。応用分野としては、ソーシャル ネットワーク内の各人の影響度を測定すること、交通ネットワーク、インターネット、または都市ネットワークにおけるインフラストラクチャ ノードの役割を理解すること、および特定のノードの疾病動態への関与などがあります。

ノードの重要性を理解するための従来のアプローチは、中心性指標を介したものです。中心性指標は、最も影響力のあるノードを正確に識別するランキングを作成するように設計されています。しかし、2000 年代半ば以降、社会科学者やネットワーク物理学者は、ノードの影響を理解するための中心性指標の適切性に疑問を抱き始めました。中心性は最も影響力のあるノードを示すかもしれませんが、影響力がそれほど大きくない大多数のノードについてはあまり役に立ちません。

ボルガッティとエヴェレットの2006年のレビュー記事^[1]は 、中心性指標の精度がネットワークトポロジーに大きく依存することを示しました。この発見はそれ以来繰り返し観察されてきました。（例：^{[2] [3]}）。2012年に、バウアーと同僚は、中心性指標はノードをランク​​付けするだけで、ノード間の差異を定量化しないということを思い出させました。^[4] 2013年に、シキッチと同僚は、中心性指標が非ハブノードの力をかなり過小評価しているという強力な証拠を示しました。^[5] その理由は非常に明白です。中心性測定の精度はネットワークトポロジーに依存しますが、複雑なネットワークには異質なトポロジーがあります。したがって、非常に影響力のあるノードを識別するのに適した中心性測定は、ネットワークの残りの部分にはおそらく不適切です。^[3]

このことは、すべてのネットワークノードの影響を測定するために設計された新しい方法の開発に影響を与えました。これらの最も一般的なものは、ランダムウォークの多様性を使用して、特定の開始ノードからネットワークの残りの部分がどれだけアクセス可能であるかを測定するアクセス可能性^[6] と、ノードによって生成される感染力の期待値から導かれる期待力^[3]です。 これらの指標は両方とも、ネットワークの構造のみから意味のある形で計算できます。

アクセシビリティはランダムウォークの理論から派生したものです。これは、特定のノードから始まる自己回避ウォークの多様性を測定します。ネットワーク上のウォークは、隣接する頂点のシーケンスです。自己回避ウォークは、各頂点を最大で 1 回訪問します (リストします)。元の研究では、長さ 60 のシミュレーション ウォークを使用して、ブラジルの都市の都市道路のネットワークを特徴付けました。^[6] これは後に、伝達確率と特定の固定長のウォークの多様性の両方を制御する階層度の修正形式として形式化されました。^[7]

階層次数は、長さ のウォークを実行することによって開始ノードから到達可能なノードの数を測定します。固定ウォークタイプの場合、これらの各隣接ノードには（潜在的に異なる）確率 で到達します。このような確率のベクトルが与えられた場合、スケールでのノードのアクセス可能性は次のように定義されます 。${\displaystyle h}$${\displaystyle h}$${\displaystyle p_{j}^{(h)}}$${\displaystyle i}$${\displaystyle h}$

${\displaystyle \kappa _{i}^{(h)}=\exp \left(-\sum _{j}p_{j}^{(h)}\log p_{j}^{(h)}\right)}$

確率は均一確率ランダムウォークに基づくこともできるし、エッジの重みや明示的な（エッジごとの）伝達確率によってさらに調整することもできる。^[7]

アクセス可能性は都市ネットワークにおけるコミュニティ構造を明らかにすることが示されており、^[6]定義された期間内に訪問できるノードの数に対応し、^[7]大きな直径と低密度のネットワーク上の疫学的SIRモデルの拡散プロセスの結果を予測します。^[2]

期待される力は、疫学的な観点からノードの影響を測定します。これは、2 回の感染後にノードによって生成される 感染力の期待値です。

ノードの期待される力は 次のように与えられる 。${\displaystyle i}$

${\displaystyle \kappa_{i}=-\sum_{j=1}^{J}d_{j}\log(d_{j})}$

ここで、合計は、から始まる 2 つの送信から生じるすべての可能な送信クラスターの集合に対して取られます。つまり、ノードとその 2 つの隣接ノード、または、その隣接ノードの 1 つ (感染ノードと呼ばれる)、および感染ノードの隣接ノードです。には送信イベントのすべての可能な順序が含まれるため、異なる順序で感染した場合は、2 つのクラスターに同じノードが含まれる可能性があります。はクラスター の正規化されたクラスター次数、つまり、クラスター 内に 1 つのエンドポイントだけを持つエッジの数です。 ${\displaystyle J}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle J}$${\displaystyle d_{j}}$${\displaystyle j\in J}$${\displaystyle j}$

この定義は、列挙をエッジの方向によって制限することで、有向ネットワークに自然に拡張されます。同様に、重み付きネットワーク、または不均一な伝達確率を持つネットワークへの拡張は、クラスターが形成される確率を含めるように の正規化を調整することです。2つ以上の伝達を使用して集合 を定義することもできます。^[3]${\displaystyle J}$${\displaystyle d_{j}}$${\displaystyle J}$

予想される力は、シミュレーションと実証の両方において、広範囲のネットワークトポロジーにわたってSI、SIS、SIRの流行結果と強い相関関係にあることが示されています。^{[3] [8]} また、世界の空港のパンデミックの可能性を測定するために使用されており、^{[9]デジタル決済、 [10]} エコロジー、^[11] フィットネス、^[12]プロジェクト管理の文脈でも言及されています 。^[13]

他には、ネットワーク上で展開される特定のプロセスのダイナミクスを明示的にエンコードする測定基準が提案されています。 動的影響は、各ノードから始まる無限ウォークの割合であり、ウォークステップは、システムの線形ダイナミクスがヌルでない定常状態に収束することが予想されるようにスケーリングされます。^[14]影響は、増加するウォークの長さにわたって、ウォークの終了ノードへの伝達確率と、終了ノードが以前に短いウォークによって訪問されていない確率を合計します。^[4] 両方の尺度は、エンコードする動的システムの結果を適切に予測しますが、いずれの場合も、著者は、1つのダイナミクスの結果が他のダイナミクスに変換されないことを認めています。