物理フラクチュオマティクス論応用確率過程論

物理フラクチュオマティクス論
Physical Fluctuomatics
第13回複雑ネットワーク
13th Complex networks and physical fluctuations
東北大学大学院情報科学研究科応用情報科学専攻
田中和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
＊本スライドの図面の一部は大久保潤氏（東大物性研）によりご提供いただき本人の許可を得て掲載しております．
July, 2009
物理フラクチュオマティクス論(東北大)
1
今回の講義の参考文献
大久保潤, 田中和之: 統計力学の基礎 ---複雑ネット
ワークとの関連にもとづいて---, 特集/ネットワーク科
学の数理, 数理科学, Vol.44, No.8 (通巻 518 号),
pp.24-29, August 2006.
Jun Ohkubo, Muneki Yasuda and Kazuyuki Tanaka:
Preferential Urn Model and Nongrowing Complex
Networks, Physical Review E, Vol.72, No.6, Article
No.065104(R), December 2005.
増田直紀, 今野紀雄: 複雑ネットワークの科学，産業図
書, 2005.
July, 2009
物理フラクチュオマティクス論(東北大)
2
今回の話題
複雑ネットワークの科学
マルコフ過程とネットワーク生成モデル
スケールフリーネットワーク
July, 2009
物理フラクチュオマティクス論(東北大)
3
確率的情報処理 (Probabilistic Information
Processing) の中での複雑ネットワーク科学
ポイントはやはり「たくさんが関連」
ICT 技術の要請に耐えうる統計科学
通信理論・像情報処理・確率推論
データマイニング
統計科学
複雑ネットワーク科学
統計的学習理論
情報統計力学
今回のテーマ
確率的情報処理のこれからの数理的基盤
コトの物理学としての定着
July, 2009
物理フラクチュオマティクス論(東北大)
4
ネットワークと情報処理
たくさんが関連して構成されるシステム
基本構成要素ノード (Node)
基本構成要素間の関連リンク(Link)
ネットワーク (Network)
ネットワークの構造に共通する性質
すぐ思いつく現実的なネットワークの例
インターネット
World Wide Web
都市間の交通網（高速道路，航空路線）
1. すべてのノード間がつながれている訳ではない（非完全グラフ）．
2. ノード間のリンクの存在にはランダム性がある（ランダム性）．
3. 少数ではあるがたくさんのノードとリンクでつながれているノードが
存在する（ハブノードの存在）．
July, 2009
物理フラクチュオマティクス論(東北大)
5
ネットワーク生成メカニズムと情報処理
1. すべてのノード間がつながれている訳ではない（非完全グラフ）．
2. ノード間のリンクの存在にはランダム性がある（ランダム性）．
3. 少数ではあるがたくさんのノードとリンクでつながれているノードが
存在する（ハブノードの存在）．
世の中で自然発生的に構成されたネットワーク上のシステムは
何故，うまく機能するのか?
解明のための戦略
どのような数理モデルに基づいてネットワークが生成されている
と解釈することが妥当なのか?
生成したネットワーク上で与えられた計算モデルにおいてどのよ
うな計算ルール（アルゴリズム）が効率的に機能するのか?
July, 2009
物理フラクチュオマティクス論(東北大)
6
ネットワークにおけるハブの役割
例：仙台からベネチアまで飛行機で移動したいとしたら
ジェノバ
新潟
仙台
東京成田
ミラノ
札幌
ベネチア
ハブ空港のおかげで
世界的距離が短くなる
（スモールワールド）．
フィレンツェ
もしすぐ近くの空港としか航空便
がなければ何回乗り継ぎをしな
ければならなくなるだろう．
もしすべての空港間で航
空便が運行していたら何
台飛行機が必要だろう．
ハブの役割を果たす空港は多い必要はないが，ある程度の数は必要．
ハブの役割にも種類がある（日本のハブ空港，アジアのハブ空港，世界のハブ空港）．
空港のネットワークに階層構造が生まれる．
空港間・航空会社間の競争の原理
から生み出され，最適化されている．
さまざまのネットワークにおける共通の数理の存在
July, 2009
物理フラクチュオマティクス論(東北大)
7
複雑ネットワーク生成におけるランダムネス
たくさんが関連して構成されるシステム
全体の構造はとても複雑だが個別のノード間のリンクはある一定の
単純な規則に従って構成される．
必ず規則に従うのか?すべてのノードのリンクが規則に従って
張られているならネットワークには規則性があるはず．
実際のネットワークは完全に規則性をもって構成されていると
は言い難い．むしろランダムネスを伴うと考える方が自然．
複雑ネットワーク
（ランダムネットワーク，スモールワールドネットワーク等）
複雑ネットワークはその生成過程でどのような規則性とどのよ
うなランダムネスを伴うとき現実の効率的ネットワークと同様の
統計的性質をもつのか?
July, 2009
物理フラクチュオマティクス論(東北大)
8
複雑ネットワークにおける統計的性質
次数 ki：ノード i につながっているリンクの本数
1 N
Pk    k i , k
N i 1
平均次数
N：ノードの総数
スモールワールド性はもつ
がスケールフリー性をもた
ない複雑ネットワーク
N 1
k   kPk 
k 0
平均最短経路長 l: ノード間を結ぶ最短経路の長さ
（最短経路長）のすべてのノード対についての平均
スケールフリー性
スモールワールド性
共通の数理
l
関数系は生成
モデルによる
k
平均次数とともに平均最短
経路長が急速に減少する．
July, 2009
ハブのある
なしの違い
スモールワールド性とス
ケールフリー性を併せ持
つ複雑ネットワーク
lnPk 
lnk 
両対数プロットで直線にのる．
物理フラクチュオマティクス論(東北大)
9
複雑ネットワークと確率モデル
スモールワールド性とスケールフリー
性はどのようなネットワーク生成モデ
ルで出現するか?
スモールワールド性はもつ
がスケールフリー性をもた
ない複雑ネットワーク
ハブのある
なしの違い
ハブの生まれる原因は何か?
どのような競争の原理がポイントか?
確率モデルからの複雑ネッ
トワークの理論的解明
スモールワールド性とス
ケールフリー性を併せ持
つ複雑ネットワーク
数値実験ではだめ!!
解析計算がはずせない!!
July, 2009
物理フラクチュオマティクス論(東北大)
10
スモールワールドネットワークの生成の簡単な例
初期状態
すべての
ノードの次数
は4
ノードにつながってい
るリンクの本数をそ
のノードの次数という．
最短で９本
のリンクを
通って到達
最短で４本
のリンクを
通って到達
ランダムにリンクを選
んで一端を別のノード
につなぎ変える操作を
繰り返す．
July, 2009
物理フラクチュオマティクス論(東北大)
11
スモールワールドネットワークの生成と次数分布
初期状態
次数が3と5
のノードが1
個ずつ出現
すべて
のノード
が次数4
4
k
4
k
k
k 本のリンクを持つノードの個数についてのヒストグラム
ランダムにリンクを選
んで一端を別のノード
につなぎ変える操作を
繰り返す．
July, 2009
次数が3と5
のノードが2
個ずつとなる．
4
次数が6の
ノードが出現．
4
k
ノード毎につながっているリンクの
本数をそのノードの次数という．
この操作を繰り返すと k はどのような分
布に従うのだろうか?
物理フラクチュオマティクス論(東北大)
12
スモールワールドネットワークの生成
1
p=0
初期
状態
P(k)
p=0
1
0.8
C(p)/C(0)
0
0
p=0.8
5 10 15
20
0.6
1
P(k)
p=0.8
80%のリンク
がつなぎ変え
られた時
0
0
Poisson
分布へ近
づく
0.4
l(p)/l(0)
0.2
0
-4
10
5 10 15 20
k
k 本のリンクを持つノードの
個数についてのヒストグラム
平均最短経路長
10
-3
-2
10
-1
10
1
p
つなぎ変えられたリンクの割合
ランダムにリンクを選んで一端を別のノードにつなぎ変える操作を繰り返す．
July, 2009
物理フラクチュオマティクス論(東北大)
13
ランダムネットワークの生成
1. N 個のノードを用意する．
2. 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ．
N=6
N  200
k
p
N 1
0.5
P(k)
Poisson分布
へ近づく
N 1
k   kPk   4
k 0
0
0
July, 2009
物理フラクチュオマティクス論(東北大)
5
10
k
15
20
14
ランダムネットワークの次数分布の解析
p
1. N 個のノードを用意する．
2. 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ．
k
N 1
N 1
k   kPk 
k 0
 N  1 k
 N  1 k 
