論文ゼミ ( 修士論文にむけて ) M2 浦田淳司 (Wed)

(1)

論文ゼミ（修士論文にむけて）

M2 浦田淳司

2009.12.02(Wed)

(2)

修士研究：全体見取り図

第1章背景・目的

第2章既往研究

（避難行動・ゲーム理論・ネットワーク分析・複雑ネットワーク）

第3章調査概要

第4章基礎分析

第7章ネットワーク評価

第8章結論

第6章巨視モデルの適用

（適応度モデル）

第5章紐帯生成モデル

（ミクロモデル）

(3)

2章概要

第2章既往研究の整理

2.1 避難行動研究の整理

避難意思決定，住民内情報伝達

2.2 ゲーム理論

利他的選好，限定合理性，フォーメーションゲーム

2.3 ネットワーク分析指標

グラフ理論, 中心性分析, 構造分析, 次数分析

2.4 複雑ネットワークモデル

スモールワールドモデル, 閾値モデル,

BAモデル, 適応度モデル

2.5 ネットワーク分析実証系研究の整理

2.6 研究の位置づけ

(4)

2.3 ネットワーク分析

2.3.1 グラフ理論

グラフの種類，距離，クラスター係数

2.3.2 中心性分析

次数中心性，媒介中心性，切断中心性，情報中心性

2.3.3 構造分析

構造同値（縮約），ブロックモデル

2.3.4 次数特性

次数分布（SF性），結合相関

・Stanley Wasserman: Social Network Analysis: Methods and Applications, Cambridge University Press, 1994

・金光淳: 社会ネットワーク分析の基礎-社会的関係資本論にむけて-, 勁草書房, 2003

(5)

2.4 複雑ネットワークモデル

2.4.1 スモールワールドモデル

枝のつなぎかえにより，複雑ネットワークを生成

短い平均距離Lと大きいクラスター性Cを実現，SF性なし

2.4.2 閾値モデル

二つのノードの持つ値の和が閾値を越えれば，リンク生成

SF性・短いL・大きなCを実現，協調的モデル

2.4.3 BAモデル

ネットワークの成長・優先的選択を考慮

古株ほどリンクを得やすい，SF性・短いLを実現

2.4.4 適応度モデル

BAモデルの拡張，ノードの固有の適応度ηを考慮

新しいノードでもハブになりうる，SF性・短いLを実現

(6)

2.4.1 スモールワールドモデル

D. J. Watts, S. H. Strogatz: Collective dynamics of ‘small-world’ networks, Nature, Vol.393, pp. 440-442, 1998

・小さい平均距離L

・大きいクラスタリング係数C

・大きすぎない平均次数ｋ

スモールワールドモデルの形成

・全ノード数 n ・両隣k/2コのノードとリンク・全リンク数 kn/2

・次数分布のベキ則は実現なし

現実ネットワークとの対比 割合p の枝をランダムにつなぎかえ 1. pkn/2 本をランダムに選ぶ 2. 片方の頂点を切り離す（確率1/2） 3. 新しいつなぎ先をランダムに選ぶはじめのネットワークショートカットの作成

(7)

2.4.1 スモールワールドモデル

n=1000, k=10から始めた時の平均距離とクラスタ係数のpによる推移・平均距離はすぐに短くなる・クラスタ係数は保持性高い小さいpで

短いL・大きなCの実現

○ 近くの相手と多く，遠くの相手とたまに結合

○ 弱い紐帯への対応

×

格子型のモデルを前提

×

_{小さいpのため，乱雑さは少ない}

×

非連結ネットワークになる可能性

(8)

2.4.2 閾値モデル

G. Caldarelli, A. Capocci, P. De Los Rios, M. A. Munoz: Scale-free networks from varying vertex intrinsic fitness, Physical Review Letters, Vol.89, No. 25, 258702, 2002

・スケールフリーネットワークを実現

・自分と相手の重みからリンクを決定

・協調的仕組みからネットワークを形成

モデルの特徴

閾値モデルからのネットワーク形成

・全ノード数 n

・i 番目の頂点

v

i

の重みをω

i

とする（確率密度f(ω)で与える）

・ ω

i +

ω

j

≧ θ のとき，頂点

v

i

とv

j

の間にリンク形成

ωA ωC ωD ωB

3

2

1

1.5 θ＝3.5

ネットワークの特徴

・ω小→クラスター係数C大

（ω＜θ/2→C=1）

・ω大→次数大

（ω＞θ→k=n）

・連結グラフ→L=2

（最大ωのノードに連結）

(9)

