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

2015 年

確率的に生成されるネットワークの規模の評価Ⅱ―特定の次数列を満たす大規模ランダムグラフについて―

浜口幸弘

1．はじめに本稿は浜口（2014）の続編に相当する。本稿では，Molloy and Reed（2000）で得られたいくつかの結果を評価するために，ランダムグラフが特定の部分グラフを含む可能性について，期待値の大きさの視点から独自の分析評価を行うものとする。そして本稿で得た結果を Molloy and Reed（2000）の結果と比較して，その類似性と相違性について考察する。

2．概念と用語の定義
ここでは本稿に関係する Molloy and Reed（2000）による概念と用語の定義を概括する。頂点数 n のi ≤ i ≤ n）の次数を di
ランダムグラフ G に対して，各頂点の次数は与えられているものとし，頂点 （1とし，次数 j の頂点の個数を nj（前回は d（j n）としていたが，ここでは便宜上改める）と記す。そして，次数列を D＝n0 ,…, nj , …とする（ j ≤ n－1）。また，n＝∑i ni は十分に大きな数とする。このとき，次数列 D の条件は次のように与えられる。：

ni∑i ≥ 1 iniとなるような定数 λi ≥ 0 が存在して，次数列 D に対して，lim＝K＋o（1）となる定n→∞ n ＝λin数 K が存在する。

i i－2）λi の正負に応じて連結成分の大きさ
Molloy and Reed（2000）によれば，基準量 Q（D）＝∑i ≥ 1（が大きく変わってくる。すなわち，正の場合には大規模な連結成分が生成される結論を得ている。本稿
では，1 より小さい正の定数 δ1 と δ（t δ1＋δt＝1）に対して，n1＝δ1n および nt＝δt n とする。このとき，

Q（D）＝－δ1＋（t t－2）δt である。また，初期状態における頂点コピーの総数を 2m＝n1＋tnt とする（mt t ≥ 3）として与えは構成されるグラフの辺の本数）。そして前回同様，各頂点の次数が予め 1 または （られていて，2 頂点がランダムに接続されるグラフについて議論する。なお，特にこのグラフを対象とする場合は Gt と記すものとする。
65

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

さて，Molloy and Reed（2000）によるコンフィグレーションモデルの構成アルゴリズムでは，頂点コピーのランダムな選択に関して若干の規則を設けているが，頂点コピーをまったくランダムに選択しても同じ結果となる。すなわち，i－1 回目（i ≥ 2）にランダムに選択した頂点コピーと，i 回目にランダムに選択した頂点コピーを接続して辺を構成するという条件のもとでは，上記 2 つの方法によって辺が構成される確率は明らかに同じである。簡単な例をあげると，頂点数 6 で各頂点 1,…,6 の次数が 1 の1グラフを考える。このとき，辺｛ 1，2 ｝が構成される確率は前者の場合と後者の場合は，ともに である。
5
したがって，以降では Molloy and Reed（2000）による構成アルゴリズムではなく，後者の考え方に基づいて議論を行う。

3．期待値による連結成分の大きさの評価次数列が与えられた頂点数 n のランダムな単純グラフを G とし，同じ次数列が与えられた頂点数 nのランダムな多重グラフを G ＊ とする。Q を特定の性質を満たすグラフの集合とすれば，両者のランダムグラフは次のように関係づけられる。

P｛ G∈ Q ｝＝

P｛ G＊∈ Q∧G＊ is simple ｝ P｛ G＊∈ Q ｝P｛ G＊ is simple | G＊∈ Q ｝＝
P｛ G＊ is simple ｝
P｛ G＊ is simple ｝

P｛ G ＊ is simple ｝は正の定数をとる（Bollobás（2001））ので， lim
P｛ G ＊ ∈ Q ｝＝1 ならば， lim
P｛ Gn→∞n→∞∈Q｝＝1 となる。したがって，G の代わりに G ＊ を対象にすることでその性質を分析できる。よって以降では，G ＊ を考えることにする。そして，次数が 1 または t からなるランダム多重グラフ G t＊ が特定の部分グラフを含む可能性について，期待値の大きさの視点から考察する。すなわち，前回のようにグラフ生成のプロセスを直接分析するのではなく，期待値の評価という間接的方法を用いることにする。
そのための基本となる考えが以下である。

k n）の閉路の個数とする。Xk がポアソン分確率変数 Xk をランダムグラフ G t＊ に含まれる大きさ k＝（
P｛ Xk＝0 ｝＝0 すなわ
布することを示せば，前述の考え方に従い，一定条件下にある Gt に対して， limn→∞
P｛ Xk ≥ 1 ｝＝1 が成り立つ。
ち， limn→∞n n（ （（ （（ k （による評価を適宜行n

そこで次の命題を提案するが，その中では不等式 e ≤ n! およびk ≤うことにする。また，（n）r＝n（n－1）…（n－r＋1）と定義する。