N  k 1

 p 1  p 

Pk   
 
 k 
 k  N  1 
N 1
G  x    Pk x
母関数
k
 N  1 k 


  
k  N  1 
k 0 


k
x  1
 1 
 N 1

N  k 1
lim G x   exp k  x  1
k

k 
1 

 N 1

N  k 1
x
k
N 1
2項分布
k
 
 k k
Pk    k lim Gx  
e
k!
 x N  

July, 2009

k 
1 

 N 1
N  
k 0
N 1
k
物理フラクチュオマティクス論(東北大)
 e
k 0
 k
 k k k

x
 k! 


0.5 N  200
Poisson
P(k)
k 4
分布へ近
づく
0
0
5
10
k
15
20
15
ランダムネットワークの平均経路長の解析
1. N 個のノードを用意する．
2. 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ．
あるノードからみて距離 L にある頂点の総数 n ~ N
平均最短経路長 l ~ L
p
k
N 1
N 1
k   kPk  : fixed
k 0
n 1 k  k
N  
N  , L  , L / N : fixed
k
 1    k
k
 1
L 1
1   k  1
L
1 k
~  k  1
1   k  1
L
ln N
l~
ln k  1
 N   


 k : fixed


l
1
ln k  1
k
1
July, 2009
物理フラクチュオマティクス論(東北大)
16
成長と優先的選択を伴うネットワーク生成モデル
（Barabasi and Albert Model）
X 3 (3)  1
初期状態はノー
ド２個，リンク１
本から出発
ノード１個，リンク１本を
時刻 n のネットワークの
ノードを1つランダムに
選んで追加．
1
2
2
4
1
2
1
4
X1 (3)  2
X1 (2)  1
X 2 (3)  1
X1 (2)  1
X 3 (4)  1
X 4 (4)  1
1
6
X 3 (4)  1
時刻 n のネット
ワークの i 番目の
ノードに追加する
確率
X i n 
X 1 n   X 2 n    X n n 
July, 2009
1
4
2
6
1
6
3
6
X1 (4)  2
1
6
X1 (4)  3
X 2 (4)  1
物理フラクチュオマティクス論(東北大)
1
6
X 2 (4)  2
2
6
1
6
X 4 (4)  1
17
成長と優先的選択を伴うネットワーク生成モデル
（Barabasi and Albert Model）
n3
n4
X 3 (3)  1
n2
1
2
1
4
2
4
1
2
1
4
X1 (3)  2
X1 (2)  1
X 2 (3)  1
X1 (2)  1
n5
X 4 (4)  1
X 3 (4)  1
1
6
X 3 (4)  1
2
6
1
6
3
6
X1 (4)  2
1
6
n  200
July, 2009
X1 (4)  3
1
6
X 2 (4)  1
物理フラクチュオマティクス論(東北大)
X 2 (4)  2
2
6
1
6
X 4 (4)  1
18
成長と優先的選択を伴うネットワーク生成モデル
（Barabasi and Albert Model）
n  200
k 本のリンクにつな
がっているノードの
個数に対するヒス
トグラム
Pk   ak

