2017
年度修士論文
Preferential Attachment
で生成されるネットワーク
の分裂に伴う性質
学籍番号：
5116A027-2
氏
名：下邨 貴裕
概要
Preferential Attachmentで生成されるネットワークは，新たに追加されるノードは次数が
高いノードにつながりやすいといった優先的選択ルール(Preferential Attachment)を持って
ネットワークに追加され，時間が十分たてばスケールフリーネットワークとなることが知られ
ている．このとき，追加されるノードがセルフループを起こすことによって，どの既存のノー
ドとも接続しないという状態が生まれ，ネットワークの分裂が発生する．
本稿ではこの「分裂」に関する性質について考察を行い，分裂で発生するグループの数の増
え方や，ノードが孤立する確率，グループサイズの増え方が明らかになった．特に，グループ
サイズは生成時刻に反比例するので後から生成されたグループはほとんど大きくならないよう
にみえるが，時間がたてば十分大きくなるということが分かった．また，異なる時間に生成さ
れたグループも成長のスピードは遅いが，同じ構造を保って成長し，最終的にスケールフリー
目次
1 はじめに 3
1.1 はじめに . . . 3
1.2 Preferential Attachmentで生成されるネットワーク. . . 4
2 ネットワークの分裂に関する性質 7 2.1 ネットワークの分裂で生成されるグループの数 . . . 7
2.2 生成されるグループの大きさ . . . 9
2.3 ノードが孤立する確率 . . . 12
2.4 後から生成された小さなグループの成長 . . . 13
2.5 グループ構造の確率的同等性 . . . 16
2.6 各グループの次数分布 . . . 19
1
はじめに
1.1
はじめに
ネットワークとは，点(ノード)と線(リンク)で構成されるものであり，身の回りで多く観測さ
れる．例えば，人をノード，友人関係をリンクとみれば，人間関係をネットワークを用いて表すこ
とができる．現在，ノード間の病気拡散や情報伝搬[1]や，ネットワークの構造の変化[2]ネット
ワークの生成[3]など様々な研究が行われ，応用されている[4]．
本稿では構造の変化，特に，「分裂」に着目し，研究を行った．どのネットワークにおいても「分
裂」は避けられない現象である．例えば，企業や学校内における意見の違いによる派閥闘争[5][6]
や習慣の違いによるグループ分裂[7]など様々な「分裂」を観測することができる．これらに共通
していることは，人が友達をつくるとき，ランダムに行っているのではなく，何かしらの「選択」
を行っており，その選択の基準により分裂が発生し，グループが生成されている，ということであ
る．
本研究では，その「選択の基準」を「友人の数」と定め，「Preferential Attachment」[8]という
接続先の次数を選択の基準とするルールを持ったモデルで解析を行った．次数とはノードにつな
がっているリンクの本数のことで，人間関係であれば友人の数を意味する．つまり，このモデルは
新しく友人を増やすとき，友人数が多い人を選びやすい，といったモデルである．
また，詳しくはTheorem1.1にて述べるが，このモデルはスケールフリーネットワークであり，
ノードを1つ選んだときのそのノードの次数がkである確率をP(k)とすると，P(k)∝k
−3 であ
る[9]．つまり，多数のノードが小さな次数を持ち，少数のノードが大きな次数を持つという点で
Twitterや空港と航空便，WWWのリンクなど，多くとつながっているのはごく少数であり，ほ
とんどはごく一部としかとつながっていないという現実のネットワークの特徴をよく表しているモ
デルである[4][10]．
以下，「Preferential Attachment」で生成されるネットワークの性質について述べた後，分裂に
1.2
Preferential Attachment
で生成されるネットワーク
Definition 1.1. (Preferential Attachment)([8])
Preferential Attachmentで生成されるネットワークは以下の流れで生成される．
1. 時刻tにおけるネットワークをG(t)とし，構成するノードとリンクの集合V(t)，E(t)を用
いてG(t) = (V(t)，E(t))で表す．また，ノードのインデックスは時刻tと一致するものと
する．
2. セルフループを持つノード1が1つある状態G(1)を初期ネットワークとする．つまり，
V(1) ={1}，E(1) ={(1，1)}である．
3. 時刻tにおいて，G(t−1)に新しいノードtが追加され，既存のノードsを1つ確率psで選
び，接続する．psはノードsの次数をksとしてps =
ks ∑t
s=1ks
で定義する．特にkt = 1と
し，ノードtが自分自身を選んだときにはセルフループが発生する．このとき，ネットワー
クの分裂が発生し，グループを生成する．
つまり，時刻tに分裂が発生する確率は
P(時刻tに分裂が発生) =
1
2t−1 (1.1)
である．
図1 ネットワーク生成の様子．t= 2のとき，ノード1は次数2，ノード2は次数1であるの
で，ノード1は確率
2
3の確率でノード1を選択し，接続する．t= 3ではノード3は自分自身を
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
図2 統計分析フリーソフト「R」を用いて作成した，Preferential Attachmentで生成された
G(250)の例．見やすさのため，セルフループは省略してある．黄色のノードがセルフループを
起こし，分裂を発生させたノードである．
Preferntial Attachmentで生成されるネットワークは，時間が十分たてばスケールフリーネット
ワークとなる．すなわち，Theorem1.1が成立し，p(k)∝k
−3
が成り立っている．多数のノードが
小さな次数を持ち，少数のノードが大きな次数を持つという点，また大きな次数を持つ人にたくさ
ん人が集まり，そうではない人は孤立していくという点で現実のネットワークの特徴をよく表して
いるといえる．
Theorem 1.1. ([9])
Nk(t)をG(t)に含まれる次数kのノードの総数とする．このとき，次が成り立つ．
lim
t→∞
Nk(t)
t =
4
k(k+ 1)(k+ 2) (1.2)
このとき，G(t)はスケールフリーネットワークである．すなわち，ノードを1つ選んだときのそ
のノードの次数がkである確率をP(k)とすると，
P(k) = lim
t→∞
Nk(t)
t =
4
k(k+ 1)(k+ 2) ∝k
−3
定理1.1を証明するにあたって，Lemma1.1の成立を認める．
Lemma 1.1. ([11])
Nk(t)をG(t)に含まれる次数kのノードの総数とする．このとき
lim
t→∞
Nk(t)
t =q(k) (1.4)
と収束値を持つ．
Proof(Theorem1.1).
新しいノードがG(t)に含まれる次数kのノードを選択するという事象をAk(ただし，セルフル
ープはA1に含む)とすると
Nk(t+ 1)−Nk(t) = 1Ak−1−1Ak
(k≥2) (1.5)
N1(t+ 1)−N1(t) = 1−1A1 (1.6)
k≥2のとき，(1.5)より
E[Nk(t)−Nk(t−1)] =E[1Ak−1−1Ak]
= k−1
2t−1E[Nk−1(t−1)]− k
2t−1E[Nk(t−1)]
∴E[Nk(t)−Nk(t−1)] = k−1
2t−1E[Nk−1(t−1)]− k
2t−1E[Nk(t−1)]
となる．Lemma1.1より lim
t→∞
Nk(t)
t =q(k)と収束値を持つので，十分大きなtに対して
q(k) = k−1
2 q(k−1) + k 2q(k)
よって
q(k) = k−1
k+ 2q(k−1) (1.7)
同様に(1.6)より初期条件を求めると，tが十分大きいとき
q(1) = 1−1
2q(1)
であることから
q(1) = 2
3 (1.8)
である．(1.7)，(1.8)より
q(k) = 4
k(k+ 1)(k+ 2) ∝k
−3
(1.9)
2
ネットワークの分裂に関する性質
2.1
ネットワークの分裂で生成されるグループの数
本節では，前節で定義したPreferential Attachmentで生成されるネットワークの分裂について
考えていく．新しく追加されるノードがセルフループを起こしたときにネットワークの分裂が発生
する．
図3 分裂したネットワーク(t= 20)の例．黄色のノードがセルフループを起こし，分裂を発
生させたノードである．3つのグループに分裂したのでグループ数はN(20) = 3となり，グル
ープ毎の人数はM(1,20) = 12,，M(3,20) = 7，M(7,20) = 1となる．
最初にネットワークの分裂においてどれくらいの数のグループができるのかを考える．
Theorem 2.1. ([12])
このネットワークにおいて，時刻tにおける，分裂によって生成されるグループの数N(t)につ
いて次が成り立つ．
E[N(t)] =
t ∑ k=1
1
2k−1 (2.1)
P(t, z) =E[zN(t)] =
t ∏ k=1
2k−2 +z
2k−1 (2.2)
Proof.
(1.1)より，時刻tに分裂を起こす確率は
1
2t−1であるから，グループの数N(t)はX1，… ，Xt
を確率変数としてP(Xk = 1) =
1
2k−1となるベルヌーイ試行を考えると
N(t) =
t ∑ k=1
図4 E[N(t)]のグラフ．E[N(t)]≈
1
2log(2t+ 1) +γ (γはオイラー定数)と近似できる．
と書くことができる．よって
E[N(t)] =
t ∑ k=1
E[Xk] = t ∑ k=1
1 2k−1
となり，(2.1)が得られる．また，
E[zN(t)] =
t ∏ k=1
E[zXk]
=
t ∏ k=1
(
2k−2 2k−1z
0+ 1
2k−1z
1
)
=
t ∏ k=1
2k−2 +z 2k−1
となり，(2.2)が得られる．この式から(2.1)を導くこともでき，両辺をzで偏微分すると
∴ ∂
∂zP(t, z)|z=1= ∂ ∂z(
t ∏ k=1
2k−2 +z 2k−1 )|z=1
= 1
2t−1 +
1
2(t−1)−1 +… + 1 2·1−1
=
t ∑ k=1
1 2k−1
となるが，
∂
∂zP(t, z)|z=1= ∂ ∂z
∞
∑ n=1
Pn(t)zn|z=1=
∞
∑ n=1
nPn(t) =E[N(t)]
2.2
生成されるグループの大きさ
Theorem2.1より，ネットワークのグループ数の増え方を知ることができた．次は分裂によって
発生したグループの大きさについて考えていきたいと思う．分裂は時刻sにセルフループを起こし
たノードを基準に発生する．時刻sに追加されたノードの次数ds(t)について，
E[ds(t)] = t ∏ i=s
2i 2i−1 ≈O
(√
t s
)
が成り立つことが知られているが[8]，各グループの大きさの成長は次数の成長とは異なるものと
なる．
Theorem 2.2.
時刻sに生成されたグループの時刻tにおける人数M(s, t)の期待値について次が成り立つ.
E[M(s, t)|時刻sにグループが生成] =
2t+ 1 2s+ 1 ≈O
( t s ) (2.3) Proof.
時 刻sに セ ル フ ル ー プ を 起 こ し ，作 ら れ た グ ル ー プ を 考 え る ．時 刻 ｔ で そ の グ ル ー プ の 人 数
がn人である確率をQn(t)とすると，t≥sとして
Qn(t) =
2(n−1)
2t−1 Qn−1(t−1) +
2t−1−2n
2t−1 Qn(t−1) (n≥2) Q1(t) =
2t−3
2t−1Q1(t−1)
が成立する．この両辺にnをかけ, 和をとることで
∞
∑ n=1
nQn(t) =
∞
∑ n=2
2(n−1)
2t−1 nQn−1(t−1) +
∞
∑ n=1
2t−2n−1
2t−1 nQn(t−1)
=
∞
∑ n=1
2n(n+ 1)
2t−1 Qn(t−1) +
∞
∑ n=1
2t−2n−1
2t−1 nQn(t−1)
= 1
2t−1
∞
∑ n=1
(2n2+ 2n−2n2+ (2t−1)n)Qn(t−1)
= 1
2t−1
∞
∑ n=1
(2t+ 1)nQn(t−1)
= 2t+ 1 2t−1
∞
∑ n=1
nQn(t−1)
より，
E[M(s, t)|時刻sでグループ生成] =
2t+ 1
2t−1E[M(s, t−1)]
が得られる．E[M(s, s)|時刻sでグループ生成] = 1であるから
E[M(s, t)|時刻sでグループ生成] =
t ∏ k=s+1
2k+ 1 2k−1 =
2t+ 1
2s+ 1 (2.3)
よって，グループの大きさは時刻tに比例し，セルフループを起こしたノードの到着時刻sに反
比例する．先にセルフループを起こし生成されたグループは大きくなりやすいが，後の方にセルフ
ループを起こし生成されたグループはほとんど大きくならないことがわかる．
この結果をグラフにしたものが，次の図5である．s= 1で生成されたグループとs= 10で生
成されたグループでは大きな差が生まれることが分かる．よって，グループを大きくするには早い
段階でセルフループを起こしたものでないと大きくなりづらい．
図5 E[M(s, t)]のグラフ．グループ生成時刻によって人数には大きな差が生まれる．
統計分析フリーソフト「R」を用いて作成した，図2のネットワークG(250)におけるM(s, t)
の成長グラフが次の図6である．実線が実測値，点線がTheorem2.2で得られた理論値である．全
体的に実測値が理論値を下回っているのは，E[N(250)]≈3であるのに対してグループが5つでき
てしまっていることが原因であると考えられる．遅くに生成されたグループの大きさが早くに生成
されたグループの大きさに近づくことはあるが，超すことは起きていない．この結果においても，
先にセルフループを起こし生成されたグループは大きくなりやすいが，後の方にセルフループを起
図6 図2の ネ ッ ト ワ ー クG(250) に お け る Ms(t)の 成 長 グ ラ フ ．実 線 が 実 測 値 ，点 線 が
Theorem2.2で得られた理論値である．全体的に実測値が理論値を下回っているのは，
E[N(250)]≈3であるのに対してグループが5つできてしまっていることが原因であると考え
2.3
ノードが孤立する確率
分裂を起こす確率はセルフループを起こすノードの到着時刻に依存する．先にセルフループを起
こしたノードは他のノードに選択されやすいが，後の方にセルフループを起こしたノードは選択さ
れにくい．しかし，分裂を起こした後どのノードにも接続されずに孤立する確率はセルフループを
起こした時刻によらず一様となる．
Theorem 2.3.
時 刻 s に 追 加 さ れ た ノ ー ド が 時 刻 t に お い て ，た だ 1 人 の 孤 立 し た グ ル ー プ と な る 確
率R(s)はsによらず一定である．すなわち，次が成り立つ.
R(s) = 1
2t−1 (2.4)
Proof.
時刻sに追加されるノードについて考える．ノードsが孤立するのは，時刻sでセルフループを
起こし，かつ，それ以後のノードがノードsを選択しないときなので
R(s) = 1 2s−1
{
2s−1 2s+ 1·
2s+ 1 2s+ 3·… ·
2t−3 2t−1
}
= 1
2s−1
t ∏ k=s+1
2k−3 2k−1
= 1
2s−1 · 2s−1 2t−1
= 1
2t−1
2.4
後から生成された小さなグループの成長
人数の増え方はTheorem2.2より，E[M(s, t)|時刻sでグループ生成] =
2t+ 1
2s+ 1であり，先にセ
ルフループを起こしたノードが作ったグループの方が増えやすく，あとの方にセルフループを起こ
したノードが作ったグループはほとんど増えないことが分かった．時間tを十分大きくしたとき，
この期待値は無限大に大きくなるが，特定の系列を考えたときM(s, t)が無限大に大きくなるとは
限らず，特にsが大きく，後の方に生成されたグループについては本当に無限大に大きくなるか，
成長が止まってしまうかは気になるところである．しかし，本節で示される定理より，あとの方に
セルフループを起こしたノードが作ったグループも時間がたてば人数が十分大きくなることが分
かる．
Theorem 2.4.
時刻sでのセルフループで生まれたグループからなるネットワークをGs(t)とする．j≥s+ 1の
とき，時刻jに追加されるノードがGs(t)に含まれるノードを選択するという事象をB(j,s)とし，
ノードjがセルフループを起こす事象はB(s,s)とする．このとき，Gs(t)にノードが無限回くる確
率は1である．すなわち
P
(
lim sup
t→∞
B(t,s)
)
= 1 (2.5)
が成り立つ．
Proof.
B(s+1,s)，B(s+2,s)，… は独立な事象ではないので，Borel-Cantelliの補題[13]を直接使って示 すことはできない．よって，ここでは独立性を用いず直接証明する．
P
((
lim sup
t→∞
B(t,s)
)c)
= 0 (2.6)
を示すことで，(2.5)を示す．
まず，lim
l→∞ P l ∩ k=j (
B(j,s)
)c
= 0を示す．
P
l ∩ j=m
(
B(j,s)
)c
=P((
B(m,s)
)c
)P(B(m+1,s)|
(
B(m,s)
)c
)P(B(m+2,s)|
(
B(m+1,s)
)c
∩(
B(m,s)
)c
)…P(
(
B(l,s)
)c
|
l−1
∩ k=m
(
B(k,s)
)c
)
=
(
1− E[Ms(m)]
2m−1
) (
1− E[Ms(m)]
2m+ 1
)
…
(
1−E[Ms(m)]
2k−1
)
…
(
1−E[Ms(m)]
2l−1
) ≤exp ( − l ∑ k=m
E[Ms(m)]
2k−1
)
(∵∀xに対して，1−x≤e
−x
)
= exp
(
−2m+ 1
2s+ 1
l ∑ k=m
1 2k−1
この変形をまとめると ∴P l ∩ j=m
(
B(j,s))c ≤exp
(
−2m+ 1
2s+ 1
l ∑ k=m
1 2k−1
)
(2.7)
(2.7)でl→ ∞とすると，
l ∑ k=m
1
2k−1 → ∞となることより
lim l→∞ P l ∩ j=m
(
B(j,s)
)c = 0
となる．
また，
l ∩ j=m
(
B(j,s)
)c
はlに関して単調なので確率測度の単調収束定理から
0 = lim
l→∞ P l ∩ j=m
(
B(j,s)
)c =P
∞
∩ j=m
(
B(j,s)
)c
となる．ここで，ド・モルガンの法則から
(
lim sup
t→∞
B(t,s)
)c
= lim inf
t→∞
(
B(t,s)
)c
=
∞
∪ m=s+1
∞
∩ j=m
(
B(j,s)
)c
であるので，Dm=
∞
∩ j=m
(
B(j,s)
)c
とおくと，
(
lim sup
t→∞
B(t,s)
)c
=
∞
∪ m=s+1
Dmであるから，確率測度
の劣加法性から
P
((
lim sup
t→∞
B(t,s)
)c)
=P
( ∞
∪ m=s+1
Dm )
≤ ∞
∑ m=s+1
P(Dm) = 0 (∵任意のmに対し，P(Dm) = 0)
よって
P
(
lim sup
t→∞
B(t,s)
)
= 1−P
((
lim sup
t→∞
B(t,s)
)c)
= 1−P
(
lim inf
t→∞
(
B(t,s)
)c)
= 1
また，Theorem2.4が成立するとき，Theorem2.5が成立し，より遅い時刻にセルフループを起
こしたノードが作ったグループも時間がたてば人数が十分大きくなることが分かる．
Theorem 2.5.
t→ ∞のとき，M(s, t)→ ∞となる．すなわち
lim
t→∞M(s, t) =∞ (2.8)
Proof.
Theorem2.4を書き換えると，
P
(
lim sup
t→∞
B(t,s)
)
=P(
∞
∩ m=s+1
∞
∪ j=m
B(j,s))
=P
( ∞
∩ m=s+1
{
x | ∃a≥m, x∈B(a,s)
} )
=P({
x | ∀b，x∈
{
x| ∃a≥b, x∈B(a,s)
}})
=P({
x | ∀b, ∃a≥b, x∈B(a,s)})
この集合はつまり「どんな自然数bをとっても，それ以上のaが存在して，xがB(a,s)に含まれ
る」ようなxの集合であるから，P
(
lim sup
t→∞
B(t,s)
)
= 1は，「どんな時刻をとってきても，それ
より後の時刻が存在して，その時刻においてB(j,s)が必ず起こる」ということを意味する．つまり，
Gs(t)には確率1でノードが無限回くるのでGs(t)は大きくなり続ける．
よって，(2.8)が成り立つ．□
Theorem2.5から，どの時刻に生成されたグループであっても，グループの人数は十分大きくな
ることがわかる．また，これらから
Corollary 2.1.
任意のT に対して，M(s, t) =T となるtが存在する．
が成立し，どの時刻に生成されたグループであっても，任意の大きさに到達可能であることが分
2.5
グループ構造の確率的同等性
本 節 で は ，分 裂 で 生 成 さ れ た グ ル ー プ 同 士 の 構 造 の 比 較 を 行 い た い ．こ こ で ，こ れ か ら 示 す
Theorem2.6のためにDefinition2.1，Definiton2.2を定義する．
まず，Defnition2.1を定義するために次のLemma2.1を示す．
Lemma 2.1.
min{t≥1|
t ∑
j=l
1B(j,l) ≥i}が空集合でない．すなわち，∀iに対して，
t ∑
j=l
1B(j,l) ≥i
となるtが存在する．
Proof.
Theorem2.4より，
P({
x | ∀b, ∃a≥b, x∈B(a,l)
})
= 1
である．P
(
lim sup
t→∞
B(t,l)
)
= 1は，「どんな時刻をとってきても，それより後の時刻が存在して，
その時刻においてB(j,l)が必ず起こる」ということを意味する．よって，B(j,l)が無限回起こる確率
が1であるので，
t ∑
j=l
1B(j,l)は単調増加であり，lim
t→∞
t ∑
j=l
1B(j,l) =∞である．
よって，∀iに対して，
t ∑
j=l
1B(j,l) ≥iとなるtが存在する．□
Definition 2.1. (Localな時刻)
{
i: 1B(i,l) = 1
}
という時点を集めてGl(t)の時刻tをとり直すことを考える．
i=
t ∑
j=l
1B(j,l)
となるiをGl(t)のLocalな時刻と定義する．すなわち，iはGl(t)の大きさと一致する． ここで，Gl(t)のLocalな時刻がiになった時刻tl(i)は
tl(i) = min{t≥1| t ∑ j=l
1B(j,l) ≥i}
Definition 2.2. (確率的に同等である)([12])
2つのランダムグラフHとH˜があって，H を構成するリンクの集合をE，H˜を構成するリンク
の集合をE˜とする．ただし，互いのインデックスを適当に付け変えて共通にしておく．
このとき，任意のリンクの集合E
′
において
P(E=E′
) =P( ˜E=E′
)
が成立するとき，HとH˜が確率的に同等であるといい，H≃H˜で表す．
Definition2.1，Definiton2.2 の G(8) に お け る 例 を 示 し た も の が 図 7 で あ る ．イ ン デ ッ ク ス
がi(j)であるGl(8)に含まれるノードは時刻i，Localな時刻jにGl(8)に追加されたことを意味 する．この状態において，G1(8)，G2(8)，G3(8)のLocalな時刻はそれぞれ3，3，2である．ノー
ドが追加されたLocalな時刻でインデックスをふり直すと，ノードのインデックスは図の括弧内の
数字になる．例えば，ノード2はインデックスが1にふり直される．
G1(8)を構成するリンクの集合をE1(8)，G2(8)を構成するリンクの集合をE2(8)とする．イン
デックスがふり直されているので，E1(8) ={(1，2)，(1，3)}，E2(8) ={(1，2)，(1，3)}となる．
よって，E1(8) =E2(8)である．
図7 G(8)における例．インデックスがi(j)で
あるGl(8)に含まれるノードは時刻i，Localな
時刻jにGl(8)に追加されたことを意味する．
図8 大きさ3のネットワーク構造．インデッ
クスが(i)であるノードはLocalな時刻iに追
加されたことを意味する．
また，大きさ3のネットワークの構造は図8の2通りあり，それぞれ確率は
3 4，
1
4である．すな
わち，
P(E1(8) ={(1，2)，(1，3)}) =P(E1(8) ={(1，2)，(1，3)}) =
3 4
P(E1(8) ={(1，2)，(2，3)}) =P(E1(8) ={(1，2)，(2，3)}) =
1 4
である．よって，Definition2.2より
G1(8)≃G2(8)
以上を用いてTheorem2.6を示す．異なる時間に生成されたグループもLocalな時刻が一致す
るときは確率的に同等である．
Theorem 2.6.
∀iに対して
Gl(tl(i))≃Gm(tm(i)) (2.9)
が成立する．
Proof.
ノードが追加されたLocalな時刻でインデックスをふり直す場合を考える．
帰納法を用いて示す．最初に，Gl(tl(1))とGm(tm(1))を構成するリンクの集合は
{(1，1)}，{(1，1)}であるから，i= 1のときは成立する．
次に，i=kのときの(2.9)の成立を仮定し，i=k+ 1のときの(2.9)の成立を示す．
Gl(tl(k)) を 構 成 す る リ ン ク の 集 合 を El(tl(k))，Gm(tm(k)) を 構 成 す る リ ン ク の 集 合 をEm(tm(k))とすると，仮定は任意のリンクの集合Fkに対して，ノードが追加されたLocalな時 刻でインデックスをふり直した場合に
P(El(tl(k)) =Fk) =P(Em(tm(k)) =Fk) (2.10)
であり，示したいことは 任意のリンクの集合Fk+1に対して，
P(El(tl(k+ 1)) =Fk+1) =P(Em(tm(k+ 1)) =Fk+1) (2.11)
である．
任意にリンクの集合F
′
k+1 = {e1，… ，ek，ek+1}をとる．また，これと同じe1，… ，ekを用い てF
′
k ={e1,…, ek}とおく．このとき，Gl(tl(k))に新たに加わるリンクをe，Gm(tm(k))に新た
に加わるリンクをe
′
とすると，同じ大きさのネットワークへの接続時点を考えているので
P(e=ek+1|El(tl(k)) =Fk′) =P(e
′
=ek+1|Em(tm(k)) =Fk′) (2.12)
であり，
P(El(tl(k+ 1)) =F
′
k+1) =P(El(tl(k)) =F
′
k)·P(e=ek+1|El(tl(k)) =F
′
k)
=P(Em(tm(k)) =F
′
k)·P(e=ek+1|El(tl(k)) =F
′
k) (∵(2.10))
=P(Em(tm(k)) =Fk′)·P(e
′
=ek+1|Em(tm(k)) =Fk′) (∵(2.12))
=P(Em(t1(k+ 1)) =Fk′+1)
よって，(2.11)は成立．よって，(2.9)が導かれる．□
以上より，異なる時間に生成されたグループもLocalな時刻が一致するときは確率的に同等であ
ることが分かった．どの時間に生成されたグループも生成する速さは違うが，同じ構造を保って成
2.6
各グループの次数分布
前節では，各グループが同じ構造を保って成長していくことが分かったが，本節では，大きさ
が十分大きくなった時の各グループの次数分布を求めたい．Theorem1.1と同様の照明を行うこ
とで，各グループは十分大きくなったときはスケールフリーネットワークとなっていることがわ
かる．
Theorem 2.7.
Nk,l(t)をGl(t)に含まれる次数kのノードの総数とする．このとき，次が成り立つ．
lim
i→∞
Nk,l(tl(i))
i =
4
k(k+ 1)(k+ 2) (2.13)
ここで，Lemma2.1よりt→ ∞のとき，i→ ∞であることを用いた．
このとき，Gl(t)はスケールフリーネットワークである．すなわち，ノードを1つ選んだときの
そのノードの次数がkである確率をP(k)とすると，
P(k) = lim
i→∞
Nk,l(tl(i))
i =
4
k(k+ 1)(k+ 2) ∝k
−3 (2.14)
定理2.7を証明するにあたって，Lemma2.2の成立を認める．
Lemma 2.2. [11]
Nk,l(t)をGl(t)に含まれる次数kのノードの総数とする．このとき
lim
i→∞
Nk,l(tl(i))
i =r(k) (2.15)
と収束値を持つ．
Proof(Theorem2.7).
新 し い ノ ー ド がGl(t)に 含 ま れ る ノ ー ド を 選 択 す る と い う 条 件 の も と で ，Gl(t) に 含 ま れ る 次
数kのノードを選択するという事象をAkとすると
Nk,l(tl(i))−Nk,l(tl(i−1)) = 1Ak−1−1Ak
(k≥2) (2.16)
N1,l(tl(i))−N1,l(tl(i−1)) = 1−1A1 (2.17)
k≥2のとき，(2.16)より
E[Nk,l(tl(i))−Nk,l(tl(i−1))] =E[1Ak−1−1Ak]
= k−1
2i−2E[Nk−1(tl(i−1))]− k
2i−2E[Nk(tl(i−1))]
∴E[Nk,l(tl(i))−Nk,l(tl(i−1))] = k−1
2i−2E[Nk−1(tl(i−1))]− k
2i−2E[Nk(tl(i−1))]
となる．Lemma2.2より lim
t→∞
Nk,l(tl(i))
i =r(k)と収束値を持つので，十分大きなtに対して
r(k) = k−1
よって
r(k) = k−1
k+ 2r(k−1) (2.18)
同様に(2.17)より初期条件を求めると，tが十分大きいとき
r(1) = 1−1
2r(1)
であることから
r(1) = 2
3 (2.19)
である．(2.18)，(2.19)より
r(k) = 4
k(k+ 1)(k+ 2) ∝k
−3 (2.20)
を得る．□
以上より，分裂で発生した各グループも時間がたてばスケールフリーネットワークとなっている
3
おわりに
本研究は，Preferential Attachmentで生成されるネットワークの分裂に関する性質について考
察し，分裂で発生するグループの数の増え方や，ノードが孤立する確率，グループサイズの増え方
が明らかになった．特に，グループサイズは生成時刻に反比例するので後から生成されたグループ
はほとんど大きくならないようにみえるが，時間がたてば十分大きくなるということが分かった．
また，異なる時間に生成されたグループも同じ大きさのときは構造が確率的に同等であり，同じよ
うな育ち方をし，最終的にスケールフリーネットワークとなることを示すことができた．
この結果は，どんな小さなグループも必ず大きくなることを示しており，どんな少数派のグルー
プも必ず大きくなれることを示している．先に生成されたグループの方が大きくなりやすく，全体
的に有利なようにも思えるが，後から生成されたグループは先に成長しているグループの成長の様
子がわかるため，未来を予測できるという点でメリットがあると考えることもできる．
今後の展望としては，本モデルはノードが次々と増えていくモデルであったが，現実世界では
ノード数には限りがある場合が多い．本研究の成果をより生かすには，この結果をノードの離脱も
含める場合に拡張し，ノード数を制限することが考えられる．このようなモデルにおいて，グルー
プの数の増え方はすでに研究されている[12]．しかし，グループの大きさに関する性質はまだ明ら
謝辞
本論文を作成するにあたり，適切かつ懇切丁寧な研究指導を頂きました，指導教官である早稲田
大学の豊泉洋教授に深く感謝を申し上げます．また，シミュレーションプログラムの提供及びアド
バイスを行っていただいた早稲田大学理工学術院総合研究所の佐藤真史氏に深く感謝を申し上げ
参考文献
[1] Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespig-nani Rev. Mod.”Epidemic processes in complex networks”. Phys. 87, 925 Published 31
August 2015
[2] Thilo Gross, Carlos J. Dommar D’ Lima, and Bernd Blasius“ Epidemic Dynamics on an
Adaptive Network” (2006).
[3] Hiroshi Toyoizumi,“ Generating Uncorrelated and Markovian Complex Networks” , (2012).
[4] 増田直紀，今野紀雄：複雑ネットワーク基礎から応用まで，近代科学社，(2010).
[5] Jnos Trk, Gerardo Iiguez, Taha Yasseri, Maxi San Miguel, Kimmo Kaski, and Jnos Kertsz
,“ Opinions, Conflicts, and Consensus: Modeling Social Dynamics in a Collaborative
En-vironment” , Phys. 110, 088701 Published 19 February 2013
[6] Junichi Yamanoi , Hiroki Sayama ,“ Post-marger cultural integration from a social network
perspective : a computational modeling approach” , Computational and Mathematical
Organization Theory, pp. 516-537, 2013.
[7] Xiao Zhang,Cristopher Moore,and M. E. J. Newman ”Random graph models for dynamic networks”(2016)
[8] B. Bollollas and O. Riordan, Combinatorica 24, 5 (2004).
[9] S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Physical review letters 85, 4633 (2000).
[10] Kwak, H., Lee, C., Park, H. and Moon, S.: “ What is Twitter, a social network or a
news media?,” Proceedings of the 19th international conference on World wide web, ACM
(2010)
[11] R. Durrett, Random graph dynamics, vol. 20 (Cambridge Univ Pr, 2007).
[12] H. Toyoizumi and T. Shimomura, “ A Toy Model of Preferentially-Attached Networks
with Break-Ups” ,第34回待ち行列シンポジウム(2017).
![図 4 E[N (t)] のグラフ． E [N (t)] ≈ 1 2 log(2t + 1) + γ (γ はオイラー定数 ) と近似できる． と書くことができる．よって E[N (t)] = t ∑ k=1 E[X k ] = t ∑ k=1 1 2k − 1 となり， (2.1) が得られる．また， E[z N(t) ] = t ∏ k=1 E[z X k ] = t ∏ k=1 ( 2k − 22k − 1 z 0 + 1 2k − 1 z 1 ) = t ∏ k=1 2k − 2 + z2k −](https://thumb-ap.123doks.com/thumbv2/123deta/6704948.210984/9.892.236.641.199.455/グラフγオイラーできるできる=∑EXとなりられる−.webp)