en k命題 4Xk をランダムグラフ G t＊ に含まれる大きさ k＝（k n）の閉路の個数とする。また，1 より小さい正の定数 δ1 と δt に対して，n1＝δ1n および nt＝δt n とする（δ1＋δt＝1）。さらに，任意の 0＜δ＜1 に対して，k＝（logn）δ とする。ただし，（t t－2）δt ＞ δ1 である。
このとき， λ＝（ （1t t－1） k（2kδ
t＋ 1δtとすれば，Xk は次のようなポアソン分布をする。

66

確率的に生成されるネットワークの規模の評価Ⅱ

P｛ Xk＝i ｝＝λie－λi!

証明
まず，n＝n1＋nt であり，2m＝n1＋tnt とおく。G t＊ において，大きさ k の閉路をなす頂点コピーのすべての組み合わせの個数を Ck とする。また，このような任意の閉路 1 つが存在する確率を pk とすれば，次のようになる。
（k－1）! ntt t－1））k（（2k（ （Ck＝1

pk＝，（2m－3）…（2m－2k＋1）（2m－1）

よって，t t－1））k（（E（Xk）＝ Ck pk ＝2kt t－1））k（（＝2k（1－t t－1））k（2kt＋（ δn（ （ δn （δδkttδ n（（ δ δ n（（ δ δ n （1－1

（よって，n（…（nt－k＋1）
t nt－1）（n1＋tnt－3）…（n1＋tnt－2k＋1）（n1＋tnt－1）

δ1
1t＋ －δttk－1
δt n＋（t1－t3－≤E（Xk）≤

t t－1） k（2kδt＋ 1
δt＋（t t－1））k（（2k（ （1…

tk1
δ1－δt δt n（Xk）～
このことから，E111tk－1t－

2 －1tt＋（k1δ1 2k－1－δtδt nを得る。

次に、r 個の k- 閉路から構成される順序つき r-tuples の個数の確率変数を（Xk）
r とし，その期待値をE（（Xk）r）とすると，各閉路の頂点共有の有無から以下のように分解できる。
E（（Xk）r）＝E（＋E（1（Xk）
2（Xk）r）
r）
前者の項は各閉路が頂点を共有しない場合の（Xk）
r の期待値であり，後者はそうでない場合の（Xk）
rの期待値である。

E（1（Xk）r）
n －（r－1）k （k－1）! rt t－1））kr（（k2（n1＋tnt－1）（n1＋tnt－3）…（n1＋tnt－2（r－1）k－2k＋1）（ kt （ t k （…（ tn －knt t－1））k r（（（2k（（（n ）（n －k）…（n －（r－1）k）

k（（n ＋tnt－1）（nt ＋k tntt－3）k…（n t＋tnt－2（r－1）
k－2k＋1）111よって，t t－1））k r（nt－rk＋1）kr（（（2kt t－1））k r（（（（n ＋tnt－1）kr ≤ E（（Xk）r）≤（
1

12k67

n kr

（（n ＋tnt－2t rk＋1）kr1

『経済研究』（明治学院大学）第 149 号このことから，E（～（E（Xk））r となる。一方，E（1（Xk）2（Xk）r）r）については以下のように評価できる。
順序つき r-tuples に現れる異なる頂点数を i とすると，1 ≤ i ≤ kr－1 である。よって，これらの頂点のn（ it （となる。後は，計算を簡単にするために，複数の閉路において j 回共有される頂点 v を j

選び方は個の頂点 v1,…,vj とみなし，選んだ i 個の頂点を kr 個として r 個の閉路に割り当てる。起こり得る順序つき r-tuples の個数を s とすれば，以下を得る。
kr－1

kr kr－kk （k－1）! rt∑（（ k （ k （…（ k （iis≤n2＝1（（（t t－1））kr

また，各順序つき r-tuple が Gt に含まれる確率 pr は次のようになる。
1≤（2m－3）…（2m－2kr＋1） （n－2kr）kr（2m－1）
1

pr＝よって，E（＝spr ≤2（Xk）r）
t

1t 2k r2kn＝1（ （ （（rkr－1e kr）2
ent kr－1 （≤（kr）!
nt（2m－2kr）kr kr－1
2（ （≤kr－1t∑（（i（2m－2kr）kr（ 2 （i（kr）!

（（1t2krn1

2 k t＋ n＝o（1）t（（Xk）r）～（E（Xk））r となる。すなわち，Bollobás（2001）定理 1.22 によれば，主張がしたがって，E示されたことになる。□

k n）の閉路を少なくと｛ Xk＝0 ｝＝e－λ → 0 となり，ほぼすべての Gt は大きさ k＝（
この命題から，Pも 1 つ含むことを導ける。これは，Molloy and Reed（2000）の結果を改善したものではないが，Xk がポアソン分布することがわかるという点では，若干意味ある情報が得られると言える。

