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

(1)

?

著者浜口幸弘

雑誌名明治学院大学経済研究 = The papers and proceedings of economics

巻 156

ページ 11‑29

発行年 2018‑07‑31

その他のタイトル Diameter of a scale‑free randam graph

URL http://hdl.handle.net/10723/00003417

(2)

1．はじめに

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

　さて前稿（浜口（2017））では，Bollobás and Riordan （2004）のモデルを検討していくつかの課題を提示した．今回は第 2 段階として，このランダムプロセスから生成されるグラフG₁ⁿを対象にして，

G1n上の単調パスの存在確率およびG1nに含まれる最大パスの長さを近似評価する．結果として，G1n （および一般的な木も含む）の特徴的な大きさを表すような定理 1 および定理 2 を導出した．

2．概念とモデルの定義

　Bollobás and Riordan （2004）はスモールワールドをランダムグラフでモデル化して，その直径の下限と上限を理論的に導出している．そのモデル化についての概略は，以下のとおりである．グラフG に新しい頂点を 1 個ずつ加えるとき，その頂点からm本の辺をグラフGに接続する．このとき，多重辺とループも認めるものとする．

　さて，m＝1 の場合について，このことを厳密に定式化すると以下のようになる．グラフに追加していく頂点列をv1，v2，…と固定し，グラフGにおける頂点vの次数をd_G（v）と記す．そしてランダム

『経済研究』（明治学院大学）第 156 号　2018 年

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

浜　口　幸　弘

(3)

グラフのプロセス（G₁^t）_t_{≥ 0}を次のように帰納的に定義すると，｛ v_i：1≤ⁱ≤^t｝上のグラフG₁^tが構成される．すなわち，まず 1 個の頂点と 1 つのループを持つグラフG11から出発する．そして，G1t^－1まで構成されたとき，次に追加する頂点v_tとv_i∈V（G₁^t^－1）を 1 本の辺で結ぶ．このとき頂点i （確率変数である）は次のようにランダムに選択される．

．

　これは，Barabási and Albert （1999）のモデルを定式化したものとなっている．また，preferrential attachment として，ネットワーク理論の基礎になる式である．

　m＞1 の場合については，一度にv_tからm本の辺がG₁^t^－1に接続される．よって，プロセス（G_m^t）については，プロセス（G₁^mt）において，最初の頂点からm個の頂点ごとに統合して 1 個の頂点にすれば（G_m^t）が得られることになる．また，以下では，頂点v_iをその添え字の番号iで表し，数直線上の閉区間［1, n］内に位置すると考える．そして，このグラフにおけるi₀を始点とし，i_kを終点とするパスをi₀i₁…i_kと記す（パスi₀→i_kとも記す）．このとき，始点からの頂点の並びがi₀＞ⁱ1＞^…＞ⁱ_k^と

なるような，頂点番号が単調に減少するパスを，本稿では単調パスと記す．ここで，頂点選択の試行の順番とは逆の並びになることに注意する．

　さて，G₁^tは［t］＝^{｛ 1，2，…，}^mn｝上のランダムグラフとする．また，追加する頂点jが接続されるグラフ内の頂点をɡ_jとして表す．そして，ランダムグラフの頂点iとjが辺で接続される事象をA_{i, j} と記す．今回は頂点数mnの木を対象にするので，mnをnと置き換えて考える．すなわち，グラフ G1nを対象にする．

3．ランダムモデルによって生成される木の性質

　Bollobás and Riordan （2004）は，確率 P（ɡ_j＝ⁱ）の大きささを評価する補題を導出している．本稿では，その評価量をもう少し詳細に導くことにする．なお，補題の（2）に関しては，i＜j＜kという条件から，ɡ_j＝ⁱ^か否かは^G1k^－1のもとで確定するので，浜口（2017）の指摘は誤りである．よって，Bol- lobás and Riordan （2004）の証明方法を踏襲する．

補題 1

