『経済研究』（明治学院大学）第 146 号

2013 年

スケールフリーネットワーク評価基準量の一般的グラフへの拡張

浜口幸弘

1．本稿の概要
本稿は浜口（2010，2011）の続編に相当する。浜口（2010）では，Li et al.（2005）の提案したネットワークを識別するための新たな基準量 s‑ 値に基づき，次数列が与えられたときに s‑ 値を最大にする*について考察した。浜口（2011）では，その考察をさらに深め，次木 Tmax とその中の特徴的な T max数列が与えられたとき，ネットワークの主要基準量である 2 頂点間の平均距離に関して，それをできる限り小さくするような木 Tmax ついて考察した。本稿では，浜口（2010，2011）の結果の一部を一般的グラフに拡張し，その展開を試みる。すなわち，既に提案した概念および命題に基づいて，一般的グラフでの定義を新たに加え，与えられた次数列 d1 ≥ d2 ≥ … ≥ dn を満たす一般的グラフ G を出来る限りs‑ 値をもつグラフ G' へ変換し，G' が最大の s‑ 値をもつグ
大きな（接続点の交換に関して s‑ 極大な）ラフ Gmax となり得るか否かについて考察する。

2．基礎概念と定義
ここでは，後で命題を導くために必要な一般的グラフに対する本稿独自の概念と定義を幾つか与える。
まず，G を単純無向グラフとし，その頂点集合を V（頂点数 n＝ | V | ），その辺集合を E とする。また，（d1 ≥ d2 ≥ …
任意の頂点 i に対して，その次数の大きさを di で表し，G の次数列を D＝（d1, d2, …, dn）≥ dn）とし，頂点 i, j に対して（i, j）を辺とする。そして （D）を同じ次数列 D をもつ単純無向グラs G）（G の s‑ 値ともいう）を与えてフの集合とする。このとき，Li et al.（2005）は次のような基準量 （いる。

s G）=Σ
（∈E di dj（i, j）（G∈ （D））

さて本稿では，最大の s‑ 値をもつグラフ Gmax の構成アルゴリズムについては言及しないで，グラフが構成できる次数条件は満たされていると仮定して議論する（その条件については広く知られている
49

CW3̲AX094D05.indd 49

2013/01/18 18:58:26

『経済研究』（明治学院大学）第 146 号が，例えば Li et al.（2005）参照）。諸定義と概念については，浜口（2010，2011）に従うが，本稿では新たに以下の定義を用意する。以下の定義では，グラフ上のレベル i を li と表記し，li 上の頂点の集合を Li と記す。
定義 1（一般的グラフ G の平面上における頂点の位置づけ）。そして，l1平面上の連結グラフ G に対して，最大次数の頂点の一つを根 r とする（l0 に位置する）
において根 r に隣接する頂点を左端から右端に次数の大きいものから並べる。以降，既に並べられたレベル（li−1）上の左側の頂点から順に，各頂点の下流の隣接点（既に並んだ頂点は操作から除外する）を次のレベル（li）で次数の大きい順に左から並べる。
よって平面上で頂点の位置づけをした G に対して，頂点 α と β が同じレベルで，α が β より左に並ぶのは，それぞれの上流の隣接点がすべて同じで dα ≥ dβ の場合（等号の場合は，どちらが左でもよい），または α の上流のある隣接点が β の上流のすべての隣接点より左にある場合である。また，li の頂点はその上流の隣接点を li−1 だけにもち（li におけるある頂点同士が隣接してもかまわない），li−2 の頂点と隣接することはない。一般的グラフに対して，上の定義を適用して得られるグラフは明らかに元のグラフと同型である。
次に，各頂点の位置を数字で表すために，上のグラフの根 r を 1 とし，次に l1 の左端から 2，3，…
として，以降各レベルにおいて左端から右端に進みながら番号を順次与え，すぐ下のレベルに進んで同様に番号をつけていく。また，頂点間において相対的にレベルの数字が小さければ，その頂点はより上位のレベルにある（すなわち，根 r 迄の距離がより近い）と呼ぶ。
次に頂点の接続に関する操作について，便宜上，名前をつけておく。
定義 2（接続点の交換）
頂点の位置づけに従う G 上の任意の頂点 α と β に対して，α のある隣接点を u とし，β のある隣接（G）かつ 辺（v, α） E（G）である。このとき，α と u および β と点を v とする。また，辺（u, β） Ev の接続を解消し，α と v および β と u を新たに接続する（明らかに次数列は維持される）。これを αと β の接続点の交換と呼ぶ。
接続点の交換では，4 頂点の各次数が維持され，その接続関係のみが変化するので，グラフの s‑ 値の変化を局所的側面から分析できる。この点において，ネットワークの性質を扱う上で最も基本的なグラフの変換方法であると言える。
以下の議論で，辺（u, α）および（v, β）の組（u と β および v と α はそれぞれ接続されていない）に対して接続点の交換によって得られるグラフ（図 1 参照）の s‑ 値の変化分 Δs は，Δs＝du dβ＋dv dα−（du dα＋dv dβ）＝（du−dv）（dβ−dα）であり，よってΔs＞0 ↔ du㲖dv and dβ㲖dα であることに注意する。また，4 頂点 x, y, u, v がこの順に隣接する（G）かつ（y, v） E（G）である場合（隣接点の交換と呼ぶ）も，明らかに上の道において，（x, u） E場合に帰着される（図 2 参照）。