k n）の部分木 Tk の出現
次に，Gt に含まれる最大の連結成分の大きさを評価するために，大きさ k＝（（（Xk）r）を確率を評価したい。ところが，Xk をランダムグラフ G t＊ に含まれる Tk の個数とすると，E求めることは前述の閉路の場合よりかなり複雑になるので，Xk がポアソン分布するか否か評価するこ（Xk）を導出し，マルコフの不等式を利とは容易ではない。よって今回は，以下のような手順に従い，E用して Xk の大きさを確率的に評価する。
まず，Tk を固定して考え，Tk を含む連結成分を Ck とする。そして，Ck ⊋ Tk のとき，e ∈ Ck かつe∈Tk を満たす辺 e の両端点が Tk に含まれるならば，e を分離して 2 つの辺にし，各端点を次数 1 のダミーの頂点とする。あるいは，辺 e の 1 つの端点だけが Tk に含まれるならば，含まれない方の端点を次数 1 のダミーの頂点とする。こうして，i 個のダミーの頂点 v1,…,vi が得られるとする。そして，Tkおよび v1,…,vi とそれらに接続する辺から得られる孤立した部分木を Tk′とする。Tk′は次数 1 と t の頂点（k－2）＝から構成され，辺の本数が k＋i－1 である。このとき，i の範囲は 0 ≤ i ≤ 2（t－1）＋（t－2）

k＋2 となる。また，Tk において，次数 1 の頂点と次数 t の頂点の個数をそれぞれ xi および yi と（t－2）
すれば，以下の式が成り立つ。

xi＋yi＝k かつ xi＋i＋tyi＝2（k＋i－1）（*）
68確率的に生成されるネットワークの規模の評価Ⅱよって， xi＝k t－2）－i＋2（t－1yi＝，k＋i－2となる。このとき，xi および yi は整数であると仮定t－1を構成できない）。
して議論する（どちらか整数でない場合，Tk′
次に，Tk′における頂点コピーの組み合わせを考える。まず，Tk′の 1 つの頂点を最上位レベルの根として位置づけ，その隣接点を次の下位レベルに位置づけ，それらの各頂点に隣接する点を次の下位レベルに位置づけ，この手順を繰り返して Tk′を平面上に位置づける。そして，上位レベルの頂点から順に以下の手続きを行う。そのレベルで未手続きの次数 t の頂点があれば，上位の 1 個の隣接点と下位のt－1 個の頂点に割り当てる頂点コピーを選択する。その選択方法は t! 通りある。よって，Tk′における頂点コピーの組み合わせは（t!）yi となる。の総数を求める。（*）を満たす次数 1 の頂点が xi＋i 個，次数 t の頂点が yi 個与えられてい次に，Tk′の総数は次のようにるとき，Matousek and Nesetril（2008）によればこれらの頂点から構成される Tk′与えられる。
（k＋i－2）!
（（t－1）!）yi
ここで，T k′からダミーの頂点を除けば Tk を得るが，i＝0 の場合を除き，Tk は重複して数えられるので，ai で割り引いて補正する。したがって，Tk の頂点を選択して組み合わせるようにすれば，以下を得る。
（t－2）k＋2n1 n1（k＋i－2）!

tt!）y∑（（xi（ yi （（2m－3）…（2m－2k＋3）（（t－1）!）y ai （2m－1）
iE（Xk）＝ii＝0

今回は上記の理由により，最も簡単な i＝0 の場合（ai＝1），すなわち Tk が孤立木となる場合を対象にする。記号の定義は先の命題に従う。
命題 5δ1 ＞ et（t－1）δt とし，k＝εn（0＜ε＜δt）とする。このとき，ほとんどすべての Gt は Tk を含まない。
証明

Xk を G t＊ に含まれる大きさ k＝（k n）の孤立木 Tk の個数とする。前述の議論から以下を得る。
n1 n（k－2）!

1（ x （ yt（（t!）y （（t－1）!）y （2m－1）（2m－3）…（2m－2k＋3）E（Xk）＝000

n1 n01（ x （ yt （t y k!（2m－1）（2m－3）…（2m－2k＋3）＝o（1）≤000

よって，マルコフの不等式から主張を得る。

□この結果は，Molloy and Reed（2000）の結果に比べて弱い結果となっている。この場合，期待値による評価方法に若干の問題があると思われる。

69

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

4．課題
引き続き考察を行って，次回にまとめを行う予定である。
参考文献
B. Bollobás, Random Graphs（2nd edition）（2001）.Cambridge Univ. Press
J. Matousek and J. Nesetril, Invitation to Discrete Mathematics（2008）,Oxford Univ. Press
M. Molloy and B. Reed, “A Critical Point for Random Graphs with a Given Degree Sequence”, citeseerx. ist. psu.
edu（2000）
M. Molloy and B. Reed, “The Size of the Largest Component of a Random Graph on a Fixed Degree Sequence”,
Combinatorics, Probability and Computing 7, 295-306（1998）
M. Molloy and B. Reed, “A Critical Point for Random Graphs with a Given Degree Sequence”, Random Structures
and Algorithms 6, 161-180（1995）
浜口幸弘，確率的に生成されるネットワークの規模の評価Ⅰ―特定の次数列を満たす大規模ランダムグラフについて―，明治学院大学経済研究 147（2014）70