（1）　1≤i＜jのとき，ある定数c1＞^{0 および}c2＞0 に対して，以下の式が成り立つ．

　　　　　　　　　．　また，以下のようにも表せる．

　　　　　　　．

（2）　1≤i＜j＜kのとき，ある定数c1＞^{0 および}c2＞0 に対して，以下の式が成り立つ．

　　　　　　． P（i＝^s^）＝

s＝t 1/^（2t－^1）

d_G₁^t^－_（¹ s）/^（2^t－^1）

⎭―⎬―⎫ 1≤^s≤^t－¹

≤P（ɡ_j＝i）≤ c₂

ij

c₁ ij

P（ɡ_j＝ⁱ^）＝₂¹_ij

（（

¹^＋^O ¹i

））

≤^P^（^ɡ_j＝ⁱ^{, ɡ}_k＝ⁱ^）≤_i^c_jk¹ c₂

jk i

(4)

　また，以下のようにも表せる．

　　　　　　　　．証明

（1）　グラフの構成プロセス（G₁^t）を考える．G₁^tは確率変数である．また，グラフG₁^tにおける頂点i の次数をd_{t, i}＝d_G（₁^t i）と記す．プロセス（G₁^t）の定義から，以下となる．

．　このとき，t＞iに対して，d_{t, i}＝d_t_－1，_i＋_｛I _ɡ_t_＝_i_｝となるから，

　　　　　　　．　上式の両辺の期待値をとると，

　　　　　　．

　ここで，E（d_{t, i}）の代わりに，μ_{t, i}と記すものとする．さて，d_{i, i}は 1 または 2 をとるので，

となり，t≥ⁱ^{に対して，}

となる．そして，μ_{t, i}の大きさを近似評価するために，以下の不等式を利用する．

　　　　　　0≤x≤1 に対して，　　　　　　　　　　． 0≤^x≤^{1 に対して，}^log^（1－^x^）≤ －^x^および

　　　　　　に対して，－x－x²≤^log^（1－x）．

　ここで，関数　　　　　　（x≥1）は単調減少するから，以下の式が成り立つ．

i≥^{2 の場合，}

P（ɡ_j＝i, ɡ_k＝i）＝₂_i¹_jk

（（

¹^＋^O ¹i

））

P（ɡ_t＝i|G₁^t^－¹）＝ ^d^t^－¹^,ⁱ/（2t－^1）^t＞i 1/^（2i－^1）

⎭―⎬―⎫ t＝i

E（d_t,i|^G1t－1）＝^d_t_－1, i＋^d_t_－1, i/（2t－^1）＝

（

¹^＋2t－¹ ¹

）

d_t_－_1,_i

E（d_t_,_i）＝

（

¹^＋₂_t_－¹ ₁

）

^E^（^d^t^－¹^,ⁱ^）

μ_i_,_i＝₂_i²－ⁱ ¹

μ_t_,_i＝ ^t

r=i

∏（

¹^＋2r－¹ ¹

）

x－₂^x²≤^log^（1＋x）≤x

0 ≤x≤¹/² y＝^log

（

¹＋2x－¹ ¹

）

log μ_t_,_i＝

Σ

_r_＝^t_ilog

（

¹^＋2r－¹ ¹

）

^≤

^∫

i^t－1^log

（

¹^＋2x－¹ ¹

）

dx log 2xdx－ log（2x－^1）dx

∫

_i^t_－₁

∫

_i^t_－1

＝

＝₂¹ _i^t _i¹ ²^t－₂ ¹

2 2i－³ log －^（i－^1）log

（

1－

）

2t

1－1

（）

－ log

2i 1－ 3

（）

＋ log

(5)

　　　　　　　　　　　　　　　． i＝^{1 の場合，}

　　　　　　　　　　．　一方，i≥^{1 に対して，}

　　　　　　　　　　．　まとめると，i≥^{2 の場合，}