50

CW3̲AX094D05.indd 50

2013/01/18 18:58:26

スケールフリーネットワーク評価基準量の一般的グラフへの拡張

uv

uv

αβ⇒αβ
図1xyu

接続点の交換

vxuyv

⇒
図2

隣接点の交換

これらの定義に基づいて，次数列 d1 ≥ d2 ≥ … ≥ dn を満たす一般的グラフ G をできる限り大きな（接s‑ 値をもつグラフ G' へ変換し，G' が最大の s‑ 値をもつグラフ Gmax
続点の交換に関して s‑ 極大な）となり得るか否かについて考察する。
なお，同じ次数列のグラフでも，非連結グラフを認めると最大の s‑ 値 smax が異なる場合がある。例（3, 3, 3, 3, 1, 1）を満たすグラフを考える。このとき，以下の 2 つの種類のグラフ
えば，次数列 D＝Gmax が考えられる。

smax＝51

smax＝55（a）連結（b）非連結
図3

最大の s ‑ 値をもつグラフ（b）は非連結で最大の s‑ 値をもつグラフである。
（a）は連結で最大の s‑ 値をもつグラフであり，本稿では接続点の交換によって得られるグラフには，非連結グラフも含めることにする。というのは，Δs の最大化と連結性の維持は必ずしも両立しないからである。しかし，ネットワークとして考える場合，連結グラフである方が望ましいので，できる限り大きな s‑ 値をもつ連結グラフが得られる手続きについても考える。

51

CW3̲AX094D05.indd 51

2013/01/18 18:58:26

『経済研究』（明治学院大学）第 146 号

3．一般的グラフへの s ‑ 値の拡張木の場合と異なり，一般的グラフに s‑ 値の概念を適用し，接続点の交換によってその性質を理論的に導くことは非常に難しい。よって，ここでは部分的に近似的方法を用いることにする。
以下で与える命題での接続点交換の基本方針は，接続点交換によって得られるグラフの任意の頂点 v（∈Lj）に関して，できる限りレベルが高い（最高 lj＋1），より左側の頂点と接続するように操作することである。
まず，Gmax の中で特徴的な性質をもつグラフを導く方法として命題 1 を与える。なお，Gmax は非連結グラフも含めるとする。
命題 1
任意のグラフ Gmax に対して，C0 はGmax の任意の連結成分とする。任意の k に対して，頂点の位置づけに従う Ck−1 から，接続点の交換を通して，連結性を維持しながら，次のような頂点の位置づけに従う連結成分 Ck を構成できる。

Ck において，1 から i 番目の頂点までの集合を Vi とする（1 ≤ i ≤ k）。このとき，∀u∈Vi . ∀v∈V（Ck） Vi . du ≥ dvである。さらに，Gmax が非連結であれば，他の連結成分に対しても上記の性質を満たすようにでき，その和をとれば，Gmax と同じ s‑ 値をもつグラフを構成できる。
証明