3.2.3 BAモデル

A. –L. Barabasi, R. Albert: Emergence of scaling in random networks, Science, Vol.286, pp. 509-512, 1999

3.2.4 適応度モデル

G. Bianconi, A. –L. Barabasi: Competition and multiscaling in evolving networks, Europhysics Letters, Vol.54, No. 4, pp. 436-442, 2001

G. Bianconi, A. –L. Barabasi: Bose-Einstein condensation in complex networks, Physical Review Letters, Vol.86, No. 24, pp. 5632-5635, 2001

スケールフリー性を成立させるための

ネットワーク生成モデル

スケールフリー則：

_P

₍

_k

₎

∝

_k

−

γ

ー次数kのノードの存在確率P(k)がkのべき乗に比例 A) B)

(10)

ネットワーク生成メカニズム

▼ルール1：ネットワークの成長表現

▼ルール2：優先的選択の記述法

ノード追加 ⇒ ネットワークが時間とともに成長

設定

_{毎時，ひとつのノードがネットワークに追加}

新しいリンクをm本もつ

リンク数と適応度が大 ⇒ 新しいリンクを得やすい

設定ノードViがリンクを得る確率

∏

∑

= = _n j j j i i i k k v 1 ) (

η

_{ｋ：リンク数} η ：適応度 t = 0 t = 1 t = 2 t = 3

新しい質の良いノードが

古いノードを凌駕しうる

(11)

リンク獲得確率

∑

∏

=

∂

n j j j i i i i

k

m

k

m

t

k

1

)

(

η

(A2)

▼リンク獲得確率

（ηは各ノードに確率密度分布ρ(η)で付与）（全てのηが等しいときが，BAモデルに対応）

▼次数kの仮定

) ( 0 0

)

,

(

i i

_t

t

m

t

k

η β η













=

(A3) （流入時間

t

0）（時間

t

=

t

0のとき，k=m）

1 )

(

0 <

β

η

<

)

(

0 <

β

η

1 )

(

η

<

β

ー時間tともに，次数k増加ー獲得リンクは毎時1以下なので，tより増分は小

(12)

分母の近似

(A2)式の分母を近似

∫

∑

≅

t j j j j j

k

d

dt

k

t

1 0 0

)

,

(

)

(

η

_η

ηηρ

η

ρ(η)はηの確率密度分布

(A3)式より

∫

⋅

₋

−

=

)

(

1 )

(

)

(

) (

η

β

η

ηηρ

m

t

β η

d

(A4) 1 ) ( 0 <

β

η

< より

Cmt

k

t j j j ∞ →

=

∑

η

(A5)

∫

−

=

)

(

1 )

(

η

β

η

ηρ

d

C

(A6)

(13)

βの導出

(A3)式より

η η β η

β

η

β

η

k

t

m

t

k

₍

₎

( ) 1

₍

₎

0 0

=













=

∂

−

(A7)式と比較して

C

η

β

(

)

=

(A2)式に(A5)を代入

Ct

k

t

k

_η

η

_i _i

=

∂

(A7) (A8)

このとき，Cは(A6)式より

∫

₋

=

1

1 )

(

1 η

η

ηρ

C

d

(A9)

を満たす必要がある

(14)

kの確率分布P(k)

η η η C C

k

m

t

k

t

m

k

t

k













<

⇔

>













⇔

>

₀ 0

)

(

(A3), (A8)より, k以上となる累積確率分布は

(

)

η η η C C

k

m

t

k

m

t

P

k

t

k

P













=

























<

=

>

₀

)

(

(A10)

(A10)より, 次数kとなる確率分布は

( )

∫

+













∝













=

∂

>

∂

−

=

1 0

)

(

)

(

)

(

)

(

max η η η _η

η

ηρ

η

ηρ

η

ηρ

C C

k

m

C

d

k

m

k

Ct

d

k

t

k

P

d

k

P

(A11)

まだスケールフリーとは言えない

(15)

適応度ηの確率分布

次数のスケールフリー性 → 適応度ηの分布ρ(η)次第

Case1

ρ

(

η

)

=

δ

(

η

−

1 )

（ηが全て等しいとき）

(A9)より

C=2

(A8)より

β=1/2

⇒

(A11)より

3

)

(

k

∝

k

−

P

Case2

ηが一様分布[0,1]のとき

[

]

1 0 1 0 log 1 1 1 η η η η = − − − − =

∫

C C C d (A9)より

(

2 /

C

)

1

1 /

C

exp

−

=

−

(A12)

_{（C*=1.255）}

(A11)より

∫

+ − +

≈

∝

1 0 ) 1 ( / 1 *

)