　　　　　　．　また，i＝^{1 の場合，}

t^1/2e^1/8＋1/（4^t^）－1/（2^t²^）≤^μt，1≤²^1/2^t^1/2^e^1/2－1/（8^t²^）^．

　したがって，頂点選択における定義式の両辺の期待値をとり，tをj－1 として上述の結果を適用すると，ある定数c₁＞^{0 および}^c2＞0 に対して，以下が成り立つ．

　　　　　　．　また，以下のようにも表せる．

　　　　　　　．

（2）　t＞^j＞ⁱ^{とする．まず，}^d_{t, i}＝^d_t－1，i＋^I_｛_ɡ_t＝i_｝であるから，以下を得る．

　　　　　　．　そして両辺の期待値をとると，次のようになる．

　　　　　　　．

　また，　　　　　　であるから，これを上式の辺々に加えて，μ_{t, i}＝^E（d_{t, i}²）＋^E（d_{t, i}）

（（）

it ¹^/²^e⁹^/^（4ⁱ^）^－¹^/ⁱ²^－¹^/^（8^t²^）

）

≤log

log μ_t,₁＝

Σ

_r_＝^t ₁^log

（

¹^＋2r－¹ ¹

）

^≤^log²^＋

^∫

¹^t^log

（

¹^＋2x¹－¹

）

^dx

2 log2

2 log t

2 2t－¹

＝＋－ ^log

（

¹－₂¹_t

）

≤^log^（2¹^/²t¹^/²e¹^/²^－¹^/^（8^t²^））

∫

log μ_{t, i}≥ ^t＋_i ¹^log

（

¹^＋2x－¹ ¹

）

^dx

＝₂¹log _i^t ＋^（^t＋^1） ²^t＋₂ ¹

1t 1＋

（）

log ₂t

1＋1

（）

－ log ²ⁱ－₂ ¹

2i 1－ 1

（）

＋ log

（（）

it ¹^/²^e¹^/^（4^t^）^－¹^/^（2^t²^）^＋¹^/^（8ⁱ²^）

）

≥log

≤^μ_t,i≤ it

（）

^e¹^/^（4^t^）^－¹^/^（2^t²^）^＋¹^/^（8ⁱ²^） it

（）

^e⁹^/^（4ⁱ^）^－¹^/ⁱ²^－¹^/^（8^t²^）

1/2 1/2

≤^P^（^ɡ_j＝ⁱ^）＝ ≤ c₂ μ_j_－₁_,_i

2j－¹ ij

c₁ ij P（ɡ_j＝ⁱ^）＝₂¹_ij

（（））

¹＋O ¹_i

2

2t－¹ ²t－¹ d_t_－₁_,_i

（）

E（d_{t, i}²

|

G₁^t^－¹）＝d_t_－₁_,i² 1＋＋

2

2t－¹ ²t－¹

（）

E（d_{t, i}²）＝ ¹＋ ^E^（^dt－¹,i²）＋ ^E^（^d^t^－¹^,ⁱ^）

1 2t－¹

（）

E（d_{t, i}）＝ 1＋ ^E^（^d_t_－1,i） ^（2）

(6)

と記せば，以下を得る．

　　　　　　　．

　ここで，d_{i, i}は 1 または 2 をとるので，　　　　　となり，以下を得る．

　　　　　　．　さて，頂点選択における定義式から，

　　　　　　となるので，両辺の期待値をとると，

　　　　　　　．　ところで，

　　　　　　となるので，

両辺の期待値をとると，

　　　　　　　　　．

　　　　　　は，（1）と同様に評価できるので，i≥1 に対して，以下の式を得る．

　　　　　　．　一方，k＞^j＞ⁱ^{に対して，}

　　　　　　　　となる．このとき，両辺の期待値をとると，

　　　　　　．　そして上述の E（d_{t, i}_｛Iɡ_j＝i｝）において，tをk－1 とすれば，主張を得る．□