k＝1 のとき，明らかに主張は成り立つ。
k−1 に対して主張が成り立つと仮定する。すなわち，Ck−1 は∀u∈Vi . ∀v∈V（Ck−1）\Vi . du ≥ dv
（1 ≤ i ≤ k− 1 ）である。そこで，Ck−1 の k 番目の頂点を α（∈V（Ck−1）\Vk−1）とし，そのレベルをj（すなわち lj）とする。
（Ck−1 ）\Vk−1 に対して，dα ≥ dβ ならば，Vk＝Vk−1∪ { α } とし，α を Ck における k 番
任意の β∈V目の頂点とする（実際，Ck の頂点の位置づけを行うと k 番目の頂点となる）。
（Ck−1）\Vk−1 かつ dα＜dβ であるような頂点のうちで，最大次数の頂点を β
そうでないときは，β∈V（複数個あれば，最上位レベルの最も左側の頂点とする）とする。このとき，Ck−1 は頂点の位置づけ（Ck−1）であるような α の上流のある隣接点 u が存在して，（α, v） E（Ck−1）であに従うから，（β, u） Eるような β の隣接点 v が存在する。よって，α と β に対して接続点の交換を行い，Vk＝Vk−1∪ { β } とし，β を Ck における k 番目の頂点とする（実際，Ck の頂点の位置づけを行うと k 番目の頂点となる）。このとき，Ck−1 に対する接続点の交換によって得られる Ck は連結である。なお，この場合のより詳しい説明に関しては，便宜上，命題 2 の証明において行う。
これで主張の前半部分が成り立つ。また，任意の連結成分についても上と同様の手続きを行えば，各連結成分について主張の前半部分が成り立つ。
また，接続点の交換によるグラフ全体の s‑ 値の変化分 Δs は，帰納法の仮定から du ≥ dv であるから，
52

CW3̲AX094D05.indd 52

2013/01/18 18:58:27

スケールフリーネットワーク評価基準量の一般的グラフへの拡張

Δs＝du dβ＋dv dα−（du dα＋dv dβ）＝（du−dv）（dβ−dα）≥ 0
よって手続きが行われる連結成分すべての s‑ 値の総和は，Gmax と同じになるので，後半部分の主張が成り立つ。□
上の命題を繰り返し適用して最終的に得られる Gmax に対して，頂点の位置づけを行うと，Gmax に関して以下のような考察を得る。

n が十分大きく，ある （k ＜n）に対して，最初の次数列の大きさの関係が d（v0）＞d（v1）＞…＞d（vk）となる（d（vi）は頂点 vi の次数）場合を考えると，命題 1 の証明手続きから，すべての Gmax において低いレベル（次数の大きい頂点からなる部分グラフ）の構造は類似していることが分かる。

s G）＜smax）より出来る限り大きな s‑ 値をもつグラフの構
次に，次数列を満たす任意のグラフ G（（成方法について考える。そこで，命題 1 の証明方法を利用すれば以下の命題を得る。
命題 2
任意のグラフ G＝∪i C（i Ci は G の任意の連結成分）に対して，一定の手続きを通して，次のような頂点の位置づけに従う G′ を構成できる。

s G′）≥ （s G）となり，かつ連結成分 Ci は連結成分 Ci′ に変換されて G′＝∪i Ci′ で，（Ci′ において，1 から j 番目の頂点までの集合を Vj とする（ ni＝ | Ci′ | と し て, 1 ≤ j ≤ ni ）と，∀u∈Vj ．
∀v∈V（Ci′）\Vj . du ≥ dv である。
証明
命題 1 の証明方法を利用して以下の（＊）が成り立つことを示す。

G の任意の連結成分 C に対して，G0：＝C とする。このとき，任意の k に対して，連結な Gk−1 から，接続点の交換を通してそれ以上の s‑ 値をもつ，次のような頂点の位置づけに従う連結な Gk を構成できる。

Gk において，1 から j 番目の頂点までの集合を Vj とする（1 ≤ j ≤ k）と，∀u∈Vj . ∀v∈V（Gk）\Vj . du ≥ dv である。また，（s Gk）≥ （s Gk−1）である。（＊）
k＝1 のとき，明らかに主張は成り立つ。
k−1 に対して主張が成り立つと仮定する。すなわち，Gk−1 は∀u∈Vj ．∀v∈V（Gk−1）\Vj ．du ≥ dv
（1 ≤ j ≤ k−1）である。そこで，Gk−1 の k 番目の頂点を α（∈Lt）とする。
（Gk−1 ）\Vk−1 に対して，dα ≥ dβ ならば，Vk＝Vk−1∪{ α } とし，α を Gk における k 番任意の β∈V目の頂点とする（実際，Gk の頂点の位置づけを行うと k 番目の頂点になる）。
（Gk−1）\Vk−1 かつ dα＜dβ であるような頂点のうちで，最大次数の頂点をそうでないときは，β∈Vβ とする（複数個あれば，最上位レベルの最も左側の頂点とする）。このとき，Gk−1 は頂点の位置づけ（Gk−1）であるような α の上流のある隣接点 u が存在して，（α, v） E（Gk−1）に従うから，（β, u） Eであるような β の隣接点 v が存在する（最もレベルの高い頂点を v として選択する）。よって，α と βr Gk−1 の根）を含む連結成分における k 番に対して接続点の交換を行い，Vk＝Vk−1∪{ β } とし，β を （。しか目の頂点とする（実際，Gk の頂点の位置づけを行うと，連結成分における k 番目の頂点になる）
し，この接続点の交換によって Gk は非連結，すなわち連結成分が 2 つになる可能性がある（以下で，53CW3̲AX094D05.indd 53

