デルを提案し，その解析と壺モデルと呼ばれる確率モデルとの関連について述べる．
1 はじめに
インターネット，人間関係，脳細胞同士の接続関係など，「複雑なシステム」は自然界や人間社会の至る所 に見受けられる．複雑なシステムが大域的な機能（交通流における渋滞や脳における想起・学習）を発現さ せる場合もある．これらの興味深い現象を研究する場合には，システムの特徴的な部分を抜き出して数理 モデルを構築する場合が多い．数理モデルの構築において重要であると考えられるのが，要素間の相互作 用や，それにより誘起されるダイナミクスである．通常は正方格子や完全グラフなどの基盤を考えた上で，
その上にシステムの構成要素を配置してモデルを構築する．近年，ダイナミクスが生じている基盤，すなわ ちシステムの構造についても盛んに研究されるようになり，基盤としてのネットワーク構造を考慮すること の重要性が指摘されている [1, 2]．
複雑なシステムの構造を研究する際には，相互作用の詳細を無視して，システムの構成要素同士の結合 情報だけに注目すると便利である．構成要素を頂点と見なして，構成要素同士の関係性を元に頂点間に辺 を結ぶことにより，システムをネットワーク（グラフ）として表現することが可能となる．現実の様々なシ ステムに対して構築されたネットワークは一般に大規模かつ複雑なものとなるため，こうした複雑なシス テムの構造に着目した研究のことを「複雑ネットワーク研究」と呼称する場合が多い．複雑ネットワーク研 究の要点は，大きく次のようにまとめることができる．
• 測る（ネットワークを特徴づける統計量（物理量）は何か）
• 作る（どのようなメカニズムで複雑な構造が発現しているのか）
• 使う（複雑な構造によって，ネットワーク上でのダイナミクスがどのような影響を受けるか）
これらはそれぞれ独立した研究課題ではなく，互いに相補的なものである．例えば，現実のネットワークを 測ることによって，その特徴を再現するような生成モデルを構築することが可能となる．逆に，生成モデル から得られた知見を元にして現実のネットワークの生成機構を考察することや，ネットワークを特徴づける 新たな指標を提案できる可能性もある．複雑ネットワーク研究が始められてからまだ10年に満たないが，
研究は多岐にわたって行われている．研究分野の大枠については，参考文献[1–3]等を見ていただきたい．
本稿では「複雑ネットワークの生成問題」に焦点を当てる．複雑なネットワーク構造がどのように生成 されるのかという問題は，複雑ネットワーク研究の最も基本的なものである．現実に存在する複雑ネット ワークが持つ特徴を再現するために，「成長するネットワーク」生成モデルという概念が提案された[4]．こ の「成長する」モデルを元にしてより現実的なネットワークに近づけようとする様々な研究が行われてきた が，一方で「成長」という要因がどの程度重要であるかを明らかにすることも大切である．そこで，「成長 しないネットワーク」生成モデルにおいて，現実的な特徴を持たせるための生成メカニズムに関する研究も 行われるようになった[5]．成長しないネットワーク生成モデルには「静的な」モデルと「動的な」モデル が存在する．本稿では既存のネットワーク生成モデルについて説明をした後，「成長しない動的な」ネット ワーク生成の枠組みにおいて現実的な特徴を持つネットワークを生成するためのモデルを提案する．さら に，成長しない動的なネットワーク生成と，平衡統計力学や壺モデルと呼ばれる確率モデルとの関連につい て指摘する．
本稿の構成は以下のようになっている．まず2節において，スケールフリー性の説明とスケールフリー ネットワークを生成する代表的なモデルについて紹介する．最も基本的なモデルである成長する生成モデ ル(Barab´asi-Albertモデル) [4]を解説した後，「静的な」成長しないモデルである閾値モデル[5]について 紹介する．3節では平衡統計力学の枠組みで取り扱うことができる「動的な」成長しないモデルを提案し，
1E-mail: [email protected]
(a) (b)
10-5 10-4 10-3 10-2 10-1 100
100 101 102 103
P(k)
k
図1: (a)BAモデルにより生成されたネットワークの例．(b)次数分布の例．
数値実験の結果を説明する．4節では，壺モデルと呼ばれる確率モデルと「動的な」成長しないモデルの間 の対応関係について述べる．5節は本稿のまとめである．
2 代表的なスケールフリーネットワーク生成モデル
始めに，本稿を通して重要となる概念である「スケールフリー性」について説明する．頂点と辺から構成さ れるネットワークにおいて，ある頂点に結ばれている辺の本数を「次数」と呼ぶ．また，ネットワークにお いて次数がkである頂点の存在確率をP(k)と表し，これを「次数分布」と呼ぶ．次数分布は頂点同士の結 合（関係性）を記述する統計的な指標の1つである．正方格子のような規則的なネットワークの次数分布 はデルタ関数型となる．また，頂点間にランダムに辺を結ぶことにより生成されるランダムネットワークの 次数分布はポアソン分布となる．
現実に存在する多くのネットワークに対して研究が行われた結果，べき則に従う次数分布が多く存在す ることが明らかとなった．次数分布がべき則P(k)∼k−γ（γはべき指数）に従う性質を「スケールフリー 性」，スケールフリー性を持つネットワークのことを「スケールフリーネットワーク」と呼ぶ．インター ネット，World Wide Web，代謝系ネットワーク（化学反応系），人間関係のネットワークなど，様々な分 野におけるネットワークが共通してこのスケールフリー性を持っていることが明らかとなっている [1]．
2.1 Barab´asi-Albert モデル
スケールフリーネットワークを生成する最も代表的なモデルとして，Barab´asi-Albertモデル[4]（BAモデ ル）が挙げられる．BAモデルにおいては，「成長」と「優先的結合」という2つの概念が重要である．成長 とは「頂点と辺がネットワークに次々と追加されていくこと」を意味し，優先的選択とは「大きい次数を 持った頂点の次数はさらに大きくなる傾向があること」を意味する．BAモデルの構成方法を下記に示す．
1. m0個の頂点を用いて完全グラフを作る．すなわち，m0個の頂点をすべて互いに辺で結ぶ．
2. kiを頂点iの次数として，ネットワークの中からm(≤m0)個の頂点を
Π(i)∝ki (1)
という確率に従って選ぶ．すなわち，頂点iを選ぶ確率Π(i)がその頂点の次数kiに比例する．
3. m本の辺を持つ頂点を1つネットワークに追加する．このとき，新たに付け加えられたm本の辺は，
ステップ2で選ばれたm個の頂点へと結ばれる．
4. ステップ2と3を繰り返す．t時刻後にはネットワークはN =t+m0個の頂点から構成される．
図 1(a)にBAモデルにより生成されたネットワークの例を示す．このネットワークは頂点数N = 200，
パラメータm=m0= 1を用いて生成されたものであり，次数の非常に大きな頂点が存在することを確認 できる．図1(b)はN = 2000，パラメータm=m0= 1を用いて生成されたネットワークを20個生成し，
その次数分布について平均を取ったものである．両対数プロットを取っており，次数分布がべき則に従うこ とがわかる．
第2項目は次数k−1の頂点に辺が結ばれた結果，次数kの頂点が増える場合を表している．なお，式(2)の 1行目から2行目の変形では，頂点数nが十分に大きい場合にPn
i=1ki=m0(m0−1) + 2m(n−m0)'2mn が成り立つことを用いた．第3項目は次数kの頂点に辺が結ばれることにより，次数kの頂点の個数が減 る場合を意味している．十分に時刻が経過した後の次数分布P(k) = limn→∞Pk,nは，式(2)より
P(k) = B(k,3)
B(m,3)P(m) (4)
のようにベータ関数を用いて書かれる．ベータ関数はガンマ関数を用いて B(a, b) = Γ(a)Γ(b)
Γ(a+b) (5)
と定義され，aが大きい領域においては近似的にB(a, b)∼a−bと表される．したがって，BAモデルの次 数分布はP(k)∼k−3のように，パラメータmに依らずに指数−3のべき則に従う．
2.2 閾値モデル
BAモデルはネットワークの成長という特徴を持っている．しかしながら，すべてのネットワークが成長し ているわけではなく，成長しないネットワークも存在することが考えられる．成長しないネットワークにお いてスケールフリー性を発現させるための研究も行われており，代表的な成長しないネットワーク生成モデ ルが「閾値モデル」である[5–7]．閾値モデルは暗に優先的選択という生成概念を持っているほか，各々の 頂点にランダムにパラメータを割り振り，そのパラメータを用いて閾値ルールによって辺を結合させるか どうかを決めるという特徴がある．また，すべての頂点対に対して辺を結合させるかどうかを判断すると ネットワークの生成が終了するため，静的な(static)ネットワーク生成モデルである．
1. n個の頂点を準備する．
2. 各々の頂点に重みwiを割り当てる．重みwiの値は確率分布f(w)からランダムに選ばれる．
3. 閾値θは実数値をとるものとする．もし頂点iと頂点jに対してwi+wj ≥θであれば，頂点iと頂 点jを辺で結ぶ．この操作をすべての頂点対に対して行う．
図 2(a)は，頂点数200，重みを指定する分布を指数分布f(w) =e−wとして，閾値θ = 6とした場合 のネットワークの例を示している．BAモデルとは異なり，孤立した頂点が存在しうる．図 2(b)は頂点数 2000の場合について20個のネットワークを生成し，その次数分布について平均を取ったものである．
次数分布の解析は，重みを指定する分布f(w)の変数変換を用いて行う．重みを指定する分布f(w)の累 積分布関数をF(w) =Rw
−∞f(w0)dw0として定義する．重みwをもつ頂点の次数kは，0≤k≤Nに対して k= (N−1)
Z ∞
θ−w
f(w0)dw0'N Z ∞
θ−w
f(w0)dw0=N[1−F(θ−w)] (6)
と計算できる．なお，重みwを持つ頂点はすべて同じ次数を持ち，したがってネットワーク全体の次数分 布は，重みを指定する分布の関数形に依存する．重みを指定する分布の変数wを変数変換することにより 次数分布が得られるため，累積分布関数F(w)を用いて次数分布は
P(k) =f(w)dw dk = f¡
(θ−F−1¡
1−Nk¢¢
N f¡ F−1¡
1−Nk¢¢ (7)
(a) (b)
10-5 10-4 10-3 10-2 10-1 100
100 101 102 103 104
P(k)
k
図2: (a)閾値モデルにより生成されたネットワークの例．(b)次数分布の例．(a)，(b)ともに指数関数に従
う重みの分布f(w) =e−wを用いた．
と計算される．
例えば，重みを指定する分布が指数分布である場合(f(w) =λe−λw(0≤w))には，累積分布関数は F(w) =
Z w
0
λe−λw0dw0= 1−e−λw (8)
となるため，次数分布は P(k) = f¡
θ−F−1¡
1−Nk¢¢
N f¡ F−1¡
1−Nk¢¢ =λexp µ
−λ µ
θ+1 λln k
N
¶¶
N−1
· λexp
µ λ
µ
−1 λln k
N
¶¶¸−1
=N e−λθ k2
(9) となり，指数−2を持つべき則に従うことがわかる．指数分布のほか，パレート分布，コーシー分布など 様々な分布が同様の指数−2を与えることがわかっている[7]．
3 「動的な」成長しないモデル
本節ではBAモデルと閾値モデルとは異なるクラスに属する，「動的な」成長しないネットワーク生成モデ ルを提案する．
閾値モデルの導入により，成長しないネットワークにおいてもスケールフリー性が発現することが明ら かとなった．しかし，閾値モデルは静的なものであるため，辺のつなぎ換えなどの動的なプロセスを含まな い．成長しないネットワーク生成モデルにおいて，閾値モデルのような静的なモデルではなく，時刻ごとに リンクのつなぎ換えが行われるような動的なモデルを考えることもできる．この場合，頂点の個数と辺の 本数は時間に依存せずに固定されるため，平衡統計力学の枠組みを用いることができると期待される．し かし，優先的選択という生成機構を用いるだけでは，スケールフリー性は発現しない[1]．そのため，全く 異なる生成機構を用いるか，もしくは優先的選択を改良することによってスケールフリーネットワークを生 成する新たな数理モデルを模索することが課題となる．
スケールフリー性の発現の可能性を探った結果，まず数値実験のレベルでスケールフリー性を発現する ネットワーク生成モデルを確認することができた．それが優先的再結合を伴う成長しないモデルである[8,9]．
このモデルにおいては，頂点と辺の数は固定されており，既存の辺が次々につなぎ換わるという動的なプ ロセスが存在する．さらに，優先的選択という概念に加えて，各頂点がそれぞれ異なるパラメータをもち，
それにより選択確率が変化するようなランダムネスをもつ生成モデルである．モデルの構成を以下に示す．
1. 始めにN個の頂点をランダムにMnet本の辺でつないでおく．また，頂点の平均次数をhki= 2Mnet/N で定義する．
2. それぞれの頂点に適応度βiを適応度分布φ(β)から割り当てる．
3. 辺lijをランダムに選ぶ．
4. 頂点mを次の確率で選ぶ．
Πm= (km+ 1)βm P
j(kj+ 1)βj. (10)
(a) (b)
10-5 10-4 10-3 10-2 10-1 100
100 101 102 103
P(k)
k
P(k) ~ k-2.05
図4: 適応度分布φ(β) = 1 (0≤β ≤1)を用いて生成されたネットワークの例(a)と次数分布の例(b)．
5. 辺lijを辺limにつなぎ換える（図3）．
6. ステップ3から5を次数分布が変化しなくなるまで繰り返す．
適応度にランダム性がない場合（適応度分布φ(β) = δ(β)など）には次数分布にべき則は表れないが，
例えば適応度分布を一様分布(φ(β) = 1 (0≤β ≤1))とするとスケールフリーネットワークが生成される．
生成されたネットワークの例を図4に示した．次数分布は指数γ∼2.05のべき則に従う分布となる．
BAモデルと同様に，この成長しないモデルに対してもマスター方程式を書くことができる．適応度β，
次数kである頂点の個数が存在する確率をfk(β, t)としたとき，fk(β, t)に対するマスター方程式は（時間 連続極限で）
∂fk(β, t)
∂t =−(k+ 1)βfk(β, t)
Z(t) +kβfk−1(β, t)
Z(t) −kfk(β, t)
Nhki +(k+ 1)fk+1(β, t)
Nhki (11)
となる．ここでZ(t)は規格化定数であり，Z(t) =R dβ P
k(k+ 1)βfk(β, t)と定義される．適応度に関して ランダム性が存在しない場合にはマスター方程式の解を求めることができるが，ランダム性がある場合に は取り扱いが難しくなる．これは規格化定数Z(t)が系の状態に依存して変化してしまうことが原因である．
4 壺モデルとネットワーク
動的な成長しないネットワーク生成モデルが平衡統計力学の枠組みに収まるものであることを考慮すれば，
既存の統計力学的なモデルを援用することが可能となる．具体的には，3節で導入した「動的な」成長しな い生成モデルを解析するために，「壺モデル」と呼ばれる確率モデルを用いることができる[9]．壺モデルと は，たくさんの壺とそれらの壺に入っているボールから構成されるモデルであり，（一般には）ボールをラン ダムに選び出し，ある遷移確率によって選ばれた他の壺へとボールを移動させるプロセスを繰り返す[10]．
図 5にネットワークの一部分とそれに対応する壺モデルを示す．例えば，頂点1は5本の辺を持ってお り，それに対応して壺1は5つのボールを持っている．また辺のつなぎ換えのプロセスは，壺モデルにお けるボールを移し換えるプロセスに対応している．すなわち，
1 2 3 4 5 6 7 ...
1
2
3 4
5
6 7
1 2 3 4 5 6 7
...
図5: ネットワークにおける次数と壺モデルにおけるボールの占有数の対応．
壺 ⇔ 頂点 ボール ⇔ 辺 占有分布 ⇔ 次数分布
という対応関係があることが容易にわかる．壺モデルにおける占有分布とは，1つの壺に何個のボールが 入っているかを表す確率分布である．壺モデルに置き換えることによってどの頂点同士が結合していたかと いう情報は捨てられてしまうが，次数分布を壺モデルにおけるボールの占有分布を求めるという形に置き 換えることにより，見通しよく解析を実行できるようになる．
以下に壺モデルの構成を示す．ここではN個の壺とM個のボールからなる体系を考える．また，系の 密度をρ=M/Nと定義する2．3節で導入した成長しないネットワーク生成モデルと対応させるために，各 壺のエネルギーを
E(ni) =−ln(ni!) (12)
と定義する．ただし，niは壺iに入っているボールの個数である．このようにエネルギーを定義すれば，各 壺の（規格化されていない）ボルツマン因子を
p(ni, βi) =e−βiE(ni) (13) と書くことができる．ここで，各々の壺は異なる温度を持ちうるとして，局所逆温度βiを導入した．局所 逆温度βiはそれぞれの壺iに割り当てられた非時間依存のパラメータであり，分布φ(β)から割り当てられ ているとする．体系が熱浴法のダイナミクスに従うとき，ni個のボールを持つ壺iがni+ 1個のボールを 持つ状態に移るための遷移確率は[11]
Wni→ni+1∝ pni+1
pni = (ni+ 1)βi (14)
となり式(10)と一致するため，式(12)のエネルギーの定義が成長しないネットワーク生成モデルに対応し ていることがわかる．さらに，壺モデルの定義により，ネットワーク生成モデルにおける適応度βiは壺モ デルにおける局所逆温度に対応することがわかる．この局所逆温度については，温度が低い壺ほどボール を溜め込みやすいためにボールの占有数が大きくなり，逆に温度が高い壺はボールをはき出しやすいと解釈 することができる．
以上でネットワーク生成モデルと壺モデルとの次数分布・占有分布の対応関係が付き，さらに3節で導 入した成長しないネットワーク生成モデルに対応するエネルギー関数を導入することができた．したがっ て，次にエネルギー(12)をもつ壺モデルについて，定常状態におけるボールの占有分布を解析することに する．壺モデルを使用する利点は，定常状態の物理量を調べるために分配関数を用いた解析手法がいろい ろと研究されている点である[10]．したがって，マスター方程式ではなく分配関数を用いることにより，定 常状態におけるボールの占有分布の解析を行うことができる．
系の分配関数Zを次のように構成する．
Z1= X∞ n1=0
· · · X∞ nN=0
p(n1, β1)
n1! · · ·p(nN, βN) nN! δ
ÃN X
i=1
ni, M
!
. (15)
2ネットワーク生成モデルとの対応関係において注意すべきなのは，ネットワーク生成モデルにおける辺の本数は壺モデルにおけ るボールの個数の2倍となる点である．1本の辺は2つの頂点と結ばれているために，それぞれの頂点の次数への寄与がある．壺に 入っているボールの個数は次数に対応しているため，2Mnet=Mである．
fk =
Z1n1=0
· · ·
nN=0
δ(n1, k)
n1! · · ·
nN! δ
i=1
ni, M = (k!) Z1
(17)
となる．
ある物理量A(β1, β2,· · ·, βN)について，{β2, . . . , βN}に関してのみ配位平均をとる操作を hA(β1, β2, . . . , βN)i{β2,...,βN}=
Z
φ(β2)dβ2· · · Z
φ(βN)dβNA(β1, β2, . . . , βN) (18)
と書く．fk(β1)の配位平均を取ったものをP(k, β1)とすると，P(k, β1)は配位平均において逆温度β1の壺 1にk個のボールが入っている確率を示しており，
P(k, β1) = D
fk(β1) E
{β2,...,βN}= (k!)β1−1
¿Z2
Z1
À
{β2,...,βN}
(19)
となる．最後にP(k, β)をβに関して平均をとることにより，系全体のボールの占有分布は P(k) =
Z
dβ φ(β)P(k, β) = Z
dβ φ(β)(k!)β−1
¿Z2
Z1
À
{β2,...,βN}
(20)
となる．
以上の手順により，形式的に平衡状態におけるボールの占有分布を計算することができる．式 (20)に おいて分母Z1と分子Z2の両方について一度に配位平均をとる必要があるため，レプリカ法を適用するか，
アニール近似を使用するなどして計算を実行する．
レプリカ法を使用して計算した結果[12]を以下に示す．まず
G(z) = Z
dβ φ(β) X∞ n=0
(n!)β−1zn (21)
とおくと，以下の鞍点方程式により壺モデルの密度ρ=M/Nと鞍点zsの関係は ρ= zs
G(zs) d
dzsG(zs) (22)
となる．したがって，密度を与えると鞍点zsを計算することができ，その鞍点zsを使用してボールの占有 分布は
P(k) = Z
dβ φ(β) (k!)β−1zks P∞
n=0(n!)β−1zsn (23)
となる．
一様なランダム性が存在する場合，すなわち逆温度の分布が一様分布φ(β) = 1, β∈[0,1]で与えられる 場合には，系のボールの密度ρが大きいときzs'1と近似することができるため，占有分布は
P(k)∼k−2 1
(lnk)2 (24)
となる[12]．したがって，占有分布は対数の補正因子を伴ったべき則（指数γ= 2）に従う．以上の解析計
算により，数値実験で確認されていたべき則を解析的にも示すことができた．
5 おわりに
本稿では，複雑ネットワークの生成問題を取り上げて，主なモデル2つ（BAモデルと閾値モデル）につい て紹介したのち，「動的な」成長しないネットワーク生成モデルの提案を行った．重要な点は「平衡統計力 学」で扱うことのできる枠組みのモデルを提案した点であり，これによって壺モデルなどの既存のモデルと の対応関係をもとにした解析を行うことが可能となる．
複雑ネットワークを生成するモデルについては研究がかなり進められており，その理解も深まりつつあ る．このような複雑ネットワーク構造に関する理解をもとにして，学習や推論等の工学的な問題に対してア プローチしていくのが次のステップのひとつであると考えられる．また，個別の対象について複雑ネット ワークという視点から研究を深めていくことも重要であろう．複雑ネットワーク上でのスピングラスのモデ ルやニューラルネットワークについても研究が進められており，解析計算なども行われている[13, 14]．
複雑ネットワーク研究が示してきたことは，ダイナミクスのbackboneとなる構造において「非一様性」
が存在することの重要性である．スケールフリーネットワークにおいては，次数の小さな頂点と大きな頂点 の差異が非常に大きく，そのためにダイナミクスは大きな影響を受ける．スケールフリー性に限らず，非一 様性がもたらすダイナミクスへの影響は場合によっては大きいものとなるため，これらを考慮した研究が 必要であることを指摘した点で，複雑ネットワーク研究の意義は大きいと考えられる．今後は，様々な分野 の個別の問題において「ネットワーク構造」にも着目した具体的な研究が行われるようになることが期待さ れる．
References
[1] R. Albert and A.-L. Barab´asi, Rev. Mod. Phys.74, 47 (2002).
[2] 増田直紀，今野紀雄，『複雑ネットワークの科学』，産業図書(2005).
[3] 増田直紀，今野紀雄，ネットワーク科学の新地平（特集/ネットワーク科学の数理），数理科学，44(8), 5 (2006).
[4] A.-L. Barab´asi and R. Albert, Science 286, 509 (1999).
[5] G. Caldarelli, A. Capocci, P. De Los Rios, and M. A. Mu˜noz, Phys. Rev. Lett.89, 258702 (2002).
[6] M. Bogu˜n´a and R. Pastor-Satorras, Phys. Rev. E 68, 036112 (2003).
[7] N. Masuda, H. Miwa, and N. Konno, Phys. Rev. E70, 036124 (2004).
[8] J. Ohkubo and T. Horiguchi, J. Phys. Soc. Jpn.74, 1334 (2005).
[9] J. Ohkubo, M. Yasuda and K. Tanaka, Phys. Rev. E72, 065104(R) (2005).
[10] C. Godr`eche and J. M. Luck, Eur. Phys. J. B23, 473 (2001).
[11] J. M. Drouffe, C. Godr`eche, and F. Camia, J. Phys. A31, L19 (1998).
[12] J. Ohkubo, M. Yasuda and K. Tanaka, J. Phys. Soc. Jpn.75, 074802 (2006).
[13] I. P. Castillo, B. Wemmenhove, J. P. L. Hatchett, N. S. Skantzos and T. Nikoletopoulos, J. Phys. A:
Math. Gen.37, 8789 (2004).
[14] D.-H. Kim, G. J. Rodgers, B. Kahng and D. Kim, Phys. Rev. E71, 056115 (2005).