　次に，辺が生成される事象間の同時確率に関する性質を表した Bollobás and Riordan （2004）の補題 2

2t－¹

（）

μ^（2）_{t, i}＝ ¹＋ μ^（2）_t_－₁_,_i 2i－¹

4i＋² μ^（2）_{i, i}＝

2 2t－¹

（）

μ_{t, i}＝ ¹＋ ₂_r－² ¹ ²^t＋¹

2i＋¹⁴ⁱ＋²

2i－¹

（

¹^＋

）

（2） μ（2）_t_－₁_,_i＝ ^t ^μ（2）i,i ＝

r＝i

∏

＋1

（）

²^j－¹

d_j_－_1,_i E ^dj, i_｛I_ɡ_j_＝_i_｝

|

^G¹^j^－¹＝（d_j_－₁_,_i＋1）

（）

²^j－¹

E d_{j, i}_I ＝ ^μ^（2）^j^－¹^{, i} ＝_（2_i－⁴^1）ⁱ^（2＋²i＋^1）

｛^ɡj＝i｝

（）（

²^t－¹

）

d_t_－_1,_i

E ^dt, i_｛I_ɡ_j_＝_i_｝

|

^G¹^t^－¹＝^d_t_－1,i＋ _｛I_ɡ_j_＝_i_｝

）

（

E d_{t, i}_｛I_ɡ_j_＝_i_｝^＝

（

¹＋²^t－¹ ¹

）

^E

（

^d^t^－^1,ⁱ^｛^I^ɡ^j^＝ⁱ^｝

）

（

E d_{j, i}

（

＝^…＝

r＝j＋1

t ¹＋²^r－¹ ¹

）

∏

^｛^I^ɡ^j^＝ⁱ^｝

）

t

r

^Π

＝j＋

（

¹¹^＋²^r－¹ ¹

）

4i＋² _e₁_/_（4_t_）_－_1（2_t2）－⁷/^（8j）－^1（16j²）≤^E（^d_t, iⅠ_{_ɡ

j＝i}）

（2i－^1）^（²ⁱ＋¹^）

（

^tj

）

¹^/²

4i＋² _e₁_/_（4_j_）_－₁_/_（8_t2）

（2i－^1）^（²i＋¹

（

^）^t^j

）

¹^/²

≤

P（ɡ_j＝^{i, ɡ}_k＝ⁱ|G　）^k¹^－¹ ＝^I_{_ɡ_j_＝_i_}^P（ɡ_k＝ⁱ^|G　 ^k¹^－¹）＝^I_{ɡ_j_＝i}2k－¹ d_k_－_1,_i

2k1－¹

P（ɡ_j＝i, ɡ_k＝i）＝ E（d_k_－_1,_iI_{_ɡ_j_＝_i_}）

(7)

を示す．なお，本稿ではその証明ではなく，補題の意味を直観的に理解できる説明を与えることにする．

補題 2（Bollobás and Riordan （2004））

　事象EとE′を次のように設定する．

　　　　　　　．

　このとき，すべてのtに対して，i_t＜j_tおよびi′_t＜j′_tである．そして集合｛i₁，…，i_r｝と｛i′₁，…，

i′_r′｝が共通要素をもたないとき，以下の式が成り立つ．

P（E∩E′）≤P（E）P（E′）.

解説

　事象Fを　　　　　　　とし，頂点の集合V_tを　　　　　　　とする。確率の基本法則から，以下の式が成り立つ。

　　　　　　　 . また，以下の式が成り立つ。

　　　　　　 .

　これは，どちらの条件付確率もj_tは　　　　　以外の頂点に接続するという条件は同じなので，j_t′

（1≤t≤r′）の接続する頂点を選択する際，両式でi_t^′の次数の確率分布は同じになるということによる。

したがって，以下の式を得る。

　　　　　　.

　このとき，　　　　　　ということが予想されるので，主張は成り立つと言える。□