2013/01/18 18:58:27

『経済研究』（明治学院大学）第 146 号

その可能性は否定される）。
上述の後者の場合について詳述すると次のようになる。頂点の位置づけに従う Gk−1 において，α∈Lt の上流の隣接点の個数を a とする。まず，β∈Lt の場合を考える。そこで，α と β が lt−1 において，頂点を b 個共有するとする。このとき，頂点の位置づけの定義から，0 ≤ b＜a である。また，dβ＞dαだから，β の残りの隣接点がすべて α に接続するならば，α の隣接点の数は dβ−b＋a となり，dβ−b＋a＞dα だから矛盾する。よって，辺（α, v） E（Gk−1）かつ（β, u） E（Gk−1）を満たすような β の隣接点 v および α の上流の隣接点である u が存在する。なお，明らかに β が lt に位置する場合には，Gk は非連結にならない。
次に，β が lt＋1 以下に位置する場合についても，b＝0 とすれば同様に考えられる。ところが，β がlt＋3 以下の場合は，上記の接続点の交換では，Gk が非連結になる可能性がでてくる。すなわち，Gk が非連結になるのは，Gk−1 において以下の 3 つの条件を満たす場合に限られる。

u と v を結ぶ任意の道が α を通り，β を通らず，かつα と u を結ぶ道が辺（α, u）だけであり，かつβ と v を結ぶ道が辺（β, v）だけである。
まず，このことを示す。
明らかに，Gk−1 において上述の 3 つの条件が成り立つならば，Gk は非連結である。
逆に，Gk−1 において u と v を結ぶある道が α を通らない，または u と v を結ぶある道が β を通ると仮定する。このとき Gk−1 において，u と v を結ぶある道が α と β を通る，α も β も通らない，β を通り α を通らないのいずれかならば，Gk は連結になる。また，α と u を結ぶ道が辺（α, u）だけではない，または β と v を結ぶ道が辺（β, v）だけではないならば，Gk は連結になる。
そこで，上記の条件が成り立つ場合には，別の接続点の交換を考える。すなわち，β の最も低いレベ
ルの隣接点を z とする（dβ ≥ 2 だから v と異なる z をとれる）。このとき，Gk−1 において道 P＝v0…

vi−1vi…vj−1vjvj＋1 かつ vi−1＝u, vi＝α, vj−1＝v, vj＝β, vj＋1＝z が存在する。（α, z） E（Gk−1）かつ（β,u） E（Gk−1）だから，辺（u, α）および（β, z）を切り離し，u と β および α と z を接続すれば，P は道 P′＝v0…vi−1vjvj−1…vi＋1vivj＋1 に変換できる。すなわち，これは上述とは別の接続点の交換になる。
連結性は維持される。
この接続点の交換によって接続関係が変化する頂点は vi−1, vi , vj , vj＋1 だけであり，前者の接続点の交換の場合，帰納法の仮定から，du ≥ dv かつ dβ＞dα であり，後者の接続点の交換の場合も同様に，du ≥ dz かつ dβ＞dα となる。それぞれ s‑ 値の変化分 ∆s は，∆s＝dudβ＋dvdα−（dudα＋dvdβ）＝（du−dv）（dβ−dα）≥ 0 および∆s＝dudβ＋dzdα−（dudα＋dzdβ）＝（du−dz）（dβ−dα）≥ 0となる。よって，s‑ 値は Gk−1 のそれ以上である。
以上のことから，連結な Gk において 1 から j 番目の頂点までの集合を Vj とする（1 ≤ j ≤ k）と，s Gk）≥ （s Gk−1）である。
∀u∈Vj . ∀v∈V（Gk）\Vj . du ≥ dv であり，かつ （
そこで，この議論を続ければ，C から始めて有限回の操作で s‑ 値に関して極大な C′ を得る。また，G が非連結ならば，それらに対しても同様の手続きを行うことで主張を得る。□
54

CW3̲AX094D05.indd 54

2013/01/18 18:58:27

スケールフリーネットワーク評価基準量の一般的グラフへの拡張