時刻 n のネットワークの i 番
目のノードに追加する確率
X i n 
X 1 n   X 2 n    X n n 
log Pk    logk  loga
スケールフリーネットワーク
July, 2009
物理フラクチュオマティクス論(東北大)
19
成長するが優先的選択を伴わない
ネットワーク生成モデル
n  200
k 本のリンクにつな
がっているノードの
個数に対するヒス
トグラム
Pk   ak ではない
時刻 n のネットワークの i 番目
のノードに追加する確率 1/n
Pk   ae
 ck
対数プロット
しても直線に
のらない
スケールフリーネットワークではない
July, 2009
物理フラクチュオマティクス論(東北大)
20
確率過程(離散時間)
確率変数の集合
X
n
n  0,1,2,
n は時間
離散的な場合に限定
（離散）マルコフ過程
X
n
n  0,1,2,
PrX n1 X 0 , X1,, X n   PrX n 1 X n 
PrX 0 , X 1 ,, X n   PrX n X 0 , X 1 ,, X n 1PrX 0 , X 1 ,, X n 1
 n

   PrX m X 0 ,, X m 1 PrX 0 
 m 1

 n

   PrX m X m 1 PrX 0 
 m 1

July, 2009
物理フラクチュオマティクス論(東北大)
21
マルコフ過程
X
n
n  0,1,2, X n  1,2,, Nn 
 n

