グラフのeccentricity(離心性)と半径(radius)と直径(diameter)と中心(center)とその他
- 参考サイト
- 説明
- Connected graphを考える
- Eccentricityは個々のノードに定義される
- あるノード
について、
以外のすべてのノード
について、グラフ上の最短距離を求める(グラフ上の最短距離は、エッジに長さが与えられていなければ、エッジ数に同じ)
- 今、このようにして得られたすべての最短距離のうち、最長のものをこのノードのeccentricityと定義する
- あるノード
- Center
- Eccentricityがグラフ中最小のノードをCenter(中心)と呼ぶ。定義からわかるとおり、1つとは限らない
- 半径(radius)と直径はグラフについて定義される
- 今、すべてのノードのeccentricityについて、その最小値を半径、その最大値を直径とする
- その他の指標
も
もグラフ理論上の呼称を見つけられないが・・・
- グラフがcenterを中心に「まとまりがよいか=centerから多方向にひろがっているか」の指標とみなしてよいような定義になっている
はその絶対値、
はその標準化した値(0-1をとる)
- 定義はこう!!!まちがっているかも知れない!!!ので要注意。定義から意訳してみている
- グラフのcenterであるノード
のそれぞれについてある条件を満たす連結ノードの集合を求めて、そのノードの数を数える。その数が
である
は
の最大値
を数えるための連結ノードの満たす条件とは
- 条件を満たすノードとノード
自身とをあわせたノードをひとつのノードとみなして作られたグラフにおいて、新たにできたノードは新しく作ったグラフのcenterであり、このグラフの半径がもとのグラフの半径より1以上短くなっていること
- 条件を満たすノードとノード
- グラフのcenterであるノード
- 上記で求めた
について
- 上記で求めた
- 定義
- 半径が
であるようなグラフを想定する
- それぞれのcenter i について要素数が最少であるノードの集合
をとる。この
はノード i のneighborsであるノードからなり、次の条件を満たす
for all
- このようにして定義された
のうち、最大のものを
とする
- 半径が
- Eccentricityが半径となっているようなノードをこのグラフの中心(center)と呼ぶ
- 非連結グラフ(Non-connected graph)の場合には、互いに非連結のグラフ上のノード間の距離を無限大と定義すると、上記のeccentricity,radius,diameterの定義はそのまま使用できる