log(

1 )

(

* *

k

C

d

k

P

C C η

η

(A13)

べき乗と対数の逆数に比例

(16)

次数分布

（両対数グラフ）

)

ln(

/

~

)

(

k

2.255

k

P

は

P

(

k

)

~

k

2.255

に比べ，傾きゆるい

・ベキ則と比較し，”super hubs”が現れうる

・

(17)

適応度⇔粒子エネルギー準位

適応度η

i

に粒子のエネルギー準位ε

i

を対応させる

i i

_β

η

ε

=

−

1 log

(B2) ε A B F C E D G A B F C E D G ノードが準位，リンクが粒子に対応

(18)

リンク獲得確率(Bose)

(A2), (B2)より

Zt

t

k

e

m

t

k

_i

₍

_i

_,

_i

₎

i _i

₍

_i

_,

_i

₎

0 0

ε

₌

−βε

∂

_(B3)

∑

= −

=

t j j j j

t

k

e

Zt

j 1 0

)

,

(

ε

βε (B4) ー分配関数

次数は時間のべき乗に比例すると仮定

（(A3)と対応） ) ( 0 0

)

,

(

i i f i i

t

m

t

k

ε ε













=

(B5) ηの確率密度分布ρ(η)に対して，εの密度分布は， βε βε

βρ

ε

η

ρ

ε

d

=

d

⇔

g

=

e

−

e

−

g

(

)

(

)

(

)

(

)

(19)

式展開（ηと同様）

(A4)-(A6)と同様に

t

mz

t

k

dt

e

g

d

Zt

t 1 1 0 0

)

,

(

)

(

−

=

−

=

∫

ε

βε

∫

ε

(B6)

∫

₋

=

−

)

(

1 )

(

1 ε

ε

βε

f

e

g

d

z

(B7)

(A5), (A8), (B6)より，f(ε)=β(η)なので

z

mt

Zt

e

t

=

>

<

=

∞ → −βµ

_lim

(B8) 化学ポテンシャルμを次のようにおく ) (

)

(

β ε µ β

ε

=

−

=

e

− −

Zt

mte

f

i e i (B9) 説明できん

(B7), (B9)より，

∫

=

−

=

₋

1

1 )

(

)

,

(

) (ε µ β

ε

µ

β

e

g

d

I

(B10)

(20)

凝縮過程

ネットワークのリンクがボーズ気体（理想気体）であると考え， n(ε)を粒子密度とすると，

∫

d

ε

g

(

ε

)

n

(

ε

)

=

1

(B11) (B10)より，

1

1 )

(

) (

−

=

_β _ε₋_µ

ε

e

n

(B12)

(B5), (B6), (B9)が成立⇔(B10)のμが存在

)

0 ,

(

1

1 )

(

)

,

(

) (

β

ε

µ

β

_β _ε _µ

I

e

g

d

I

≤

−

=

∫

₋

1 )

0 ,

(

β

<

I

if

β，g(ε)の解なし

⇒ベキ分布の仮定が不成立（(B5)）

一部の粒子が最低エネルギー準位に凝縮と考える

(21)

凝縮過程(2)

粒子のうち，

_n

0

(β)だけ凝縮していると考える

まず，凝縮していないとき，全粒子数（2mt）は，

)

,

(

)

,

(

2

1 0 0 0

β

µ

ε

t

mt

mtI

k

mt

t t t

=

+

=

∑

=

I(β, 0)＜0のとき

)

(

)

,

(

2 mt

=

mt

+

mtI

β

µ

+

n

₀

β

(B13) (B14)

)

0 ,

(

1 )

(

0

β

I

mt

n

−

=

(B15)

ある割合だけ，凝縮

(22)

∑

∏

=

∂

n j j j i

k

m

t

1

)

(

η

(A2) ) ( 0 0

)

,

(

i i

_t

t

m

t

k

η β η













=

(A3)

∫

∑

=

⋅

₋

−

)

(

1 )

(

)

(

) (

η

β

η

ηηρ

η

k

d

m

t

β η j j j _(A4)

Cmt

k

t j j j ∞ →

=

∑

η

(A5)

∫

₋

=

)

(

1 )

(

η

β

η

ηρ

d

C

(A6)

C

η

β

(

)

=

Ct

k

t

k

_η

η

_i _i

=

∂

(A7) (A8)

∫

₋

=

1 )

(

1 η

η

ηρ

C

d

_(A9)

(

)

η η C

k

m

t

k

t

k

P













=

>

)