　ここで，プロセス（G₁^t ）_t_{≥ 0}において，頂点iが自分自身を選択しない，すなわち，ループを持たないように頂点選択のモデルを若干変更して，単調パスi0i1 … i_kの存在する確率P（A_i_0,_i₁∩…∩A_i_k－1, i_k）を考える。このとき，事象A_i_0,_i₁∩…∩A_i_t－2_,_i_t－1と事象A_i_t－1_,（2_i_t ≤^t≤^k^{）は独立となるので，}^P^（^A_i_0,_i1

∩…∩A_i_{k－1 ,}_i_k）＝^P^（A_i_0,_i₁）…P（A_i_k－1, i_k）が成り立つ。このモデルの場合については，次回に議論する。

　次に以下では，各頂点を数直線上の閉区間［1, n］上に位置付けて考える．そして［1, n］上の区間 I_kを［a＋^Δ^（k－^1）＋^1，a＋^Δk］と定義する．ここで，kは 1≤k≤^（n－a）/^Δ^{を満たす整数である．}

　さて補題 1 と補題 2 を適用して，単調パスに関する基本的な補題を以下に与える．

補題 3

（1）　a＞^{0 とし，Δ}²＝^o^（^a^）かつ^k^{は 2}≤^k≤^（^n－a^）/^Δを満たす整数とする．このとき，区間I_kに含まれる任意の頂点は，I_k－1に含まれるどの頂点にも接続しない．

∩

E＝｛r ɡ_j_t＝i_t｝，E′＝｛ɡ_j_t_′＝i_t′｝ t＝1

r′

t＝1

∩

∪

F＝^r ɡ_j_t∈｛i₁，…，i_r

t＝

｛

1 ′ ′′^｝

｛

^V^t^＝^V

（

^G

）

¹^jt^－¹

P（E′）＝^P^（^F^）^P^（^E′|F）＋

（）

¹^－^P^（^F^）^P

（

^E′^|

∩

t＝^r

｛

1 ^ɡ^j^t^∈^V^t^｛^\ ⁱ¹^′^,^…^,ⁱ^r^′′^｝

｝）

∩

t＝^r

｛

1 ^ɡ^j^t^∈^V^t^｛^\ ⁱ¹^′^,^…^,ⁱ^r′^′ ｝

｝）

^＝^P^（^E′^|^E^）

P

（

^E′^|

′

｛i₁′，…，i_r′｝

P（E′）－^P^（^E′^|^E^）＝^P^（^F^）

（

^P^（^E′^|^F^）^－^P

^（

^E′^|

^∩

^t^＝^r

^｛

¹ ^ɡ^j^t^∈^V^t^｛^\ ⁱ¹^′^,^…^,ⁱ^r′^′^｝

^｝ ^））

P（E′|F）≥^P

（

^E′^|

^∩

t＝

｛

1 ^ɡ^j^t^∈^V^t^｛^\ ⁱ¹^′^,^…^,ⁱ^r^′′^｝

｝）

r

(8)

（2）　a＞^{0 とし，}^mは 2 以上の整定数で，かつΔ＝^o^（^a^（^m^－1）/^m^{）のとき，長さ}^m^{以上の単調パスは，}

1≤k≤^（n－a）/^Δを満たすほとんどすべてのI_k内には存在しない．

証明

（1）　区間I_kに含まれる頂点jが，I_k－1に含まれる頂点iに接続する事象をA_{i, j}とする．このとき，区間I_kに含まれる頂点が，I_k_－1に含まれる頂点に接続する確率は，補題 1 を用いて以下のように評価できる．ある正の定数cに対して，

　　　　　　　．