PrX 0 , X1,, X n     PrX m X m 1 PrX 0 
 m 1

P rX n  
N0
N n 1
N1
   P rX
X 0 1 X 1 1
X n 1 1
0
, X 1 , , X n 

 n
      P rX m X m 1 P rX 0 
X n 1 1  m 1
X 0 1 X 1 1

N0
N n 1
N1
N n2

 N 0 N1

 n 1
  P rX n X n 1      P rX m X m 1 P rX 0 
X n 1 1


 X 0 1 X 1 1 X n2 1  m 1
N n 1

 P rX
N n 1
X n 1 1
July, 2009
n
X n 1P rX n 1
物理フラクチュオマティクス論(東北大)
22
マルコフ過程の推移確率
マルコフ過程
X
n
PrX n  
推移確率行列
n  0,1,2, X n  1,2,, Nn 
 PrX
N n1
X n1 1
n
X n 1PrX n 1
推移確率
PrX n  1 X n 1  2
 PrX n  1   PrX n  1 X n 1  1

 
 PrX n  2   PrX n  2 X n 1  1 PrX n  2 X n 1  2






 
 PrX  N   PrX  N X  1 PrX  N X  2
n
n
n 1
n
n
n 1
n
n 


 PrX n  1 X n 1  N n 1  PrX n 1  1 


 PrX n  2 X n 1  N n 1  PrX n 1  2 









 PrX n  N n X n 1  N n 1 PrX n 1  N n 1
 P rX t  1 
 P 1 






 Pr Xt  2 
 P 2  

lim

   t   





 P  N 
 P rX  N 


t


July, 2009
物理フラクチュオマティクス論(東北大)
定常分布
23
成長と優先的選択を伴うネットワーク生成モデル
（Barabasi and Albert Model）
X 3 (3)  1
初期状態はノー
ド２個，リンク１
本から出発
ノード１個，リンク１本を
時刻 n のネットワークの
ノードを1つランダムに
選んで追加．
1
2
2
4
1
2
1
4
X1 (3)  2
X1 (2)  1
X 2 (3)  1
X1 (2)  1
X 3 (4)  1
X 4 (4)  1
1
6
X 3 (4)  1
時刻 n のネット
ワークの i 番目の
ノードに追加する
確率
X i n 
X 1 n   X 2 n    X n n 
July, 2009
1
4
2
6
1
6
3
6
X1 (4)  2
1
6
X1 (4)  3
X 2 (4)  1
物理フラクチュオマティクス論(東北大)
1
6
X 2 (4)  2
2
6
1
6
X 4 (4)  1
24
マルコフ過程による
Barabasi and Albert Model の解析
n2
n3
Barabasi and Albert Model
等価
Yule Process
July, 2009
物理フラクチュオマティクス論(東北大)
25
マルコフ過程による
Barabasi and Albert Model の解析
PrX 1 n  1,, X n 1 n  1
n 1 n 1 n  2
   
k1 1 k 2 1k 3 1
 PrX n  1,, X n  1 X n  k ,, X n  k
2
k n 1 1
n 1
1
1
1
n 1
n 1
, X n n   1
 PrX 1 n   k1 ,, X n 1 n   kn 1 , X n n   1
P rX 1 n  1  l1 ,, X n n  1  ln , X n 1 n  1  1 X 1 n   k1 ,, X n n   kn 
n
 n
  n

ki
  
 li  ki  1   li   ki  1
i 1

 i 1 2n  1
  i 1
1
2
PrX1 2  1, X 2 2  1  1
初期状態
July, 2009
物理フラクチュオマティクス論(東北大)
26
マルコフ過程による
Barabasi and Albert Model の解析
PrX 1 3, X 2 3, X 3 3
 PrX 1 3, X 2 3, X 3 3 X 1 2  1, X 2 2  1PrX 1 2  1, X 2 2  1
1
2
PrX 1 3  2, X 2 3  1, X 3 3  1 
1
2
PrX1 2  1, X 2 2  1  1
初期状態
PrX 1 3  1, X 2 3  2, X 3 3  1 
July, 2009
物理フラクチュオマティクス論(東北大)
1
2
27
マルコフ過程による
Barabasi and Albert Model の解析
PrX1 4, X 2 4, X 3 4, X 4 4
   PrX1 4, X 2 4, X 3 4, X 4 4 X1 3  k1 , X 2 3  k2 , X 3 3  1PrX1 3  k1 , X 2 3  k2 , X 3 3  1