(

(A10)

( )

_∫



+











∝

1

)

(

η

ηρ

C

k

m

C

d

k

P

(A11)

(23)

Zt

m

t

i i i i i i 0

=

0

∂

(B3)

∑

= −

=

t j j j j

t

k

e

Zt

j 1 0

)

,

(

ε

βε (B4) ) ( 0 0

)

,

(

i i f i i

t

m

t

k

ε ε













=

(B5)

∫

₋

=

−

)

(

1 )

(

1 ε

ε

βε

f

e

g

d

z

(B7)

z

mt

Zt

e

t

=

>

<

=

∞ → −

lim

βµ (B8) ) (

)

(

β ε µ β

ε

=

−

=

e

− −

Zt

mte

f

i e i (B9)

∫

=

−

=

₋

1

1 )

(

)

,

(

) (ε µ β

ε

µ

β

e

g

d

I

(B10)

(24)

1 / ) ( − − ∝       =

∫

η ρ η η η η c c k d k ct k m

適応度モデル（導出）

∑

∏

= = = ∂ ∂ n j j j i i i i k k m k m t k 1 ) ( η η リンク生成確率次数kは時刻tのべき乗で表されると仮定 ) ( 0 0) , ( i i t t m t t k η β η       = (1)式の分母を集団平均で近似

∫

∑

≅ t j j jk d dt k t t 1 0 0 ) , ( ) (η _η ηηρ η       − =

∫

ρ η η η β η d c ( ) ) ( 1 (1) (2) (3) (3)式を(1)式に代入して ct k t k_η η _η = ∂ ∂ ₍₅₎ (2), (4)式が同時に成立するため必要条件 c η η β( ) = (6) 時刻tで次数k以上となる頂点の確率分布

[

η

]

η η / / 0 ) ( c c k m t k m t t P k t k P       ≅               < = > (7)

∫

∂ _∂ > − = η ρ η dη k k t k P k p( ) ( ( ) ) ( ) (8) G. Bianconi, A.-L. Barabasi(2001)より

cmt ≅ 時刻tで次数kとなる頂点の確率分布 (4)

m

i

k

ノード i の次数 i

η

ノード i の適応度 ) (η ρ 適応度の確率分布 i

t

ノード i の生成時刻ノードの追加の際の生成リンク数

(25)

1 / ) ( − − ∝       =

∫

η ρ η η η η c c k d k ct k m

スケールフリー性の証明

∑

∏

= = = ∂ ∂ n j j j i i i i k k m k m t k 1 ) ( η η リンク獲得確率次数kは時刻tのべき乗で表されると仮定 ) ( 0 0) , ( i i t t m t t k η β η       = (1)式の分母を集団平均で近似

∫

∑

≅ t j j jk d dt k t t 1 0 ( , 0) ) (η _η ηηρ η       − =

∫

ρ η η η β η d c ( ) ) ( 1 (1) (2) (3) (3)式を(1)式に代入して ct k t k_η η _η = ∂ ∂ ₍₅₎ (2), (4)式が同時に成立するため必要条件 c η η β( ) = (6) 時刻tで次数k以上となる頂点の確率分布

[

η

]

η η / / 0 ) ( c c k m t k m t t P k t k P       ≅               < = > (7)

∫

∂ _∂ > − = η ρ η dη k k t k P k p( ) ( ( ) ) ( ) (8) スケールフリー（ρ(η)の分布）

G. Bianconi, A.-L. Barabasi(2001)より

cmt ≅ 時刻tで次数kとなる頂点の確率分布 (4)

m

i

k

ノード i の次数 i

η

ノード i の適応度 ) (η ρ 適応度の確率分布 i

t

ノード i の生成時刻

部分性の仮説から全体則を導く

全体を整合させる個の決定モデル

(26)

2.4.1 スモールワールドモデル

D. J. Watts, S. H. Strogatz: Collective dynamics of ‘small-world’ networks, Nature, Vol.393, pp. 440-442, 1998

・小さい平均距離L

・大きいクラスタリング係数C

・大きすぎない平均次数ｋ

スモールワールド・ネットワークの形成

・全ノード数 n ・両隣k/2コのノードとリンク・全リンク数 kn/2

・次数分布のベキ則は実現なし

現実ネットワークとの対比割合p の枝をランダムにつなぎかえ 1. pkn/2 本をランダムに選ぶ 2. 片方の頂点を切り離す（確率1/2） 3. 新しいつなぎ先をランダムに選ぶ

論文ゼミ ( 修士論文にむけて ) M2 浦田淳司 (Wed)