（2）　確率変数X_i₀をi₀を始点とするI_k内の長さmの単調パスの個数とする（なお，単調パスはコンポーネントとは限らない）．また，X^（^k^）をI_k内の長さmの単調パスの個数とし，X_i₀_i₁_…_i_mをI_k内の頂点i₀＞ⁱ1＞^…＞ⁱ_m^{に対して，単調パス}ⁱ0 i₁…i_mが存在すれば 1，そうでなければ 0 をとる確率変数とする．さらに単調パスi₀i₁…i_mがI_kに含まれることをi₀i₁…i_m⊂I_kと表し，A_{x, y}をI_k内の頂点xとyが接続する事象とすれば，補題 1 と 2 を用いて以下を得る．

　　　　　　であり，ある正の定数cに対して，

　　　　　　　　　　　　　　　　　　.

　ここで，　　　　　とする．ただし，K＝^（n－a）/^Δである．このとき，以下を得る．

　　　　　　　　　　　　　．

よって，Markovの不等式から主張を得る．□

　例えば，a＝^logⁿとすれば，補題 3 の（1）の条件は，Δ²＝^o^（^logⁿ^），^{（2）の条件は，}^Δ＝^o^（（^logⁿ^）^（^m^－1）/^m^）

となる．

（k^）

i

∪

∈I_k_－₁

（

_j_∈_I ^Aⁱ^，^j

∪

k ^≤_i_∈_I k－1

∑ ∑

_j_∈_I

k

（k）

）（

^Aⁱ^，^j ^≤^c_i_∈_I

k－1

∑ ∑

_j_∈_I

k

（k）

）

¹_ij

P P

c ^a^＋^∆k ¹ dx ^a^＋^∆^（^k^－^1） c∆² a＋∆（k－^2）

x

a＋∆（k－1）

∫

_a_＋_∆_（_k_－_2） ¹_x dx≤ ＝^o^（1）

∫

≤

（k^）

X_i₀＝

i₀i₁

∑

…i_m^⊂I_k

（k） X^（_i₀^k_i^）₁_…_i_m

∑

_i

0∈I_k

（）

^X^（^k^）＝ ^E

（）

^X^（ⁱ⁰^k^）^＝

∑

_i

0∈I_k _i

∑

0 i₁…i_m⊂I_k

E E

（

^X^（ⁱ⁰^kⁱ^）¹^…ⁱ^m

）

＝

∑

_i

0∈I_k _i

∑

0 i₁^…i_m^⊂I_k^P

（

^A^（ⁱ⁰^k^，^）ⁱ¹^∩^…∩^A^（ⁱ^m^k^－^）¹^，ⁱ^m

）

≤

∑

_i

0∈I_k _i

∑

0 i₁…i_m⊂I_k^P

（

^A^（ⁱ⁰^k^，^）ⁱ¹

）

^…^P

（

^A^（ⁱ^m^k^－^）¹^，ⁱ^m

）

^≤^∆

（

a＋∆（^c∆k－1）

）

^m

X＝

k＝¹

∑

^K ^X^（^k^）

E（X）＝

k＝¹

∑

^K ^E^（^X^（^k^）^）^＝

∑

_k_＝^K₁^∆

（

a＋∆^c∆（k－^1）

）

^m

≤c^m∆

∫

₀^K

∆a 1 x－¹＋

（）

^m^dx

m^c－¹

m∆

＝

∆a

－¹

（）

¹ ^m^－¹^－ ^＝^o^（1）

（

∆n

－¹

（）

¹ ^m^－¹

）

(9)

　次に，本稿の目的である定理 1 および定理 2 を導くために，頂点i_k_＋1のみ区間I_σ＝^［1,^σ^{］に入るよ}

うな，i0を始点とする長さk＋^{1 の単調パス}i0…i_k＋1が存在する確率の上限を評価する不等式を与える．

なお，これに関連して，単調パスの存在する確率の上限および下限を評価する別の補題を次回でも議論する．

補題 4

　c₀およびc₁を正の定数とし，σ→∞とする．頂点i_k_＋₁のみ区間I_σ＝^［1,σ］に入るような，i₀を始点とする長さk＋^{1 の単調パス}ⁱ0…i_k_＋₁が存在する確率P　　は以下の不等式を満たす．

