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

2017 年

スケールフリーランダムグラフの直径に関する考察Ⅰ

浜口幸弘

1．はじめに
近年，複雑な現実世界のネットワーク（complex real-world networks）は自然科学のみならず各分野で注目さてれており，とりわけスモールワールド（small-world）現象は多くの研究が行われてきている。例えば最初の頃では，Albert, Jeong and Barabási（1999，2000）による研究が有名である。この現象では，観測データやコンピュータシミュレーションによって，頂点数 n のグラフの直径はほぼlog n に近くなることが指摘されている。Barabási and Albert（1999）は最初にその現象のモデル化を行っているが，さらに Bollobás and Riordan（2004）は，それにランダムグラフの理論をとり入れてモデル化し，その直径を理論的に与えている。また，この文献はいろいろな分野で数多く引用されている。
本稿では最初の段階として，Bollobás and Riordan（2004）の各定理における疑問点を指摘しつつ議論を進めていくことにする。

2．ランダムグラフの直径
Bollobás and Riordan（2004）によるスモールワールドのランダムモデル化を議論する前に，ランダムグラフにおける直径について述べる。なお，グラフの直径はグラフにおける最長の道（path）の長さとして定義される。また，ここで対象にするランダムグラフのモデルは，確率空間 ɡ（n, M）および ɡ（n, p）のそれぞれに属するグラフ G（n, M）および G（n, p）である（M は辺の本数，p は任意の 2 頂点間における辺の接続確率を表す）。
さて，Bollobás（2001）はランダムグラフの直径の下限と上限を以下の定理として導いている。
［Bollobás（2001）の定理］
ほとんどすべてのランダムグラフのプロセスは以下の不等式を満たす。

95

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

 log n－log 2  log n + 6 
 + 1 ≤ diamGτ 0 ≤ +3
 log log n  log log n 
ここで，τ0 はランダムグラフのプロセスにおいて，グラフが連結される最小の辺の本数を意味する（hitting time）。
この定理の証明（上限についての証明）では，省略されている部分もあるので以下に補足して検討していく。なお，参照する記号，定理と補題は，断りのない限り Bollobás（2001）中に記載されているものである。
まず，Q を特定の性質（property）を満たすグラフの集合とするとき，定理 2.2 を参照して，不等式P（GM has Q）≤ 3 P（Gp has Q）を証明に用いている。ところが，定理 2.2 ではこの不等式について直接は述べていない。この不等式は Q が単調増加（例えば，グラフの直径がある上限 D で抑えられるということは，単調増加の性質）であるときに，定理 2.2（ⅲ）の特別な形であることを意味している。
その証明に関しては，例えば，Frieze and Karoński（2015）に記されている。
次に，P. 269 の記述にある，「青色グラフにおいて与えられた m 個の頂点は，確率 1－o（n－1）で少なくとも mlog n/ 2 個かつ高々3 mlog n/ 2 個の隣接点をもつ」ことを検討してみる。補題 7.5 の証明中の記述から G ∈ ɡ（n,M）における孤立点の個数は高々log n であるから（これは定理 5.3 および定理 7.2 のk0＝1 の場合から導出できる），巨大連結成分（giant component）である青色グラフ G′M ⊂ G の頂点数を n－r（0 ≤ r ≤ log n）とする。すなわち，青色グラフ G′M は確率空間 ɡ（n－r, M）に属す任意のグラフとみなせる。ここで，v を青色グラフにおける任意の頂点とし，v の隣接点の個数を d（1 v）とする。
性質 d（1 v）≤ log n/2 は単調減少であり，d（1 v）≥ 3 log n/2 は単調増加であるから，定理 2.2（ⅱ）により，

p´＝ M（ 2 ）と し て，G′M の 代 わ り に G′p′ で 考 え て も よ い。v の 隣 接 点 の 平 均 個 数 は
n－r（n－r－1）ṕ～log n であり，隣接点の個数は n が十分大きいとき正規分布するから以下を得る。

log n（~ P d（v ）≥2 ） （≤P d（1 v）

13 log n2（C：定数）
ここで，b（ i ; n－r －1, p ）≤）＝ Σ
log ni≥32C（ log n1）21n 0.1＝ o（ n －0.1）b（ i ; n－r －1, p ）の近似に当たっては，本書において最も厳密な近似式を与える定理
Σlog ni≥321.1 を用いている。このことから，青色グラフにおいて与えられた任意の頂点は，確率 1－o（n－0.1）で少なくとも log n/2 個かつ高々3 log n/2 個の隣接点をもつ。よって，青色グラフの頂点 vi（1 ≤ i ≤ m）
以下が成り立つ。
は少なくとも log n/2 個かつ高々3 log n/2 個の隣接点をもつという事象を Ai とすると，（ m － 1 ）P
（ A1 ∨… ∨Am ）＝1 － o（ n－0.1）
P（ A1 ∧…∧Am）≥ P（ A1）+ … + P（ Am）－

