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

電気・通信・電子・情報工学実験D
確率的情報処理の基礎
第３部講義(2008年6月17日)
本実験DのWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2008/
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
1
第3部の参考文献
大久保潤, 田中和之: 統計力学の基礎 ---複雑
ネットワークとの関連にもとづいて---, 特集/
ネットワーク科学の数理, 数理科学, 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.
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
2
今回の話題
複雑ネットワークの科学
マルコフ過程とネットワーク生成モデル
スケールフリーネットワーク
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
3
確率的情報処理 (Probabilistic
Information Processing) の更なる拡大
日常生活の
情報処理
ポイントはやはり「たくさんが関連」
ICT 技術の要請に耐えうる統計科学
通信理論・像情報処理・確率推論
データマイニング
統計科学
複雑ネットワーク科学
統計的学習理論
情報統計力学
今回のテーマ
確率的情報処理のこれからの数理的基盤
コトの物理学としての定着
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
4
ネットワークと情報処理
たくさんが関連して構成されるシステム
基本構成要素ノード (Node)
基本構成要素間の関連リンク(Link)
ネットワーク (Network)
ネットワークの構造に共通する性質
すぐ思いつく現実的なネットワークの例
インターネット
World Wide Web
都市間の交通網（高速道路，航空路線）
1. すべてのノード間がつながれている訳ではない（非完全グラフ）．
2. ノード間のリンクの存在にはランダム性がある（ランダム性）．
3. 少数ではあるがたくさんのノードとリンクでつながれているノードが
存在する（ハブノードの存在）．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
5
ネットワーク生成メカニズムと情報処理
1. すべてのノード間がつながれている訳ではない（非完全グラフ）．
2. ノード間のリンクの存在にはランダム性がある（ランダム性）．
3. 少数ではあるがたくさんのノードとリンクでつながれているノードが
存在する（ハブノードの存在）．
世の中で自然発生的に構成されたネットワーク上のシステムは
何故，うまく機能するのか?
解明のための戦略
どのような数理モデルに基づいてネットワークが生成されている
と解釈することが妥当なのか?
生成したネットワーク上で与えられた計算モデルにおいてどのよ
うな計算ルール（アルゴリズム）が効率的に機能するのか?
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
6
ネットワークにおけるハブの役割
例：仙台からベネチアまで飛行機で移動したいとしたら
ジェノバ
新潟
仙台
東京成田
ミラノ
札幌
ベネチア
ハブ空港のおかげで
世界的距離が短くなる
（スモールワールド）．
フィレンツェ
もしすぐ近くの空港としか航空便
がなければ何回乗り継ぎをしな
ければならなくなるだろう．
もしすべての空港間で航
空便が運行していたら何
台飛行機が必要だろう．
ハブの役割を果たす空港は多い必要はないが，ある程度の数は必要．
ハブの役割にも種類がある（日本のハブ空港，アジアのハブ空港，世界のハブ空港）．
空港のネットワークに階層構造が生まれる．
空港間・航空会社間の競争の原理
から生み出され，最適化されている．
さまざまのネットワークにおける共通の数理の存在
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
7
複雑ネットワーク生成におけるランダムネス
たくさんが関連して構成されるシステム
全体の構造はとても複雑だが個別のノード間のリンクはある一定の
単純な規則に従って構成される．
必ず規則に従うのか?すべてのノードのリンクが規則に従って
張られているならネットワークには規則性があるはず．
実際のネットワークは完全に規則性をもって構成されていると
は言い難い．むしろランダムネスを伴うと考える方が自然．
複雑ネットワーク
（ランダムネットワーク，スモールワールドネットワーク等）
複雑ネットワークはその生成過程でどのような規則性とどのよ
うなランダムネスを伴うとき現実の効率的ネットワークと同様の
統計的性質をもつのか?
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
8
複雑ネットワークにおける統計的性質
次数 ki：ノード i につながっているリンクの本数
1 N
Pk    k i , k
N i 1
平均次数
N：ノードの総数
スモールワールド性はもつ
がスケールフリー性をもた
ない複雑ネットワーク
N 1
k   kPk 
k 0
平均最短経路長 l: ノード間を結ぶ最短経路の長さ
（最短経路長）のすべてのノード対についての平均
スケールフリー性
スモールワールド性
共通の数理
l
関数系は生成
モデルによる
k
平均次数とともに平均最短
経路長が急速に減少する．
24 June - 14 July, 2008
ハブのある
なしの違い
スモールワールド性とス
ケールフリー性を併せ持
つ複雑ネットワーク
lnPk 
lnk 
両対数プロットで直線にのる．
電気・通信・電子・情報工学実験D
9
複雑ネットワークと確率モデル
スモールワールド性とスケールフリー
性はどのようなネットワーク生成モデ
ルで出現するか?
スモールワールド性はもつ
がスケールフリー性をもた
ない複雑ネットワーク
ハブのある
なしの違い
ハブの生まれる原因は何か?
どのような競争の原理がポイントか?
確率モデルからの複雑ネッ
トワークの理論的解明
スモールワールド性とス
ケールフリー性を併せ持
つ複雑ネットワーク
数値実験ではだめ!!
解析計算がはずせない!!
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
10
スモールワールドネットワークの生成の簡単な例
初期状態
すべての
ノードの次数
は4
ノードにつながってい
るリンクの本数をそ
のノードの次数という．
最短で９本
のリンクを
通って到達
最短で４本
のリンクを
通って到達
ランダムにリンクを選
んで一端を別のノード
につなぎ変える操作を
繰り返す．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
11
スモールワールドネットワークの生成と次数分布
初期状態
次数が3と5
のノードが1
個ずつ出現
すべて
のノード
が次数4
4
k
次数が3と5
のノードが2
個ずつとなる．
4
k
k
k 本のリンクを持つノードの個数についてのヒストグラム
ランダムにリンクを選
んで一端を別のノード
につなぎ変える操作を
繰り返す．
24 June - 14 July, 2008
4
次数が6の
ノードが出現．
4
k
ノード毎につながっているリンクの
本数をそのノードの次数という．
この操作を繰り返すと k はどのような分
布に従うのだろうか?
電気・通信・電子・情報工学実験D
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
つなぎ変えられたリンクの割合
ランダムにリンクを選んで一端を別のノードにつなぎ変える操作を繰り返す．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
13
ランダムネットワークの生成
1. N 個のノードを用意する．
2. 2 個のノードを確率 p でランダムに選択し，リンクで結ぶ．
N=6
N  200
p
k
0.5
P(k)
Poisson分布
へ近づく
N 1
k 
N 1
 kPk   4
