論文 ベキ乗則生成に関するサイモン モデルとバラバシ モデル Son Model and Barabas Model on Generang Power Law 鈴木武 ネットワークにおけるベキ乗則の生成について Barabas & Alber (999) から始まる研究が盛んである ここでは それを バラバシ モデル と呼ぶことにする ベキ乗則の研究は 90 年代からみられるが 949 年に Zpf が論文を著してから注目されるようになった その生成メカニズムについて有力なモデルを提示したのは Son (955) である それを サイモン モデル と呼ぶことにする 本稿では サイモン モデルがより一般的であると判断し それを基にバラバシ モデルの解釈と拡張をする Ⅰ では Son (955) が提示し 鈴木武 (007) が精緻化したモデルの要旨を再掲する Ⅱ では バラバシ モデルを記述する () モデルの前提 および() モデルの解 は Barabas & Alber (999) に (3) マスター方程式 は Dorogovsev & Mendes (00) に基づいている Ⅲ では バラバシ モデルをサイモン モデルと同程度に一般化するために 新たに形成されるグループへの要素の配分をα と固定して サイモン モデルと同じ結論を得る Ⅳ では () バラバシ モデルに適応度を加味したモデルを Bancon & Barabas (00a) に基づき記述し サイモン モデルの観点からの解釈を述べる () サイモン モデルの枠組みによる適応度モデルを述べる (3)Bancon & Barabas (00b) は適応度モデルを量子力学のボーズ アインシュタイン短縮に結びつけて ひとり勝ち する状況を説明している 本稿ではそれをエネルギーによる表現ではなく 適応度の表現で記述する Ⅰ サイモン モデル () モデルの前提 あるシステムがベキ乗則を生成するメカニズムを考察する そのために以下の前提をお く システムはいくつかのグループから構成されており 各グループの大きさは要素数で示される グループの大きさ x は 以上の自然数であり x である 初期状態で 以上の大きさをもつグループが a 個存在し 大きさの合計を c とする システムの初期状態において グループは少なくともつ存在し a とする 毎期 要素ずつシステムに参入する 参入にさいし 既存グループのどれかに所属する確率を α とし 既存グループではなく新たに形成されるグループに参入する確率をα とする ただし グループの要素数は 以上であるので 新たなグループは要素数が になるまでシステムには参入しないで待機しているものとする システム外で待機している新たなグループはつとする = の場合には 新たなグループはすぐにシステムに参入することができる
特定のグループがとる大きさの確率分布を考えよう 時点において 第 グループが大きさ x である確率を P (,) x であらわす 時点におけるグループの大きさは から+ cまでの範囲内にある したがって + c x= P(,) x = である ここでつの仮定を設けよう それは Son (955) が初めて提示した仮定である 仮定 システムに参入する要素が既存のどのグループに所属するかは 各グループの大きさに誘引されるものとする 仮定 システムに参入する要素が既存グループではなく 新たなグループに所属する確率はα である ただし 0 α 仮定 は 優先的選択 (preferenal aachen) と呼ばれているので このモデルを 優先的選択モデル と呼ぼう 第 グループにおける時間経過による確率の変化をみよう ( ) 時点から 時点にかけて大きさ x がとる確率の変化は x> の場合 仮定 から P( x, ) P( x, ) = K( ){( x ) P( x, ) xp( x, )} (-) である ただし K ( ) は時間に依存する比例定数とする x= の場合 P(, ) P(, ) = δ( ) K ( ) P(, ) (-) ここで δ () は第 グループが 時点でシステムに参入する確率である () モデルの解 (a) 期待度数時間が経過し となったとき システム全体として大きさ x に関する確率分布がどのようになるか (-) 式 (-) 式をもとに算出しよう 時点において大きさ x を固定し 全グループの確率合計を求めると 時点における大きさ x の期待度数 f(,) x になる 時点におけるグループ数を g () としよう 初期状態においてグループは a 個存在しているので すべてのグループの大きさがであるならば グループ数は+ a になる したがって可能なグループ数は a g () + aである それゆえ 時点における大きさ x の期待 度数は f(,) x = P(,) x (-3) = と表現される また 期待度数を合計すると
+ c + c f(,) x = P(,) x = g () x= = x= であり グループ数に一致する (-) 式を で合計しよう ( ) 時点において 時点のものは実現していないので その 確率は 0 である したがって g( ) g( ) P( x, ) = P( x, ) = = である (-) 式を で合計すると よって g( ) g( ) g( ) P( x, ) P( x, ) = K( ) {( x ) P( x, ) xp( x, )} = = = f( x, ) f( x, ) = K( ){( x ) f( x, ) xf( x, )} (-4) 同様に (-) 式についても である = f(, ) f(, ) = g ( ) K ( ) f(, ) (-5) = g () は 時点においてシステムに新たなグループが参入する確率を意味する 新たな グループがシステムに参入するためには 要素数が 個に達していなければならない 個 に達していない場合はシステム外で待機していると想定している 待機しているケースとしては 要素数が 0 個 個 ( ) 個の 通りの場合があり 各ケースの生じる確率は等しいと考えてよい 時点において要素が新たなグループに所属する確率はα であり ( ) 個の要素がシステム外で待機している場合のみ 新たなグループがシステムに α 参入してくる したがって その確率はとなる それゆえ (-5) 式は α f(, ) f(, ) = K ( ) f(, ) (-6) と書ける (b) 比例定数の計算比例定数 K ( ) を求めよう ( ) 時点における全グループの要素数合計は ( + c) である ただし 新たなグループに所属するためシステムへの参入を待機している要素があるかもしれない その数もここでは含めている グループの大きさは から ( + c) までの可能性がある 該当する大きさがない場合に は その確率を 0 とする K( ) xf ( x, ) は第 要素がシステムに参入するとき すでに x 回生起しているグル
ープのどれかに属する確率である すべての x についてその和をとると 第 要素が既存のどれかのグループに属する確率 ( α) になるので + c K( ) xf ( x, ) = α (-7) x= また すべての大きさを合計すると要素数全体の値になるから + c xf ( x, ) = + c (-8) x= したがって (-7) 式 (-8) 式から α K ( ) = (-9) + c である (c) グループ数についての仮定 相対度数を求めるさい 度数の合計が必要である 本モデルではグループ数と度数の合 計が一致するので グループ数の具体的な表現を考察する必要がある そこで グループ数は参入する要素数に比例するという仮定を設けよう すなわち 時点におけるグループ数 g () は初期状態における a 個のグループ数と 要素数 に比例する部分からなると仮定す る 比例定数を k とすると g( ) = k + a (0 < k ) (-0) と表される 時点における大きさ x の期待相対度数 すなわち確率は f(,) x f(,) x Px (,) = = k + a (-) と表現される (-) 式を用いると (-4) 式は a a + Px (, ) + Px (, ) k k a + = ( α) k ( x ) Px (, ) xpx (, ) + c { } (-6) 式は a a + P (, ) + P (, ) k k a + α = ( α) k P (, ) k + c (-) (-3)
となる (d) 定常状態における確率 としたとき定常状態になると仮定して 大きさ x の確率を求めよう その準備と して (-) 式 (-3) 式に出てくる a + k + c の値について考えてみよう a k c は定数なので が大きな値をとる場合 この値は と みなしてよい 以上のことを考慮すると x > の場合における (-) 式は a a + Px ( ) + Px ( ) = ( α) ( x ) Px ( ) xpx ( ) k k となる したがって 変形して { + ( α) xpx } ( ) = ( α)( x ) Px ( ) ( α)( x ) x Px ( ) = Px ( ) = Px ( ) + ( α) x x + α となる ここで とすると { } (-4) β = (-5) α x Px ( ) = Px ( ) x + β と表現される β は後述するように分布を特徴づけるパラメータとなる (-6) のとき x= の場合における (-3) 式は a a α + P ( ) + P ( ) = ( α) P ( ) k k k したがって α { + ( α) P } ( ) = k 変形して (-7)
α P ( ) = k + ( α) (-8) となる (e) 定数の計算 ここで 定数 である α α = k a α の値について考えてみよう (-0) 式から k 時点までに 個の要素がシステムに参入している そのうち 新たなグループに所属す る要素の期待割合は α である グループを形成するためには 個の要素が必要なので 時 点におけるグループ数の期待値は 初期に存在している a 個を含めて α + a α である したがって g () a= となるので α α = = (-9) k α それゆえ (-8) 式における P ( ) の期待値は となる β P ( ) = = + ( α) + β (-0) (f) 確率分布の計算 (-6) 式 (-0) 式から x Px ( ) = Px ( ) x + β x x = P ( ) x+ β x+ β + β + Γ( x) Γ ( + β + ) β = Γ( ) Γ ( x+ β + ) + β ここで x=, +, +, である (-) 式を大きな値 を単位にして その極限の分布を求めよう (-)
とする = h y + x= ( y = 0, h, h, ) h すなわち h 0 の極限分布は (-) 式を計算すればよい y + Γ Py ( ) Γ + β + h h β l = l h 0 h h 0 y + h Γ Γ + β + + β h h h 得られる確率密度関数は (-3) 式である ( 注 ) (-) 0β 0 f( y) = β ( y+ ) ( y > 0) (-3) 変数 x で表現すると となる β β gx ( ) = βx ( x ) (-4) Ⅱ バラバシ モデル () モデルの前提 このモデルは Barabas & Alber (999) で発表されているので ここではバラバシ モデ ルと呼ぶことにする 考察対象は成長するネットワークであり インターネットにおける ウェブページへのリンク数がどのような分布になるかを議論する グラフ理論の用語では 頂点 ( ウェブページ ) への接続する枝 ( リンク ) の次数である Ⅰ で述べたサイモン モデルの用語では グループ ( 頂点 ) における要素数 ( 枝の次数 ) である ( 注 ) 時点 = 0 では a 個の頂点がある 初期状態における全頂点の枝の次数合計は c である 各時点で頂点がずつ追加され 各頂点から枝が 本ずつ連結される 枝 本につきネットワーク全体の頂点次数の合計はだけ増えるので 各時点で頂点次数は ずつ増加する このモデルでは優先的選択を仮定している すなわち Ⅰ で記述した仮定 である 仮定 新しくネットワークに加わる頂点は 元からいる頂点のどれかと結びつくとき 各頂点の次数に比例して接続する Ⅰ で記述した仮定 は このモデルにはない 仮定 を翻訳すれば α = になる () モデルの解 時点における頂点数を g () としよう 初期状態における頂点数は a 個であり それ以降 時点までに追加された頂点数は 個であるので g () = a+ になる 頂点 の大きさ ( 次数 ) を x とする 仮定 から ある新しい枝が頂点 に結びつく確率は
x Π ( x ) = ( g ( )) x j= j である 時点でのネットワーク全体の次数合計は = (-) x = c + (-) であり が大きくなると x (-3) = と近似できる と x を連続変数として扱うことにして (-) 式と (-3) 式を用いると x x = Π ( x ) = となる (-4) 式を変形して x x = 不定積分を解くと x () (-4) = A (-5) である 頂点 が出現する時点を とする その時点で頂点 の次数は であるので x ( ) = (-6) したがって A = (-7) (-5) 式と (-7) 式から x () = となる 次数分布を求めよう (-8) 式から 頂点次数が x 以下の確率は P[ x() < x] = P > x (-8) (-9) 時刻 では ( a+ ) 個の頂点がある そのうち > を満たすのは 時点 x
+, +,, に加えられた頂点たちで 合計 個ある これらが ( a+ ) 個 x x x の頂点からランダムに選ばれると仮定して ( a+ ) で割ると (-9) 式は P > x = a+ x ( a+ ) (-0) (-0) 式を x で微分すると 確率密度関数は [ () ] P x < x px ( ) = = 3 x x ( a+ ) にすると (-) 3 px ( ) = x ( x ) (-) これはサイモン モデルの (-4) 式に対応しており β = である バラバシ モデルをサイモン モデルで解釈すれば 各時点で新たな頂点が加わるとき 枝が 本加わり 次数 ( 要素数 ) が 追加される その次数が既存の頂点 ( グループ ) に 個 新たな頂点に 個配分される したがって Ⅰ における新たなグループに配分 される確率はα = であり (-5) 式から β = となる (3) マスター方程式サイモン モデルでの記述方式をマスター方程式と呼んでいる Dorogovsev & Mendes (00) はバラバシ モデルをマスター方程式でも記述している これを Ⅰ で用いた記号で記述しよう ( 注 3) 時点に導入された頂点が 時点で次数 x をもつ確率を P (,) x とすると x x P(, x + ) = P( x,) + P(,) x (-3) が成り立つ (-3) 式は (-) 式の特殊なケースであり 時点ではなく ( + ) 時点で記述 α したものである (-9) 式から K () = であるが (-3) 式ではα = とし が大きな + c 値をとっている状態を想定して c を無視している したがって K () = (-4) としている のときの次数分布は
Px ( ) = l = P (,) x から得られると期待している これは (-) 式で g () いる (-3) 式を で合計し (-5) 式を用いると x x ( + ) Px ( ) = Px ( ) + Px ( ) が導かれる したがって x Px ( ) = Px ( ) ( x + ) x + P ( ) = ( x= ) + (-5) = とし の極限をとった式になって (-6) (-7) (-8) が得られる (-7) 式は (-6) 式に (-8) 式は (-0) 式に対応する (-7) 式の漸化式を解 き (-8) 式を代入すると ( + ) Px ( ) = xx ( + )( x+ ) が得られる これは (-) 式に対応する (-) 式に β = を代入して したがって Γ( x) Γ ( + 3) Px ( ) = Γ( ) Γ ( x+ 3) + Px ( ) Γ( x) Γ ( + ) = Γ ( x+ 3) Γ( ) ( + ) = xx ( + )( x+ ) (-9) 3 x (-0) Ⅲ バラバシ モデルに α を導入 バラバシ モデルはサイモン モデルの特殊なケースにあたるので バラバシ モデル をサイモン モデルと同じレベルに一般化しよう 各時点で 本の要素が追加され 既存の頂点に ( α) 本 新たな頂点にα 本が配分 されるとする ただし サイモン モデルと同様に頂点の要素数は 本以上とするので 新たな頂点は要素数が 本に達してから初めて参加するものとする 仮定 が成り立つので ある新しい枝が頂点 に結びつく確率は (-) 式と同じである 時点でのネットワーク全体の次数合計は
x = c + (3-) = であり が大きくなると x 不定積分をすると x () 時点では x = ( α) Π ( x ) = ( α) x と近似できるので (-4) 式に対応する式は = (3-) α = (3-3) A x ( ) = A = (3-4) α (3-3) 式と (3-4) 式から定数 A を消して α x () = となる (3-5) 式は (-8) 式に対応する 次数分布を求めるために (-9) 式に対応する式は α P[ x() < x] = P > x 時点では ( a + k) 個の頂点がある そのうち > x α (3-5) (3-6) を満たすのは 時点 α α +, +,, x x のうちで 実際に加えられた頂点たちであり 合計 k x α 個ある これらが ( a + k) 個の頂点からランダムに選ばれると仮定して ( a + k) で割る (-0) 式に対応する式は α k α k P > = (3-7) x a + k x a + k (3-7) 式を x で微分すると 確率密度関数は
[ ] P x () < x + k α α px ( ) = = x x α a + k にすると (-) 式に対応するのは + α α px ( ) = x ( x ) (3-8) α (3-8) 式で β = とすると サイモン モデルにおける (-4) 式と同じになる α Ⅳ バラバシの適応度モデル () バラバシ モデルのサイモン モデルによる解釈バラバシ モデルの拡張として 次数に比例するだけでなく 各頂点に重みを持った 適応度モデル が Bancon & Barabas (00a) によって提示されている 以下にこれを記述し サイモン モデルの観点から解釈を加える ( 注 4) (-) 式の優先的選択のルールを (4-) 式に拡張する x Π ( x ) = ( g ( )) x j= (-4) 式 (3-) 式に対応するのは x = Π ( x ) = j j x j= x j j 初期条件は (-6) 式 (3-4) 式であるので (-8) 式 (3-5) 式に対応して (4-) (4-) b( ) x () = (4-3) と書ける b( ) は適応度 によってゆらぎが生じるので 集団平均で近似する τ ρ b( ) ax E jxj = d ( ) d 0 j= τ = 0 ax b( ) 0 ρ ( ) d 0 b( ) (4-4) b( ) は新たに追加される枝のうち既存の頂点に配分される割合なので b( ) < である b したがって のとき ( ) 0 となる それゆえ
j= C = x j 0 j ax C C ρ ( ) d 0 b( ) である (-4) 式 (3-) 式に対応するのは x x = C となる (4-3) 式との関係から が言える (4-5) (4-6) b( ) = (4-7) C (-9) 式 (3-6) 式から (-) 式 (3-8) 式までと同様の論理展開により C C ax C 0 + ( ) ρ ( ) 0 px = x d (4-8) となる サイモン モデルの観点から b( ) は新たに追加される枝が既存の頂点に配分される割合 を示していると解釈できる 新たな頂点に配分される割合を α ( ) とするならば b( ) = α ( ) である したがって (4-8) 式は 0 ax + d ( ) 0d ( ) ( ) = 0 ρ ( ) 0 px x d (4-9) 0d ( ) と書ける すなわち 適応度モデルは各適応度によって枝の配分割合を変化させ その期 待値としてベキ指数が生じるモデルと言える () サイモン モデルの枠組みによる適応度モデルもしサイモン モデルの枠組みで 新たな頂点への配分割合をα とする仮定 を条件に 適応度モデルを構成したらどうなるだろうか (-) 式に対応する式は P( x, ) P( x, ) = K( ) ( ){( x ) P( x, ) xp( x, )} (4-0) (-) 式に対応するのは P(, ) P(, ) = δ ( ) K ( ) ( ) P(, ) (4-) (-4) 式に対応するのは g( ) g( ) P( x, ) P( x, ) = = g( ) = K( ) ( ){( x ) P( x, ) xp( x, )} = (4-)
(4-) 式を期待度数で表現しよう ( ) 時点での適応度の期待値 ( ) を用いて f( x, ) f( x, ) (4-3) = K( ) ( ){( x ) f( x, ) xf( x, )} と書くことができる 同様に (-6) 式に対応するのは α f(, ) f(, ) = K ( ) ( ) f(, ) (4-4) である これ以降は Ⅰ で記述した K ( ) を K ( ) ( ) に置き換えて論理を進めればよい 結論は Ⅰ と同じ結果になる 結論として システムに参入する要素が新たなグループに所属する確率がα で一定であるならば 適応度モデルにおいても優先的選択モデルと同じベキ指数になることが言える (3) ひとり勝ちを説明する適応度モデル Bancon & Barabas (00b) の適応度モデルの特徴は ひとり勝ち する状況を説明したことにある すなわち ネットワークのひとり勝ち現象を量子力学のボーズ アインシュタイン短縮に結びつけた ここでは エネルギーによる表現ではなく 適応度の表現に止めて記述する (4-7) 式を用いて (4-5) 式を変形し ax = ρ ( ) d (4-5) 0 C 0 (4-5) 式の右辺を IC ( ) とおく C であり IC ( ) はC の減少関数になる したがって I() が最大値になる もし I () > ならば (4-5) 式が成り立つ C が存在して 適応度モデルによるベキ乗則になる もし I () < ならば (4-5) 式は成立せず I() の割合がもっとも高い適応度をもつ頂点に吸収される ベキ乗則の場合には 頂点の次数 x は大きいといっても全体の頂点数 g () よりは十分に小さい しかし ボーズ アインシュタイン短縮の場合には x が g () と比較可能なくらいに大きくなっている これがひとり勝ちの状況と言える 注 ( 注 ) この計算過程については鈴木武 (06) を参照 ( 注 ) Ⅱ での記号は Barabas & Alber (999) で用いられたものでなく Ⅰ で記述している記号にあわせて用いている場合がある また この節の (-) 式までは Barabas & Alber (999) と増田直紀 今野紀雄 (005) を参考にしている ( 注 3) Ⅱ の(3) は Dorogovsev & Mendes (00) と増田直紀 今野紀雄 (005) を参考にしている
( 注 4) Ⅳ () での記号は Bancon & Barabas (00a) で用いられたものでなく Ⅰ で記述している記号にあわせて用いている場合がある また 増田直紀 今野紀雄 (005) も 参考にしている 参考文献 H.A.Son (955) "On a Class of Skew Dsrbuon Funcons", Boerka, Vol.4, No.3/4, p.45-440 A.L.Barabas, R.Alber (999) Eergence of Scalng n Rando Neworks, Scence, Vol.86, p.509-5 G.Bancon, A.L.Barabas (00a) Copeon and Mulscalng n Evolvng Neworks, Europhyscs Leers, Vol.54, No.4, p.436-44 G.Bancon, A.L.Barabas (00b) Bose-Ensen Condensaon n Coplex Neworks, Physcal Revew Leers, Vol.86, No.4, p.563-5635 S.N.Dorogovsev, J.F.F.Mendes (00) Evoluon of Neworks, Advanced n Physcs, Vol.5(4), p.079-87 増田直紀 今野紀雄 (005) 複雑ネットワークの科学 産業図書 鈴木武 (007) 参入下限値を単位としたべき乗則生成モデル 経営志林 第 44 巻 号 p.-3 鈴木武 (06) 超優先的選択および非定常状態におけるベキ乗則生成モデル 経営志林 第 5 巻 4 号