ネットワーク科学における いくつかの確率的手法

ネットワーク科学における
いくつかの確率的手法
京都大学 大学院情報学研究科
大久保 潤
講演の構成
（使えそうな）確率的手法を２つ紹介する
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword:
分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword:
(完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
講演の構成
（使えそうな）確率的手法を２つ紹介する
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword:
分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword:
(完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
さまざまなシステムと凝縮現象
Particle aggregation
凝縮現象
n  Bose-Einstein凝縮（運動量空間）
n  Real-space凝縮（実空間）
Traffic flow
（例）
•  Particle aggregation
粒子の巨大な塊（クラスター）の生成
•  Congestion in traffic flow
渋滞（車のクラスター）の発生
•  Complex networks
１つの頂点に大部分の辺が集中
Complex networks
Barabási-Albertモデル
[Barabási and Albert, 1999]
成長 + 優先的選択
初期条件: 個の頂点を持つ完全グラフ
個の頂点を次数 に比例する確率で選択
本の辺を持つ新しい頂点を一つ追加
選択された 個の頂点に新しい頂点から辺を
つなぐ
5.  2から4を繰り返す．
時刻 における頂点の数は
P(k)
1. 
2. 
3. 
4. 
10-1
-2
10
-3
10
-4
10
t=0
t=1
t=2
t=3
t=4
-5
10
0
10
1
10
10
k
2
3
10
マスター方程式による解析
k +1
Pref
k
Pref
k -1
m +1
Pref
m
add
1
2
3
1
2
3
再結合モデル
[Ohkubo et al., 2005]
β = 0.81
β = 0.15
不規則性 + 優先的選択
β = 0.10
β = 0.34
β = 0.72
m
j
1.  初期条件: 頂点数 ，辺の数 のランダムネッ
トワーク．各頂点が という分布に従う適応
度 を持つとする．平均次数は
2.  辺 をランダムに選ぶ
3.  ある頂点を， に比例する確率で選ぶ
4.  辺 を辺 につなぎかえる
5.  2から4を，平衡状態になるまで繰り返す
β = 0.62
β = 0.45
i
β = 0.50
β = 0.20
β = 0.81
β = 0.15
β = 0.10
β = 0.34
β = 0.72
m
j
β = 0.62
β = 0.45
β = 0.50
i
β = 0.20
ネットワークの例
P(k)
10
0
10
-1
10
-2
10
-3
デルタ関数型適応度分布
分布:
指数関数的な減衰
10-4
10
-5
0
10
1
2
10
10
3
10
k
100
P(k) ~ k-2.05
P(k)
10-1
10
-2
10
-3
10
-4
10
-5
100
一様分布型適応度分布
分布:
べき乗的な減衰
101
102
k
103
どう解析するか？
マスター方程式を解くのは難しい
平衡状態の性質を知りたい 分配関数を使う
次数分布のみに着目 壺モデルを使う
Randomly
chosen ball
ネットワークの
次数分布
3
1
Preferentially
chosen urn
...
Randomly
chosen edge
4
2
6
1
2
3
4
5
6
7
7
5
Preferentially
chosen node
...
壺モデルの
ボールの占有分布
1
2
3
4
5
6
7
優先的壺モデル
※ネットワークの時と記号が違います
...
h1 h2 h3 h4 h5 h6 h7
1. 
2. 
3. 
4. 
5. 
個の壺に計 個のボールが入っている（平均密度 ）
不規則性のパラメータ を，分布 に従って各壺に割り当てる
ボールを一つランダムに選択する
そのボールを抜く
抜いたボールを，次の確率で選んだ壺に移す: ここで， は壺 のボールの個数
6.  3から5を，平衡状態になるまで繰り返す
分配関数
壺 1 にボールが 個入っている確率
占有確率
解析結果のポイント 1
n  不規則性があるので，レプリカ法（もしくは大数の法則）を用いる
n  ボールの密度と鞍点の関係
n  凝縮を調べるために重要な関数
n  占有分布
解析結果のポイント 2
凝縮を生じるための条件
n  関数 の収束半径 が有限
n  その収束半径を用いて計算される臨界密度 が有限
コメント
•  ボールの密度と鞍点の関係を表す式において，等式を満たす鞍点
が存在しない場合がある（鞍点の取りうる範囲が限られている場
合）．その場合，臨界密度を超えた分は別に扱われる 凝縮
•  関数 の中の因子 は非常に強いため，大抵の において収束半径は無限大になる 凝縮しづらい
0
0.5
10
0.4
10-1
0.3
10
0.2
10-4
0.0
10
-5
0
5
10
15
20
k
= 1.0
= 4.0
-1
10
-2
10
-3
10
-4
10
-5
10
0
1
10
10
k
0
10
1
2
10
10
k
0
10
P(k)
-3
10
0.1
10
=2
=5
-2
P(k)
P(k)
数値実験の結果
2
3
10
10
3
Complete condensation
...
h1 h2 h3 h4 h5 h6 h7
The number of balls
350
300
250
200
150
100
50
0
0
50
100
Site
n  どれか一つの壺でも であれば，収束半径
n  臨界密度
すべてのボールが一つの壺のみに凝縮
150
200
のとき
は一様分布．
臨界密度:
凝縮が生じない
のとき
臨界密度は有限:
凝縮が生じる
180
160
140
120
100
80
60
40
20
0
0
50
100
150
200
Site
0
10
= 1.4
= 2.4
-1
10
10-2
P(k)
パラメータの確率密度関数
The number of balls
Genuine condensation
-3
10
10-4
注意：
凝縮が生じても，巨視的な量のボールを占有する壺が
出現することを除いて，占有分布の形状は変化しない
-5
10
-6
10
10
0
1
10
2
10
k
10
3
10
4
Note for the genuine condensation
凝縮を生じている壺の入っているボールの個数を とする．
このとき， は密度 に線形に依存する
5000
Nmax
4000
3000
2000
1000
0
0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6
Pseudo-condensation
100
ある一つの壺（パラメータ ）を除き，
すべてのパラメータを とする
= 2.0
= 3.0
-1
10
のとき
Pseudo-condensation
ボールの密度を増やしたとき，占有
分布の形状が変化する（有限系）．
10-3
10-4
10-5
10-6 0
10
101
102
103
104
k
100
= 2.0
= 3.0
-1
10
10-2
P(k)
のとき
臨界密度は ．
実空間凝縮が生じる．
凝縮相においても，占有分布の形状
は変化しない（ポアソン分布）．
P(k)
10-2
10-3
10-4
10-5
10-6
100
101
102
k
103
104
前半のまとめ
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword: 分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword: (完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
•  分配関数を用いた解析: 統計力学の分野で発展
•  平衡状態における系の情報を引っ張りだすことができる
•  不規則性がある場合の解析: レプリカ法など
（符号や通信など，数多くの応用）
J. Ohkubo, Phys. Rev. E 76, 051108 (2007)
講演の構成
（使えそうな）確率的手法を２つ紹介する
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword:
分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword:
(完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
(完全)計数統計とは何か？
離散状態をもつ連続状態マルコフ過程
D
A
D
A
Donor-­‐Acceptor model
[Gopich and Szabo, J. Chem. Phys (2005; 2006)]
D
A
(FRET: Förster Resonance Energy Transfer) 目的: 遷移の回数に関する揺らぎも含めた統計
光子の統計性から系の状態や
パラメータを推定する
[Chung et al., J. Phys. Chem. A (2011)]
粒子のホッピングのモデル
LeV reservoir
Container
empty / filled
Right reservoir
何が問題になるか？
コンテナの状態
[Empty]
[Filled]
[Empty]
状態の変化を追うだけでは違いがわからない
状態 状態 状態 ……
過程: ここを知りたい
ここでの目的
状態の時間発展と過程（の時間発展）をつなぐこと
マスター方程式
?
時間発展方程式
粒子のホッピングのモデル
LeV reservoir
Container
Right reservoir
empty / filled
計算したいもの: 時間にターゲットとする遷移が何回生じたか？
計数統計とマスター方程式
状態変化の時間発展
過程（遷移の回数）の時間発展
Technical details 1
[Gopich and Szabo, J. Chem. Phys (2005)]
一般的な設定:
ターゲットとする遷移 が生じないという条件下で，
時間の間の の遷移確率
時間の間に 回，ターゲットとする遷移が生じる確率
Technical details 2
母関数
母関数の時間発展
Technical details 3
新しい母関数
新しい母関数に対する時間発展
何をすべきか？
過程に関する母関数
すべての統計
母関数をどのように作るか？
例1
コンテナ 右の粒子浴
定常解
[Gopich and Szabo, J. Chem. Phys (2006)]
例2
コンテナ 右の粒子浴
GeneraWng funcWon
非定常の場合は難しい？
Rate coefficients
流れの平均は簡単
母関数に基づく数値計算 1
母関数の1階微分より
母関数から計算した流れの「平均」
母関数に基づく数値計算 ２
高次のモーメント
6
-0.1
4
2nd moment
0.0
-0.2
-0.3
0
2
4
6
8
10
time
-1
-2
-3
-4
0
2
4
6
time
2
0
0
2
4
6
time
0
3rd moment
1st moment
モンテカルロ法との比較
8
10
8
10
後半のまとめ
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword: 分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword: (完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
•  マルコフ過程による状態の時間発展方程式を書き下すことができれば，
すぐに遷移の回数に対する統計を計算することが可能
•  生物，化学，非平衡統計物理学の文脈で研究されている
•  ネットワーク上でのダイナミクスの研究に使える？
•  （数理的な構造についても調べられている）
J. Ohkubo and T. Eggel, J. Stat. Mech., P06013 (2010)
全体のまとめ
n  同じ遷移規則を繰り返してできる平衡状態の解析
Keyword: 分配関数
不規則性を持つモデルと凝縮現象
n  状態の時間発展と過程（の時間発展）をつなぐ
Keyword: (完全)計数統計
連続時間・離散状態のマルコフ過程において遷移の回数を数える
確率的な現象
とりあえずモンテカルロシミュレーション？
解析的な扱い 現象の理解，高速な数値計算法