命題 2 によれば，有限回の操作で s‑ 値に関して極大な G′（必ずしも連結ではない）を得ることができる。最初のグラフ G から連結グラフを得るためには，命題 2 の証明方法にしたがってグラフを変換する過程において，以下の方法が考えられる
最初にグラフを連結して，s‑ 値の増大をはかる。
最終的に得られたグラフを連結して s‑ 値の増大をはかる。
（C）お よ び（u, v）∈E
こ の と き， 連 結 成 分 C と C′ に 対 し て，（x, y）∈E（C′）と す る。 ま た，dx

≥ dy ≥ du ≥ dv とする。
このとき，du dx＋dv dy−（du dy＋dv dx）＝（dx−dy）（du−dv）≥ 0∆s＝du dx＋dv dy−（dx dy＋du dv）＝（dx−dv）（du−dy）≤ 0
よって，dx と dv の差が小さく，かつ du と dy の差が小さくなるような辺の組に対して，接続点の交換を行えば ∆s の減少分を抑えられ，C と C′ を接続することができる。しかし，どちらの方法にしても Gmax が得られる保証はない。
さて，グラフの連結性を維持しつつ，∆s の増加を実現するには，特定の条件を満たす必要があることがわかる。ここでは，上述の接続点の交換とは異なる方法として，道上での接続点の交換に関する命題 3 を与える。
命題 3
任意の連結グラフ G に対して頂点の位置づけを行い，レベル i にある頂点を vi∈Li とし，その次数j i ＜ j）に対して，d（vi−1）−d（vj−1）≥ d（vi＋1）−d（vj＋1）かつ d（vi）を d（vi）と記す。このとき，ある i, （＜d（vj）であるような道 P＝vi−1vivi＋1…vj−1vjvj＋1 が存在するならば，P にある操作を行い，連結かつ∆s ≥ 0 となるグラフ G′ が得られる。
証明
頂点の位置づけに従う連結グラフ H 上の任意の道 P＝vi … vj vj＋1…v（k i＜j＜k−1）に関し，任意のj に対して vj∈Lj とする。頂点の位置づけの定義から，P 上で vj と隣接するのは，vj−1 と vj＋1 だけである。よって，P 上で vj と vj＋1 の交換を行うと，H における 2 頂点間の接続関係の変化は，vj−1 と vjの接続が vj−1 と vj＋1 の接続に代わり，vj＋2 と vj＋1 の接続が vj＋2 と vj の接続に代わるだけであり，また，多重グラフになることもない。このことから H は連結グラフ H′ に変換できる（この頂点の交換方法は，前述の接続点の交換とは異なる）。
そこで G の道 P＝vi−1vivi＋1…vj−1vjvj＋1 上で上述の頂点の交換を繰り返し，P′＝vi−1vjvi＋1… vj−1vivj＋1 とする。このとき，G′ の連結性は維持され，∆s＝（d（vj）−d（vi））（d（vi−1）−d（vj−1）−（d（vi＋1）−d（vj＋1）））≥ 0 である。□
命題 3 の手続きによれば，∆s は最大でないが，連結性が維持されるグラフが得られる。
さて，頂点の位置づけに従うグラフにおいて，任意の連結成分 C の 1 から i 番目の頂点までの集合（C）\Vi . du ≥ dv を満たす Gmax の集合を，を Vi とする（1 ≤ i ≤ | C | ）。このとき，∀u∈Vi . ∀v∈V55

CW3̲AX094D05.indd 55

2013/01/18 18:58:27

『経済研究』（明治学院大学）第 146 号*G maxと定義する。
*となる保証はないが，次数の大きな頂点同士命題 2 の手続によって得られるグラフ G′ が G′∈G max*が接続するような構成方法から G maxと類似した性質をもつと予想される。この一連の方法によって，*（d1, d2, …, dn）を満たす任意のグラフ G と G maxの関係が，段階的に単調増加する ∆s の次数列 D＝大きさによって定量的に近似評価できる。

4．課題
導出した命題は明らかにまだまだ改良の余地を残している。一般的グラフに対して連結な Gmax を得るためのより精密な理論を導く必要がある。

参考文献
Li, L., Anderson, D. , Doyle, J. and Willinger, W.（2005）. “Towards a Theory of Scale-Free Graphs: Deﬁnition,Properties and Implications”, Internet Math. 2: 4, 431‑523
浜口（2010），スケールフリーネットワーク評価のための基準量の提案，明治学院大学経済研究 144
浜口（2011），スケールフリーネットワーク評価のための平均距離の分析，明治学院大学経済研究 145

56

CW3̲AX094D05.indd 56

2013/01/18 18:58:27