加重グラフの密集中心

グラフの頂点uのCloseness
Centralityを決定するには、グラフ内のuと他のすべての頂点との間の最短経路を計算します。中心性は、次に与えられる:

$ C(u)= frac {1} { sum_v {d(u、v)}} $ $ d(u、v)$は$ u $と$ v
$の間の距離(=辺の数)です。

私は重み付けされていないグラフについてはこれを理解していますが、重み付けされたグラフでは理解できません。最短経路を決定するときは、重みを考慮する必要があります。したがって、3つのエッジ(重み1,1、および2)を含む$
u $と$ v
$の間に経路が存在する可能性があります。しかしながら、重み10を有する1つのエッジのみからなる第2の経路も存在し得る。もちろん、最短経路は、4が10未満である3つのエッジを有する経路である。しかし、近さの中心性については、この最短経路上の辺の数は3である。これは直感的ではないように見えます。なぜなら、単一のエッジのみを持つ別のパスが存在するからです。

だから私の質問は:これはちょうど方法か、それはエッジの数ではなく、重みに基づいた実際の距離であるように、加重グラフの$
d(u、v)$の定義を変更しなければならないか? ?

ベストアンサー

残念ながら、私は紙やその他の証明書を提供することはできませんが、私は近くの中心性で多く働く同僚と話をしました。彼は重み付けされたグラフのためにあなたは
“本当の”経路長のみを使用します。距離の最短経路上の重みの合計。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です