第 5 章 グラフ理論
5.3 グラフ理論より計算される指標について
図5.4 スモールワールドモデルで構築されるグラフ例とそれらのネットワークにお けるクラスター係数C(p)と平均経路長L(p)の特徴(参考文献[36]より改変引用)
して最短経路長の算出する．weighted graphにおける最短経路長𝐺𝐺𝑖𝑖𝑖𝑖𝑤𝑤は，
𝐺𝐺
𝑖𝑖𝑖𝑖𝑤𝑤= ∑
𝑟𝑟𝑤𝑤∈𝐺𝐺𝑖𝑖↔𝑗𝑗𝑤𝑤𝑓𝑓(𝑤𝑤
𝑢𝑢𝑢𝑢)
(5.2)と定義される39)40)．𝑓𝑓は重み付きグラフを意味し，𝐺𝐺𝑖𝑖↔𝑖𝑖𝑤𝑤 はノードiからノードjに至るま での最短経路である．
図5.5 binary graphとweighted graphにおける最短経路長の算出
5.3.2 平均経路長(Characteristic Path Lengths)について
Characteristic Path Lengthsは固有パス長や平均経路長とも呼ばれ，すべての2組のノー ド間の最短経路長の平均で表される39)40)．平均経路長を𝐿𝐿𝑝𝑝とすると，
𝐿𝐿
𝑝𝑝=
𝑛𝑛1∑
𝑖𝑖∈𝑁𝑁𝐿𝐿
𝑖𝑖=
𝑛𝑛1∑
∑𝑗𝑗∈𝑁𝑁,𝑖𝑖≠𝑗𝑗𝑑𝑑𝑖𝑖𝑗𝑗𝑖𝑖∈𝑁𝑁 𝑛𝑛−1
(5.3)
で定義される．このとき，𝑠𝑠はノード数，𝐿𝐿𝑖𝑖はノードiと他のノード全てとの間の平均距 離である．つまり，平均経路長は各経路長の総和をノードの全ての組み合わせの数で割 ったものに等しくなる．平均経路長の算出の仕方を示したものを図5.5に示す．
また，weighted graphにおける平均経路長は次式(5.4)で求めることができる39)40)．
𝐿𝐿
𝑤𝑤𝑝𝑝=
𝑛𝑛1∑
∑𝑗𝑗∈𝑁𝑁,𝑖𝑖≠𝑗𝑗𝑑𝑑𝑖𝑖𝑗𝑗𝑤𝑤𝑖𝑖∈𝑁𝑁 𝑛𝑛−1
(5.4)
40
図5.6 平均経路長(Characteristic Path Lengths)の算出例
5.3.3 クラスター係数(Clustering Coefficient)について
クラスター係数は各ノードに対して定義され，ノードiの次数𝑘𝑘𝑖𝑖とノードiとその周り のノードで構成される三角の総数𝑐𝑐𝑖𝑖で表現される．次数(degree)とはそのノード i に接続 されているエッジの数であり，ノードiの次数𝑘𝑘𝑖𝑖は隣接行列のi行目の合計値
𝑘𝑘
𝑖𝑖= ∑
𝑖𝑖∈𝑁𝑁𝑎𝑎
𝑖𝑖𝑖𝑖 (5.5) に対応する．また，ノードiとその周りのノードで構成される三角の総数𝑐𝑐𝑖𝑖，つまり，ノ ードiの隣に位置するノードがお互いに接続している割合は，𝑐𝑐
𝑖𝑖=
12∑
𝑖𝑖,ℎ∈𝑁𝑁𝑎𝑎
𝑖𝑖𝑖𝑖𝑎𝑎
𝑖𝑖ℎ𝑎𝑎
𝑖𝑖ℎ (5.6) で定義される39)40)．i番目のノードのクラスター係数を𝐶𝐶𝑖𝑖とすると，ネットワーク全体のクラスター係数𝐶𝐶 は，式(5.5)と式(5.6)より
41
𝐶𝐶 =
1𝑛𝑛∑
𝑖𝑖∈𝑁𝑁𝐶𝐶
𝑖𝑖=
1𝑛𝑛∑
𝑝𝑝 2𝑑𝑑𝑖𝑖𝑖𝑖(𝑝𝑝𝑖𝑖−1)
𝑖𝑖∈𝑁𝑁 (5.7)
となる．ここで，ノードiの周りの三角の総数𝑐𝑐𝑖𝑖は，次数が𝑘𝑘𝑖𝑖のとき，最大𝑘𝑘𝑖𝑖(𝑘𝑘𝑖𝑖− 1)/2と なるため，その最大値で正規化してネットワーク全体で平均をとり，𝐶𝐶を算出している．
図5.7 ノードiにおけるクラスター係数の算出例
weighted graphの場合，次数はノードiに接続されているエッジの数で定義されている ため変わらず，ノードiとその周りのノードで構成される三角の総数𝑐𝑐𝑖𝑖は次式(5.8)で定義 される33)．
𝑐𝑐
𝑖𝑖𝑤𝑤=
12∑
𝑖𝑖,ℎ∈𝑁𝑁(𝑤𝑤
𝑖𝑖𝑖𝑖𝑤𝑤
𝑖𝑖ℎ𝑤𝑤
𝑖𝑖ℎ)
1/3(5.8) つまり，weighted graphの場合のクラスター係数は，
𝐶𝐶
𝑤𝑤=
1𝑛𝑛∑
𝑖𝑖∈𝑁𝑁𝐶𝐶
𝑖𝑖𝑤𝑤=
𝑛𝑛1∑
𝑝𝑝 2𝑑𝑑𝑖𝑖𝑤𝑤𝑖𝑖(𝑝𝑝𝑖𝑖−1)
𝑖𝑖∈𝑁𝑁 (5.9)
と表現することができる．
5.3.4 Global Efficiencyについて
Global Efficiency(𝐸𝐸𝑔𝑔𝑔𝑔𝑔𝑔𝑏𝑏𝑟𝑟𝑔𝑔)はノードi, j間の効率性𝜀𝜀𝑖𝑖𝑖𝑖の平均値で定義され，これはどの 程度効率的に情報のやり取りをしているかを表現している．効率性𝜀𝜀𝑖𝑖𝑖𝑖は最短経路長𝐺𝐺𝑖𝑖𝑖𝑖に 反比例する．ここで，ノードiにおける効率性を𝐸𝐸𝑖𝑖とすると，Global Efficiencyは次式(5.10) で表すことができる39)40)．
𝐸𝐸
𝑔𝑔𝑔𝑔𝑔𝑔𝑏𝑏𝑟𝑟𝑔𝑔=
1𝑛𝑛∑
𝑖𝑖∈𝑁𝑁𝐸𝐸
𝑖𝑖=
𝑛𝑛1∑
𝑖𝑖,𝑖𝑖∈𝑁𝑁,𝑖𝑖≠𝑖𝑖𝑛𝑛−1𝜀𝜀𝑖𝑖𝑗𝑗=
𝑛𝑛(𝑛𝑛−1)1∑
𝑑𝑑1𝑖𝑖,𝑖𝑖∈𝑁𝑁,𝑖𝑖≠𝑖𝑖 𝑖𝑖𝑗𝑗
(5.10) また，weighted graphの場合は次式(5.11)で定義される．
𝐸𝐸
𝑔𝑔𝑔𝑔𝑔𝑔𝑏𝑏𝑟𝑟𝑔𝑔𝑤𝑤=
𝑛𝑛(𝑛𝑛−1)1∑
𝑑𝑑1𝑖𝑖𝑗𝑗𝑤𝑤
𝑖𝑖,𝑖𝑖∈𝑁𝑁,𝑖𝑖≠𝑖𝑖
(5.11) 42
5.3.5 Local Efficiencyについて
Local Efficiency(𝐸𝐸𝑔𝑔𝑔𝑔𝑐𝑐𝑟𝑟𝑔𝑔)は，ノードiに隣接するノードj, hのみで構成されたグラフ(サ ブグラフ)における効率性𝐸𝐸𝑔𝑔𝑔𝑔𝑐𝑐,𝑖𝑖の平均値で定義されている．また，ノードj, h間のサブグ ラフ内の効率性𝐸𝐸𝑔𝑔𝑔𝑔𝑐𝑐,𝑖𝑖は，そのサブグラフ内での最短経路長𝐺𝐺𝑖𝑖ℎ(𝑁𝑁𝑖𝑖)の逆数の平均値とノー ドj, hの次数で表現される．よって，Local Efficiency(𝐸𝐸𝑔𝑔𝑔𝑔𝑐𝑐𝑟𝑟𝑔𝑔)は次式(5.12)で定義すること
ができる39)40)．
𝐸𝐸
𝑔𝑔𝑔𝑔𝑐𝑐𝑟𝑟𝑔𝑔=
𝑛𝑛1∑
𝑖𝑖∈𝑁𝑁𝐸𝐸
𝑔𝑔𝑔𝑔𝑐𝑐,𝑖𝑖=
1𝑛𝑛∑
∑𝑗𝑗,ℎ∈𝑁𝑁 ,𝑗𝑗≠ℎ𝑟𝑟𝑖𝑖𝑗𝑗𝑟𝑟𝑖𝑖ℎ�𝑑𝑑𝑗𝑗ℎ(𝑁𝑁𝑖𝑖)�−1 𝑝𝑝𝑖𝑖(𝑝𝑝𝑖𝑖−1)𝑖𝑖∈𝑁𝑁 (5.12)
また，weighted graphの場合のLocal Efficiencyは，次式(5.13)で定義される．
𝐸𝐸
𝑔𝑔𝑔𝑔𝑐𝑐𝑟𝑟𝑔𝑔𝑤𝑤=
𝑛𝑛1∑
∑𝑗𝑗,ℎ∈𝑁𝑁 ,𝑗𝑗≠ℎ(𝑤𝑤𝑖𝑖𝑗𝑗𝑤𝑤𝑖𝑖ℎ�𝑑𝑑𝑗𝑗ℎ𝑤𝑤(𝑁𝑁𝑖𝑖)�−1)1/3 𝑝𝑝𝑖𝑖(𝑝𝑝𝑖𝑖−1)𝑖𝑖∈𝑁𝑁
(5.13)
5.3.6 Small -World propertyについて
Small-World propertyは，対象とするグラフがsmall-world networkを有するかどうか検 証するための指標である40)．5.2.3節で述べたが，small-world networkとはランダムグラ フと元の規則的なネットワークの間に位置するネットワークであり，それらの双方の特 徴を持つ，つまり高いクラスター係数(high Clustering Coefficient)と短い平均経路長(low Characteristic Path Lengths)をあわせ持つネットワークである．したがって，small-world
network を有するかどうか調べるには，対象となるグラフとそのグラフから構成された
ランダムグラフから生成された平均経路長やクラスター係数などを比較すればよい．こ れを指標化したのがSmall-World propertyと呼ばれる指標である．他にもsmall worldness と呼ばれる指標も存在するが，本研究では取り扱わないので省略する．
Small-World property は規格化された平均経路長𝜆𝜆とクラスター係数γの比で与えられ，
それらは次式(5.14)および(5.15)で与えられる40)．
𝜆𝜆 =
𝐿𝐿𝐿𝐿𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝 (5.14)
𝛾𝛾 =
𝐶𝐶𝐶𝐶𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 (5.15)
ここで，𝐿𝐿𝑟𝑟𝑟𝑟𝑟𝑟𝑔𝑔𝑝𝑝 は対象グラフの平均経路長，𝐿𝐿𝑟𝑟𝑟𝑟𝑛𝑛𝑑𝑑𝑝𝑝 は対象グラフから構成されたランダムグ
ラフの平均経路長，𝐶𝐶𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑔𝑔は対象グラフのクラスター係数，𝐶𝐶𝑝𝑝𝑟𝑟𝑟𝑟𝑛𝑛𝑑𝑑は対象グラフから構成 されたランダムグラフのクラスター係数である．Small-World property はγ/𝜆𝜆で表される ため，
43
Small-World property =
𝛾𝛾𝜆𝜆=
𝐶𝐶𝐶𝐶𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟
∙
𝐿𝐿𝐿𝐿𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟
(5.16)
と表現できる．しかし実際は，ランダムグラフは乱数で制御されるため，乱数が変われ ば当然ネットワークトポロジーも変わり，そのグラフから計算される平均経路長やクラ スター係数などの指標も多少変化する．そのため，ランダムグラフをいくつも作成し，
それらから計算された指標の平均値を用いる．
つまり，実際算出したSmall-World propertyは次式(5.17)のような式で求められる．
Small-World property =
1𝑛𝑛∑ (
𝐶𝐶𝐶𝐶𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝑛𝑛)
∙
𝐿𝐿𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝𝐿𝐿 (𝑛𝑛)𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑝𝑝
)
𝑛𝑛
(5.17)
本研究では，参考文献[40]を参考にn=100でSmall-World propertyを算出した．
44