近接中心性

連結グラフにおいて、ノードの近接中心性（または近接度）は、ネットワークにおける中心性の尺度であり、そのノードとグラフ内の他のすべてのノードとの間の最短経路の長さの合計の逆数として計算されます。したがって、ノードの中心性が高いほど、他のすべてのノードとの距離が近くなります。

近さはバベラス（1950）によって遠さの逆数として定義された[ ^{1 ] [ 2 ] 。}すなわち、

${\displaystyle C_{B}(x)={\frac {1}{\sum _{y}d(y,x)}},}$

どこ${\displaystyle d(y,x)}$は頂点間の距離（最短経路の長さ）です。${\displaystyle x}$そして${\displaystyle y}$この正規化されていない近接性は、ステータスと呼ばれることもあります。^{[ 3 ] [ 4 ] [ 5 ]}近接中心性について話す場合、通常は最短経路の合計ではなく、最短経路の平均長を表す正規化された形式が用いられます。これは一般的に、前述の式に次の式を掛けたものです。${\displaystyle N-1}$、 どこ${\displaystyle N}$グラフ内のノード数は次のようになります。

${\displaystyle C(x)={\frac {N-1}{\sum _{y}d(y,x)}}.}$

近接度の正規化は、異なるサイズのグラフにおけるノードの比較を簡素化する。大規模なグラフの場合、正規化におけるマイナス1は意味をなさなくなり、しばしば省略される。

最も古い中心性指標の一つである近接性は、入門書^{[ 6 ] [ 7 ] [ 8 ]}や、異なる中心性指標を比較する論文[9][10][11][12]におけるネットワーク中心性指標の一般的な議論^{でしばしば取り上げられます。多くの中心性指標によって得られる値は、高い相関関係を示すことがあります[ 9 ] [ 13 ] [ 11 ] 。特に、}近接^{性と次数は、多くのネットワークにおいて}近似的な関係で結びついていることが 示されています^{[ 12 ]。}

${\displaystyle {\frac {1}{C(x)}}\approx {\frac {-1}{\ln(z-1)}}\ln(k_{x})+\beta }$

どこ${\textstyle k_{x}}$頂点の次数${\displaystyle x}$その間${\displaystyle z}$および β は、この式に近接度と次数を当てはめることで得られるパラメータです。zパラメータは分岐係数を表し、この関係を示す際にネットワークを近似するために使用される最短経路ツリーのノードの平均次数 (ルートノードと葉を除く)です。^{[ 12 ]}これは決して正確な関係ではありませんが、多くの現実世界のネットワークで見られる傾向を捉えています。

近接性は、ネットワーク科学で使用される他の長さスケールと関連しています。例えば、平均最短経路長などです。${\textstyle \langle \ell \rangle }$ネットワーク内の頂点間の平均距離は、単純に近接度の逆数の平均です。

${\displaystyle \langle \ell \rangle ={\frac {1}{N}}\sum _{x}{\frac {1}{C(x)}}={\frac {1}{N(N-1)}}\sum _{x}\sum _{y}d(y,x)}$。

無向グラフでは、他のすべてのノードとの距離を計算することは無意味ですが、有向グラフでは全く異なる結果が生じる可能性があります（例えば、ウェブサイトは発信リンクからの近接中心性は高いものの、受信リンクからの近接中心性は低い場合があります）。

近接性はさまざまな文脈で使用されています。書誌計量学では、近接性は、さまざまな分野で研究者がジャーナルや参考文献を選択する方法を調べるために使用されてきました^{[ 14 ]。}また、著者が分野に与える影響やソーシャルキャピタルを測定するためにも使用されています^{[ 15 ]}。顧客データから潜在的なリードを選択するために使用された場合、近接性は成功率の大幅な向上につながることがわかっています^{[ 16 ]} 。航空輸送ネットワークにおける都市の近接性は、地域総生産などの社会経済指標と高い相関があることが示されています^{[ 17 ]}。近接性は生物学的ネットワークにも適用されており^{[ 5 ]}、たとえば、上位2%の遺伝子の中にグローバルレギュレーターの50%以上を特定するために使用されたり^{[ 18 ]}、タンパク質相互作用ネットワークでは必須遺伝子が非必須遺伝子よりも高い近接性を持つことがわかっています。^{[ 19 ]}代謝ネットワークでは、ノードの近接性によって最も重要な代謝物を特定できる。^{[ 20 ]}

グラフが強く連結されていない場合、Beauchampは1965年に距離の逆数の合計の代わりに距離の逆数の合計を使用するというアイデアを導入しました^{[ 21 ]。}${\displaystyle 1/\infty =0}$:

${\displaystyle H(x)=\sum _{y\neq x}{\frac {n-1}{d(y,x)}}.}$

ボーチャンプの修正は、マルキオリとラトーラ（2000）^{[ 22 ]}が提唱した（ずっと後の）一般原則、すなわち無限距離を持つグラフでは調和平均が算術平均よりも優れた挙動を示すという原則に基づいている。実際、バベラスの近接性は距離の算術平均の非正規化逆数として記述できるのに対し、ボーチャンプの中心性は距離の調和平均の逆数である。

このアイデアは文献で何度か再浮上しているが、多くの場合、正規化係数なしで提示されている。${\displaystyle n-1}$: Dekker (2005) ^{[ 23 ]}による値付き中心性という名前で無向グラフの場合、調和中心性は、Rochat (2009) によって提唱されました。^{[ 24 ]} Garg (2009) によって公理化され^{[ 25 ]}、後に Opsahl (2010) によって再び提案されました。^{[ 26 ]}一般的な有向グラフについては、Boldi と Vigna (2014) によって研究されました。^{[ 27 ]}この考え方は、Harris (1954) で提案された市場ポテンシャルとも非常によく似ており^{[ 28 ]} 、現在では市場アクセスという用語で呼ばれることが多いです。^{[ 29 ]}

Dangalchev (2006) ^{[ 30 ]}は、ネットワークの脆弱性に関する研究の中で、無向グラフに対して異なる定義を提案している。

${\displaystyle D(x)=\sum _{y\neq x}{\frac {1}{2^{d(y,x)}}}.}$

この定義は非連結グラフに効果的に適用でき、グラフ演算のための便利な数式を作成できます。例えば：

グラフの場合${\displaystyle G_{1}+G_{2}}$リンクノードによって作成されます${\displaystyle p}$グラフの${\displaystyle G_{1}}$ノードへ${\displaystyle q}$グラフの${\displaystyle G_{2}}$すると、総合的な近さは次のようになります。

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+(1+D(p))(1+D(q));}$

グラフの場合${\displaystyle G_{1}+G_{2}}$ノードを折りたたむことによって作成されます${\displaystyle p}$グラフの${\displaystyle G_{1}}$ノード${\displaystyle q}$グラフの${\displaystyle G_{2}}$1 つのノードに統合すると、近接度は次のようになります。^{[ 31 ]}

${\displaystyle D(G_{1}+G_{2})=D(G_{1})+D(G_{2})+2D(p)D(q).}$

グラフの場合${\displaystyle S(G)}$グラフの影グラフです${\displaystyle G}$これには${\displaystyle n}$ノード、次に${\displaystyle S(G)}$近さは： ^{[ 32 ]}

${\displaystyle D(S(G))=4D(G)+{\frac {n}{2}}.}$

グラフの場合${\displaystyle T(G)}$グラフの棘グラフです${\displaystyle G}$これには${\displaystyle n}$ノード、次に${\displaystyle T(G)}$近さは：^{[ 33 ]}

${\displaystyle D(T(G))={\frac {9}{4}}D(G)+n.}$

この定義の自然な一般化は次のとおりです。^{[ 34 ]}

${\displaystyle D(x)=\sum _{y\neq x}\ {\alpha ^{d(y,x)}},}$

どこ${\displaystyle \alpha }$（0,1）に属する。${\displaystyle \alpha }$が0から1に増加すると、一般化された近接性は、局所的な特性（次数）からグローバルな特性（接続されているノードの数）に変わります。

StephensonとZelen（1989）の情報中心性は、別の近接度尺度であり、頂点xへの抵抗距離の調和平均を計算します。xが他の頂点に接続する抵抗の小さいパスを多数持っている場合、この値は小さくなります。^{[ 35 ]}

近接中心性の古典的な定義では、情報の拡散は最短経路の使用によってモデル化されます。このモデルは、すべてのタイプの通信シナリオに対して最も現実的ではない可能性があります。そのため、 Noh と Rieger (2004) によって導入されたランダムウォーク近接中心性など、近接性を測定するための関連する定義が議論されてきました。これは、ランダムウォークメッセージがグラフ内の他の場所から頂点に到達する速度を測定します。^{[ 36 ]} Tran と Kwon (2014) ^{[ 37 ]}の階層的近接性は、強く接続されていないグラフにおける近接性の制限に別の方法で対処するための拡張された近接中心性です。階層的近接性は、与えられたノードによって影響を受ける可能性のある他のノードの範囲に関する情報を明示的に含みます。

• 中心性
• ランダムウォーク近接中心性
• 媒介中心性