このことから，青色グラフにおいて与えられた m 個の頂点は，確率 1－o（n－0.1 ）で少なくともmlog n/2 個かつ高々3 mlog n/2 個の隣接点をもつことを得る。これは証明中の結果とやや異なるが，以下の議論から問題ないと考えられる。
頂点数 n－r のグラフにおいて与えられた m 個の頂点は，少なくとも mlog n/2 個かつ高々3 mlog n/2個の隣接点をもつという事象を R とし，頂点数 n－r のグラフにおいて，その直径は少なくとも D＋196スケールフリーランダムグラフの直径に関する考察Ⅰとなる事象を Q とする。定理の証明における議論の展開を大雑把に式で表すと，以下となる。なお，
近似的に G′p′ の代わりに G′p で考えても同じ結果を得るので，後者で考える。

＋ P（Gp´ ∈ R ）P（Gp´ ∈ Q │ Gp´ ∈ R ）P（Gp´ ∈ Q ）＝ P（Gp´ ∈ ¬ R ）P（Gp´ ∈ Q │ Gp´ ∈ ¬ R ）定理では上記 2 番目の確率項について議論を進めている。このとき前述の不等式 P（GM has Q）≤
3 P（Gp has Q）を用いると，P（G′p ∈ Q）→ 0 を示せば，P（G′M ∈ Q）→ 0 となり，Gτ ∈ ɡ（n, τ0）の0

直径は高々 D であることを導ける。ここでもし，定理 2.2（ⅲ）を適用するならば，P（GM has Q）≤ 3 M1/2 P（Gp has Q） な の で， 先 ほ ど の 議 論 か ら 得 ら れ る P（G′p ∈ ¬ R）＝o（n－0.1 ） の た め に，P（G′p ∈ Q）→ 0 は必ずしも保証されない。よって，グラフの直径は一定の下限と上限をもつという，単調性の性質が証明の鍵になっていることがわかる。
さて，この定理によれば，グラフの直径がスモールワールドの場合より小さくなっており，ランダムグラフはスモールワールド現象を表していないといえる。

3．スケールフリーランダムグラフのモデル化
Bollobás and Riordan（2004）はスモールワールドをランダムグラフでモデル化して，その直径の下限と上限を理論的に導出している。そのモデル化についての概略は，以下のとおりである。グラフ Gに新しい頂点を 1 個ずつ加えるとき，その頂点から m 本の辺をグラフ G に接続する。このとき，多重辺とループも認めるものとする。
さて，m＝1 の場合について，厳密に定式化すると以下のようになる。グラフに追加していく頂点列を v1, v2, …と固定し（以下，頂点の表記は vi＝i とも記す），グラフ G における頂点 v の次数を dG（v）と記す。ランダムグラフのプロセス（G 1t ）t ≥ 0 を次のように帰納的に定義すると，｛ vi：1 ≤ i ≤ t } 上のグラフ G 1t が構成される。すなわち，1 個の頂点と 1 つのループを持つグラフ G 11 から出発する。そして，

G 1t－1 まで構成されたとき，次に追加する頂点 vt と vi ∈ V（G 1t －1）を 1 本の辺で結ぶ。このとき頂点 i（確率変数）は次のようにランダムに選択される。
⎭―⎬―⎫P（i ＝s ）＝dG1t－1（s ）/ 2 t－1 ） 1 ≤ s ≤ t－1（/ 2 t－1 ）1（s = 𝑡𝑡

これは，Barabási and Albert（1999）のモデルを定式化したものとなっている。

m＞1 の場合については，一度に vt から m 本の辺が G 1t －1 に接続される。よって，プロセス（Gmt ）については，プロセス（G mt1 ）において，最初の頂点から m 個の頂点ごとに統合して 1 個の頂点にすれt）が得られることになる。このとき，グラフ G nm の含まれる確率空間を ɡ nm と記す。
ば（G m

さて，G n1 と同じ分布を実現する別の方法がペアリングの点から示されている（Bollobás and Riordan（2000））。すなわち，集合｛ 1, 2, …, 2n ｝を n 個のペア（弦となる）に分割する方法（n-paring）であり，全部で（2n）!/（n! 2n）通りある。それぞれを「線形化された弦のダイアグラム（linearized chord diagram or LCD）」と呼び，L で表す。このとき，左から数字を昇順に並べて，1 つのペアをなす 2 個の数字（要素）が弦で結ばれるようにする。また，各弦において小さい数を左端点（left endpoint），大97

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