2
2
k1 1 k 2 1
X 1 3  k1  2
X 1 3  k1  1
X 3 3  1
X 3 3  1
X 2 3  k2  2
X 2 3  k2  1
PrX 1 3  2, X 2 3  1, X 3 3  1 
1
2
PrX 1 3  1, X 2 3  2, X 3 3  1 
1
2
PrX1 4  k1  1, X 2 4  k2 , X 3 4  1, X 4 4  1 X1 3  k1 , X 2 3  k2 , X 3 3  1 
k1
k1  k2  1
PrX1 4  k1 , X 2 4  k2  1, X 3 4  1, X 4 4  1 X1 3  k1 , X 2 3  k2 , X 3 3  1 
k2
k1  k2  1
1
PrX1 4  k1 , X 2 4  k2 , X 3 4  2, X 4 4  1 X1 3  k1 , X 2 3  k2 , X 3 3  1 
k1  k2  1
July, 2009
物理フラクチュオマティクス論(東北大)
28
マルコフ過程による
Barabasi and Albert Model の解析
P rX 1 3  3, X 2 3  1, X 3 3  1, X 3 3  1

2 1 1
 
4 2 4
PrX 1 4  2, X 2 4  2, X 3 4  1, X 4 4  1
1 1 1
 2  
4 2 4
1 2
PrX 1 4  2, X 2 4  1, X 3 4  2, X 4 4  1

1 1 1
 
4 2 8
PrX 1 4  1, X 2 4  3, X 3 4  1, X 4 4  1

2 1 1
 
4 2 4
PrX 1 4  1, X 2 4  2, X 3 4  2, X 4 4  1

July, 2009
初期状態
物理フラクチュオマティクス論(東北大)
1 1 1
 
4 2 8
29
マルコフ過程による
Barabasi and Albert Model の解析
PrX 1 n  1,, X n n  1, X n 1 n  1
n 1 n 1 n  2
   
k1 1 k 2 1k 3 1
 PrX n  1,, X n  1, X n  1 X n  k ,, X n  k
2
k n 1 1
1
n 1
n
1
1
n 1
n 1
, X n n   1
 PrX 1 n   k1 ,, X n 1 n   kn 1 , X n n   1
n 1 n 1 n  2
2
k1 1 k 2 1k 3 1
k n1 1
PrX i n  k      ki , k
 PrX1 n  k1 , X 2 n  k2 , X 2 n   k3 ,, X n 1 n  kn 1 , X n n  1

k 

P rX i n  1  k   n
P rX i n   k  1  1  n
P rX i n   k 


i 1 ki
 i 1 ki 
k 1


k 1
k 
P rX i n   k  1  1 
 P rX i n   k 
2n  1
 2n  1 
1  i  n, k  2
July, 2009
物理フラクチュオマティクス論(東北大)
30
マルコフ過程による
Barabasi and Albert Model の解析
 k 1


k 














Pr
X
n

1

k

Pr
X
n

k

1


1


Pr
X
n

k


i
i
i
 2n  1 
 2n  1

i 1
i 1 



n 1
n

n 
k  n 
 Pk  1, n   n  
  Pk , n k  2
2  n  1
2  n  1

n  1Pk , n  1  k  1 

k  1k  21
Pk , n  
P1, n 
k  2k  14

3!
P1, n  ~ k  3
k  2k  1k
n が十分大きい時 
スケールフリーネットワーク
July, 2009
定性的に再現
k についてのべき分布
物理フラクチュオマティクス論(東北大)
31
まとめ
複雑ネットワークの生成におけるメカニズム
ランダム性
優先的選択性
が重要
Barabasi and Albert Model はネットワークの成長を伴う
がスケールフリー性にネットワークの成長は必要か?
成長を伴わないネットワークでもスケールフリー性は出現する:
J. Ohkubo, M. Yasuda and K. Tanaka: Preferential Urn Model
and Nongrowing Complex Networks, Phys. Rev. E, Vol.72,
No.6, Article No.065104(R), December 2005.
July, 2009
物理フラクチュオマティクス論(東北大)
32

Download Report