　　　　　　　．

　このとき，　　　　　　（2≤r≤k）である．

証明

　G₁ⁿにおいて，頂点xとyが接続する事象をA_{x, y}とする．そして，頂点i_k_＋₁のみ区間I_σ＝^［1,σ］に入るような，始点をi₀，終点をi_k_＋₁とする長さk＋^{1 の単調パス}ⁱ0…i_k_＋₁が存在する確率をP　　とする．そして補題 1 と補題 2 を用いて以下を得る．

　ある正の定数c₀およびc₁に対して，k＝0 の場合，主張は明らかに成り立つ．k≥^{1 の場合は，}

　　　　　　　　　 k＋¹

i0→I_σ 1

（k－^r^）^！

i^k0^＋→I¹_σ≤ _i 2

0

1＋^c_σ⁰

（）

^k

（ ^） ^∑

_r＝^k0a_r^（log i₀）^k^－^r σ

2c₁ P

e＋¹ e

）

^r^－¹

（

a₀＝^1,a₁＝^0,a_r＝

k＋1

i0→I_σ

P_i^k₀_→^＋_I¹_σ＝^P _n_≥_i

（

Âⁱ⁰^，ⁱ¹^∩Âⁱ¹^，ⁱ²^∩^…^∩Âⁱ^k^，ⁱ^k^＋¹

））

0>^…>

∪

i_k>σ≥i_k_＋₁≥1

（

＝_n_≥_i ^P

（

Âⁱ⁰^，ⁱ¹^∩Âⁱ¹^，ⁱ²^∩^…^∩Âⁱ^k^，ⁱ^k^＋¹

）

0>^…>

∑

i_k>σ≥i_k_＋₁≥¹ i0－¹

≤ ^…

i₁＝

∑

σ＋k _i ⁱ¹^－¹ ^P

（

^Aⁱ⁰^，ⁱ¹

）

2＝

∑

σ＋k－¹ _iⁱ^k^－¹^－¹ k

∑

＝σ＋¹ _i ^σ

k

∑

＋1＝¹ ^P

（

^Aⁱ¹^，ⁱ²

）

^…^P

（

^Aⁱ^k^，ⁱ^k^＋¹

）

≤ c₁ ¹_{2 1}

（

＋^c_σ⁰

）

_i ⁱ⁰^－¹ ^…

1＝

∑

σ＋k _i ⁱ¹^－¹

2＝

∑

σ＋k－¹ _iⁱ^k^－¹^－¹ k

∑

＝σ＋¹ _i ^σ

k

∑

＋1＝¹ _i¹₀_i₁ _i¹₁_i₂^… _i_k¹_i_k_＋₁

（）

^k

＝ _i¹

k＋1

1

2 1

（

＋^c_σ⁰

）

c₁ i₀

i0－¹

i₁＝

∑

σ＋k _i ⁱ¹^－¹ …

2＝

∑

σ＋k－¹ _iⁱ^k^－¹^－¹

k

∑

＝σ＋¹ _i ^σ

k

∑

＋1＝¹

i1₁ i¹₂^…i¹_k

（）

^k

≤ ^c_i¹

0

12 1

（

＋^c_σ⁰

）

_i ⁱ⁰^－¹ ^…

1＝

∑

σ＋k _i ⁱ¹^－¹

2＝

∑

σ＋k－¹ _iⁱ^k^－¹^－¹

k

∑

＝σ＋¹i¹₁ i¹₂^…i¹_k

（

1＋

^∫

1^σ ¹_x ^dx

）

（）

^k

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

?

著者 浜口 幸弘

雑誌名 明治学院大学経済研究 = The papers and proceedings of economics

巻 156

ページ 11‑29

発行年 2018‑07‑31

その他のタイトル Diameter of a scale‑free randam graph

URL http://hdl.handle.net/10723/00003417