きい数を右端点（right endpoint）と呼ぶ。
（L）を構成する方法について略述する。まず小さい数から順に並んだ L に対して，次に，L からグラフφ一番左の端点から出発して最初の右端点に達したら，それまでのすべての端点と右端点を含めて 1 つの頂点に統合する。次に，残りの端点を左から進んで最初の右端点に達したら，先ほどと同様にして 2 番目の頂点を作る。辺については，各弦を右端点に対応する頂点と左端点に対応する頂点とを結ぶ辺で置き換える。
（L）
ここで，L が n 個の弦をもつ（2n）!/（n! 2n）個の LCDs から一様ランダムに選択されるならば，φの分布がスケールフリーグラフと同じ分布になることを n に関する帰納法で証明する。L に関する主張の前提が成り立つとして，L から，L の一番右端にある右端点とそれに対応する左端点を結ぶ弦をとり，φ（L′）の分布はスケー結果としてできる LCD を L′ とする。n－1 のとき主張が成り立つと仮定するので，ルフリーグラフと同じ分布になる。さて除外した弦を改めて L′ に加えるとする。右端点を L′ の一番右端にし，左端点を L′ の入り得る位置（各端点の両隣）に等確率で入れると，その確率は 1/（2n－1）で（L）ある。このとき，L′ が決定されている条件の下で，L は一様ランダムに構成される。上述のグラフφの構成方法に従えば，この追加する弦に対応する辺は，頂点次数に比例した確率（すなわち，前述の式（L′）の 1 つの頂点に接続されることになり，主張は成り立つ。
で示す頂点 i が選択される確率）でφ4．グラフの直径の下限に関する考察
n
まず，G mの直径を評価する Bollobás and Riordan（2004）の定理を以下に示す。

［Bollobás and Riordan（2004）の定理］

m ≥ 2 を整数とし，εを正の実数として固定する。このとき，ほとんどすべての G nm は連結であり，n）は以下の不等式を満たす。
その直径 diam（G mlog n≤ diam（Gmn ）≤（ 1 + ε ）log log nlog log n（ 1 －ε ）log n

この結果は Bollobás（2001）の定理と類似しているが，m＝1 の場合には，diam（G nm）はほぼ log nになることも証明されている。
さて，diam（G nm）の下限を導く場合には，前述の LCD を用いる方法は必要としない。ランダムグラ
フ理論においてよく用いられる期待値による方法を考えればよい。まず Bollobás and Riordan（2004）は diam（G nm）の下限を得るために次の補題を導いている。
［Bollobás and Riordan（2004）の最初の補題］
1 ≤ i ≤ j に対して，以下の式が成り立つ。
（1） P（ ɡ j＝i）＝O（（ij）－1/2）
また，1 ≤ i＜j＜k に対して，以下の式が成り立つ。
（2） P（ ɡ j＝i, ɡk＝i）＝O（i－1（ jk）－1/2）
この補題は前述の定理の不等式の下限を証明する際に用いられている。ここで，上記補題について検98

スケールフリーランダムグラフの直径に関する考察Ⅰ討する。この補題の証明では，次の式が成り立つとして，それを証明に用いている。

dk－1, iP（ ɡ j＝i，ɡk＝i | G k1 －1 ）＝ ｛I ɡj ＝i ｝
2k－1tt i）はグラフ G における頂ここで，IA は事象 A の指示間数（indicator function）であり，dt，i＝dG（11点 i の次数を表す。本文中の（3）式から，右辺は以下となる。

dk－1, i＝｛I｛ ɡj ＝i ｝
I ɡj ＝i ｝P（ ɡk＝i | G k1 －1 ）2k－1
（A ∧ B￨C）＝P（A￨C）P（B￨C ∧ A）とな
さて条件付確率の定義により，事象 A，B，C に対して，Pるので，上の式から以下を得る。
k－1＝ P（ ɡ j＝i | ɡk＝i ∧ G 1I ɡj ＝i ｝｛）

このとき，左辺は 0 または 1 の値となるが，右辺は G 1k－1 かつ ɡk＝i を満たすプロセスの条件下でɡj＝i を満たすプロセスの出現確率であり，これは 0 と 1 の間をとる。両辺は一致せず，この点において疑問が提示できるが，実は，これに続く補題ではこの補題の（1）だけで十分なので，結果的に問題ないと言える。