k 0
0
0
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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  

24 June - 14 July, 2008

k 
1 

 N 1
N  
k 0
N 1
k
電気・通信・電子・情報工学実験D
 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
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
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 
1
4
2
6
1
6
3
6
X1 (4)  2
1
6
X1 (4)  3
X 2 (4)  1
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
X1 (4)  3
1
6
X 2 (4)  1
電気・通信・電子・情報工学実験D
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
スケールフリーネットワーク
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
19
成長するが優先的選択を伴わない
ネットワーク生成モデル
n  200
k 本のリンクにつな
がっているノードの
個数に対するヒス
トグラム
Pk   ak ではない
時刻 n のネットワークの i 番目
のノードに追加する確率 1/n
Pk   ae
 ck
対数プロット
しても直線に
のらない
スケールフリーネットワークではない
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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

24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
n
X n 1P rX n 1
電気・通信・電子・情報工学実験D
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


24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
定常分布
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
24 June - 14 July, 2008
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 
1
4
2
6
1
6
3
6
X1 (4)  2
1
6
X1 (4)  3
X 2 (4)  1
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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
初期状態
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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 
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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

24 June - 14 July, 2008
初期状態
電気・通信・電子・情報工学実験D
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
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
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 が十分大きい時 
スケールフリーネットワーク
24 June - 14 July, 2008
定性的に再現
k についてのべき分布
電気・通信・電子・情報工学実験D
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.
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
32
複雑系科学におけるネットワークの
確率的生成・統計的分析課題
課題レポート提出期限：2008年7月7日
課題レポート提出方法：LaTeX で作成し，最終版
を PDF に変換し，電子メール添付にて
[email protected] 宛に送付．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
33
複雑系科学におけるネットワークの
確率的生成・統計的分析課題１
ネットワークサイズN=1000のランダムネットワーク
を平均次数<k>が2と4である場合について，以下
の手順による計算機実験からそれぞれ20個ずつ
生成し，次数を横軸にとりヒストグラムを求めよ．
1. N 個のノードを用意する．
2. 2 個のノードを確率 p=<k>/(N-1) でランダ
ムに選択し，リンクで結ぶ．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
34
複雑系科学におけるネットワークの
確率的生成・統計的分析課題２
ネットワークサイズN=1000のBAネットワークを平均次数<k>が2であ
る場合について，次の手順による計算機実験からそれぞれ20個ず
つ生成し，20個のサンプルのそれぞれに対して次数を横軸にとりヒ
ストグラムを書け．さらにべき指数を評価せよ．
得られた次数分布にばらつきが多い場合はその20個のネットワーク
の次数分布の平均をとり評価せよ．
1. 3個のノードを互いにリンクにより結合させ，完全グラフを構成する．
2. 1本のリンクをもつ新しいノード1個を追加し，i 番目のノードに結合
する確率が ki に比例するとしてランダムにノードを選び結合する．
ここで ki は i 番目のノードの次数である．
3. 2の操作を N3 回繰り返す．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
35
複雑系科学におけるネットワークの
確率的生成・統計的分析課題３
課題２で与えられた手順を拡張し，ネットワークサイズ
N=1000のBAネットワークを平均次数<k>が4である場合
について，計算機実験からそれぞれ20個ずつ生成し，20
個のサンプルのそれぞれに対して次数を横軸にとりヒス
トグラムを書け．さらにべき指数を評価せよ．
24 June - 14 July, 2008
電気・通信・電子・情報工学実験D
36

Download Report