中心性指標

ここ半年で行ってきたことについて少しずつまとめていく。

まずは中心性計算に関してまとめる。最短路を用いた中心性計算のうち、最短距離による closeness, graph と最短路数による stress, betweenness が有名である。特に betweenness は Web, Communication, Citation, Patents などの座標を持たないネットワークに頻繁に用いられている。

それではそれぞれの特徴をまとめていく。

d(s,t) ... s-t 間の最短路長
sigma_{s,t}(v) ... s-t 間の最短路のうち、vを通る数

1. closeness ... 他点への最短距離の和を指標とする
2. graph ... 他点への最短距離の最大値を指標とする

→ 他点への最短距離に着目している。以下の例のような平面グラフでは非常に分かりやすい結果が得られるものの、座標を持たないグラフに対しての意味付けは難しいかもしれない。graph の最大値は直径(diameter) と一致する。


3. stress ... 最短路上に含まれる回数を指標とする。
4. betweenness ... 最短路上に含まれる割合を指標とする。normalize された stress という解釈も可能

→ 最短路上に含まれる回数や割合を指標としているため、この指標が高い点は何度も最短路に使用される重要な点であることを示している。道路ネットワークであれば渋滞の起こりやすさ等に、ソーシャルネットワークであれば友人関係の活発さ等に関係性があるといえるだろう。※ stress は betweenness に対して最短路数の絶対数を考慮しているため、格子グラフなどの最短路数が非常に多いグラフではオーバーフローしてしまう可能性が高い。


図は、 att532.tsp の近い点間に枝を引いて生成した点数 n=532, 枝数 m=3724 のグラフの中心性の結果である。