5．グラフの直径の上限に関する考察
Bollobás and Riordan（2004）によれば，グラフの直径の上限については前述の LCD では導けないということで，彼らは新たな LCD を定義している。以下では，この LCD の構成方法について概略する。
いま N＝mn とし，N 個の弦からなるペアリングを構成することを考える。このとき，x 軸上で右端点の位置を示す確率変数を r1, …, rN とする。これらは区間（0, 1）上で密度関数 2x に従う独立変数である。
そして，各 r1, …, rN に区間（0, 1）に属す実数をランダムに割り当てたら，これらを昇順に並べ替えて，, 1 ≤ i ≤ N 上で一様分布する独立変数を Li として，小さいほうから R1, …, RN とする。次に，区間［0, Ri］弦｛ Li , Ri ｝を構成して LCD を得る。この LCD を用いて G 1mn を構成する方法は，前述の L からグラフφ（L）を構成する方法と同じで，Rk－1 ＜ Li ＜ Rk（R0＝0）を満たす i に対して，各頂点 i から頂点 k までを統合して 1 つの頂点にする。G nm を構成する方法についても前述の方法と同様である。すなわち，m 個の頂点ごとに 1 つの頂点に統合するので，Wi＝Rmi として，Ri の代わりに Wi を対象にする。このとき，Wk－1＝Rm（k－1）＜ Lm（i－1）＋j ＜ Wk＝Rmk（1 ≤ i ≤ n, 1 ≤ j ≤ m）に対して，Lm（i－1）＋j は，x 軸上を右に進んで最初の右端点である Rm（k－1）＋s に 1 つの頂点になるように統合され，さらに Rmk に統合されて，また Rm（i－1）＋j は Rmi に統合される結果，G nm において頂点 i と頂点 k は辺で結ばれる。

この定義の下で，先ほどのようにグラフφ（L）の分布がスケールフリーグラフと同じ分布になるかどうか検討してみる。先ほどと同じ記号を用い，簡単のために m＝1 の場合について前述の帰納法による証明方法に従い考える。L から弦｛ Ln , Rn ｝を除くとする（Rn は最も右端にある端点）。Ln がどの区間（隣り合う右端点の間）に含まれていたか考えると，一様分布するという新たな LCD の定義によれば，その確率は区間幅 ￨Rk－Rk－1￨ に比例する。いま，k＋2 ＜ k′ として，同じ区間幅である［Rk－1, Rk］と99

『経済研究』（明治学院大学）第 153 号［Rk′－1, Rk′］を考えると，それぞれの区間に Ln は同じ確率で含まれていたことになる。ここで，右端点 Ri と R（j i ＞ j）に対して，Rk′ ＜ Ri および Rk ＜ Rj ＜ Rk′－1 とする。このとき，Ri に対応する左端
点 Li は両区間に同じ確率で含まれるが，Rj に対応する Lj は［Rk′－1 , Rk′］に含まれることはない。すな
わち，左側にある区間の方が弦の左端点を含む可能性が高いと思われる。これは Rk の方が Rk′ よりも，φ（L）において頂点の次数が高くなることを意味するので，スケールフリーグラフの構成方法に反する。
したがって，スケールフリーグラフについて論じていないかもしれないという疑問を提示できる。

6．今後の課題
引き続き，Bollobás and Riordan（2004）の証明方法を検討するとともに，上限について他の証明方法を模索する必要もあろう。しかし，任意の 2 頂点の距離がある値以下になることを示すには，その組み合わせのオーダーn２を掛けることになるので，補題 3 の（1）の確率では，そのオーダーが大きく，下限と同様の証明方法は使えない。また，この確率は精度の高い近似なので，簡単には改善することはできない。よって，この確率を用いる場合には，別の点から証明しなければならない。
参考文献
A.-L. Barabási and R. Albert, “Emergence of scaling in random networks”, Science（1999）
R. Albert, H. Jeong and A.-L Barabási, “Diameter of the world-wide web”, Nature（1999）
A.-L Barabási, R. Albert, and H Jeong, “Scale-free characteristics of random networks: the topology of the worldwide web”, Physica A（2000）
B. Bollobás, “Random Graphs（2nd ed.）”, Cambridge University Press（2001）
B. Bollobas and O. Riordan, “Linearized chord diagrams and an upper bound for Vassiliev́ invariants”, J. Knot
Theory Ramifications 9（2000）
B. Bollobás and O. Riordan, “The diameter of a scale-free random graph”, Combinatorica（2004）
A. Frieze and M. Karoński, “Introduction to Random Graphs”, Cambridge University Press（2015）100