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

M2 浦田淳司
2009.12.02(Wed)Behavior
InNetworks

修士研究：全体見取り図
第1章

背景・目的

第2章

既往研究

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

第5章

第3章

調査概要

第4章

基礎分析

紐帯生成モデル

第6章（ミクロモデル）

第7章

2巨視モデルの適用（適応度モデル）

ネットワーク評価
第8章

結論

Behavior
In
Networks

2章 概要
第2章 既往研究の整理
2.1 避難行動研究の整理
避難意思決定，住民内情報伝達

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

2.3 ネットワーク分析指標
グラフ理論, 中心性分析, 構造分析, 次数分析

2.4 複雑ネットワークモデル
スモールワールドモデル, 閾値モデル,BAモデル, 適応度モデル

2.5 ネットワーク分析実証系研究の整理
2.6 研究の位置づけ

3

Behavior
InNetworks

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
4

Behavior
InNetworks

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を実現

5増田直紀, 今野紀雄: 複雑ネットワークの科学, 産業図書, 2005 を主に参考に

Behavior
InNetworks

2.4.1 スモールワールドモデル
D. J. Watts, S. H. Strogatz: Collective dynamics of ‘small-world’ networks, Nature,Vol.393, pp. 440-442, 1998

現実ネットワークとの対比

・小さい平均距離L・大きいクラスタリング係数C・大きすぎない平均次数ｋ・次数分布のベキ則は実現なし

スモールワールドモデルの形成
ショートカットの作成

6

はじめのネットワーク
・全ノード数 n・両隣k/2コのノードとリンク・全リンク数 kn/2

割合p の枝をランダムにつなぎかえ
1. pkn/2 本をランダムに選ぶ
2. 片方の頂点を切り離す（確率1/2）
3. 新しいつなぎ先をランダムに選ぶ

Behavior
InNetworks

2.4.1 スモールワールドモデル
n=1000, k=10から始めた時の平均距離とクラスタ係数のpによる推移

・平均距離はすぐに短くなる
・クラスタ係数は保持性高い小さいpで短いL・大きなCの実現○近くの相手と多く，遠くの相手とたまに結合○弱い紐帯への対応
×格子型のモデルを前提
×小さいpのため，乱雑さは少ない
×非連結ネットワークになる可能性
7

Behavior
InNetworks

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 番目の頂点viの重みをωiとする（確率密度f(ω)で与える）
・ ωi + ωj ≧ θ のとき，頂点viとvj の間にリンク形成
ω3A

ωB
1.5

ネットワークの特徴
・ω小→クラスター係数C大（ω＜θ/2→C=1）

ω2C

ω1D

θ＝3.5

・ω大→次数大（ω＞θ→k=n）

・連結グラフ→L=2（最大ωのノードに連結）

8Behavior
InNetworks

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 適応度モデル
A)

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

B)

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のべき乗に比例9Behavior
InNetworks

ネットワーク生成メカニズム▼ルール1：ネットワークの成長表現
ノード追加 ⇒ ネットワークが時間とともに成長
設定

毎時，ひとつのノードがネットワークに追加
新しいリンクをm本もつ▼ルール2：優先的選択の記述法
リンク数と適応度が大 ⇒ 新しいリンクを得やすい
設定

t=0

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

t=1

t=2

∏

( vi ) =ηi ki∑ ηknj =1jj

ｋ：リンク数η ：適応度t=3

新しい質の良いノードが古いノードを凌駕しうる

10Behavior
InNetworks

リンク獲得確率▼リンク獲得確率∂k i=m∂t∏ (k ) =imη i k i∑ ηk(A2)nj =1jj（ηは各ノードに確率密度分布ρ(η)で付与）（全てのηが等しいときが，BAモデルに対応）▼次数kの仮定 t kηi (t , t 0 ) = m  t0 β (η i )(A3)（流入時間t0）（時間t=t0のとき，k=m）0 < β (η ) < 1

110 < β (η )ー時間tともに，次数k増加

β (η ) < 1ー獲得リンクは毎時1以下なので，tより増分は小Behavior
InNetworks

分母の近似(A2)式の分母を近似

ρ(η)はηの確率密度分布t∑η k ≅ η ∑ k ≅ ∫ dηηρ (η )∫ dt kη (t, t )jjjjj(A3)式より

100(t − t β (η ) )= dηηρ (η ) ⋅ m
1 − β (η )∫(A4)0 < β (η ) < 1 より∑j12

η jk jt →∞

= Cmt

(A5)

∫

C = dηρ (η )

η(A6)1 − β (η )Behavior
In
Networksβの導出(A2)式に(A5)を代入

∂kη
∂t=

ηi kiCt(A7)(A3)式より∂kηmβ (η )  t  =∂tt 0  t 0 

β (η ) −1=β (η )tkη(A7)式と比較して

β (η ) =η(A8)C

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

1 = dηρ (η )
13

1
C −1

η

(A9)

を満たす必要があるBehavior
InNetworkskの確率分布P(k)(A3), (A8)より, k以上となる累積確率分布は
ηC

 t C m ηkη (t ) > k ⇔ m  > k ⇔ t 0 < t  k
 t0 C C m η   m ηP kη (t ) > k = P t 0 < t    = t  k  k()(A10)(A10)より, 次数kとなる確率分布はP(k ) = −

η max

∫

0dηρ (η )∂P (kη (t ) > k )∂kC

CCt  m  ηC  m η
= dηρ (η )   ∝ dηρ (η )  ηk  k ηk∫

14∫+1(A11)

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

適応度ηの確率分布
次数のスケールフリー性 → 適応度ηの分布ρ(η)次第
Case1 ρ (η ) = δ (η − 1)
(A9)よりC=2(A8)より

β=1/2（ηが全て等しいとき）⇒(A11)より P ( k ) ∝ k−3

Case2 ηが一様分布[0,1]のとき(A9)より

1=1

∫0dη

1C −1

η

[]1= − C log η − C − η 0exp(− 2 / C ) = 1 − 1 / C(A11)より P (k ) ∝15

1

∫0dη

*1

η k1+ C * /ηC(A12)≈（C*=1.255）− (1+ C * )klog(k )(A13)

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

次数分布（両対数グラフ）

・ P(k ) ~ k 2.255 / ln(k ) は P(k ) ~ k 2.255 に比べ，傾きゆるい・ベキ則と比較し，”super hubs”が現れうる

16

Behavior
InNetworks

適応度⇔粒子エネルギー準位適応度ηiに粒子のエネルギー準位εiを対応させる

εi = −1βlogη i(B2)
ノードが準位，リンクが粒子に対応
εG

B

FAFC

BCE

DEA

D
17G

Behavior
InNetworks

リンク獲得確率(Bose)(A2), (B2)より∂k i (ε i , t , ti 0 )e − βε i k i (ε i , t , ti 0 )=m∂t
ZttZt =∑e− βε jk j (ε j , t , t j 0 )

(B4)

(B3)

ー分配関数

j =1

次数は時間のべき乗に比例すると仮定（(A3)と対応）

 t kε i (t , ti 0 ) = m  ti 0 f (ε i )(B5)ηの確率密度分布ρ(η)に対して，εの密度分布は，g (ε )dε = ρ (η )dη ⇔ g (ε ) = βρ ( e − βε )e − βε18

BehaviorInNetworks

式展開（ηと同様）(A4)-(A6)と同様に
− βεt

∫
∫
1e βε
= ∫ dεg (ε )z
1 − f (ε )Zt = dεg (ε )e−1dt 0 k (ε , t , t 0 ) = mz −1t(B6)(B7)

化学ポテンシャルμを次のようにおく
説明できん

e− βµ

< Zt >= lim=zt →∞ mt(B8)(A5), (A8), (B6)より，f(ε)=β(η)なのでmte − βeif (ε i ) == e − β (ε − µ )Zt(B7), (B9)より，∫I ( β , µ ) = dεg (ε )19(B9)

1e β (ε − µ ) − 1=1(B10)Behavior
InNetworks

凝縮過程
ネットワークのリンクがボーズ気体（理想気体）であると考え，n(ε)を粒子密度とすると，∫ dεg (ε )n(ε ) = 1(B11)(B10)より，n(ε ) =1eβ (ε − µ )(B12)−1(B5), (B6), (B9)が成立⇔(B10)のμが存在∫I ( β , µ ) = dεg (ε )1eβ (ε − µ )−1≤ I ( β ,0 )if I ( β ,0) < 1 β，g(ε)の解なし⇒ベキ分布の仮定が不成立（(B5)）
一部の粒子が最低エネルギー準位に凝縮と考える
20BehaviorInNetworks

凝縮過程(2)粒子のうち，n0(β)だけ凝縮していると考える
まず，凝縮していないとき，全粒子数（2mt）は，
t

2mt =

∑ k (ε , t, t ) = mt + mtI (β , µ )t 0 =1t00(B13)I(β, 0)＜0のとき

2mt = mt + mtI ( β , µ ) + n0 ( β )(B14)n0 ( β )= 1 − I ( β ,0)mt(B15)

ある割合だけ，凝縮

21Behavior
IniNetworks∂k=m∂t∏(ki ) =

 t kηi (t , t 0 ) = m  t0 

mη i k i∑n(A2)

η jk jβ (η i )(A3)∑η kjt →∞
j(A4)

= Cmt

(A5)

η1 − β (η )

(A6)

j∫

C = dηρ (η )∂kη∂t=β (η ) =22

ηi kiCtηC(A9)C −1()C m η
P kη (t ) > k = t  k(A10)Cβ (η )∫1ηj =1(t − t)
η j k j = dηηρ (η ) ⋅ m
1 − β (η )j∑∫

1 = dηρ (η )

(A7)

(A8)

C  m ηP(k ) ∝ dηρ (η )  ηk∫+1(A11)Behavior
InNetworksi∂k (ε i , t , ti 0 )e − βε i k i (ε i , t , ti 0 )=m∂tZttZt =∑e− βε j(B3)k j (ε j , t , t j 0 )

(B4)

j =1

 t 
kε i (t , ti 0 ) = m  ti 0 f (ε i )(B5)1e − βε= dεg (ε )z
1 − f (ε )∫(B7)< Zt >= lim=zt →∞ mt(B8)mte − βeif (ε i ) == e − β (ε − µ )Zt(B9)e− βµ∫I ( β , µ ) = dεg (ε )1eβ (ε − µ )−1=1(B10)

Behavior
InNetworks

適応度モデル（導出）G. Bianconi, A.-L. Barabasi(2001)よりリンク生成確率∂k i=m∂t∏(2), (4)式が同時に成立するため必要条件(k i ) =mη i k i∑ ηk(1)

nj =1jβ (η i )

(2)

tj

10

≅ cmt

(3)


η
 c =
ρ (η )dη 
1 − β (η )(4)∫(3)式を(1)式に代入して∂kη ηkη=∂tct
240c /ηc /ηm  m
(7)
P kη (t ) > k = P t 0 < t    ≅ t   k    k []p(k ) = −∑η k ≅ ∫ dηηρ (η )∫ dt kη (t, t )j

時刻tで次数k以上となる頂点の確率分布

時刻tで次数kとなる頂点の確率分布(1)式の分母を集団平均で近似
j(6)

c

j

次数kは時刻tのべき乗で表されると仮定 t kηi (t , t 0 ) = m  t0 ηβ (η ) =(5)∫∂P (kη (t ) > k )m=  k∫∂kc /ηρ (η )dηc− −1ctρ (η )dη ∝ k ηηk(8)k i ノード i の次数 ρ (η ) 適応度の確率分布t i ノード i の生成時刻 η i ノード i の適応度
m ノードの追加の際の生成リンク数

BehaviorInNetworks

スケールフリー性の証明
G. Bianconi, A.-L. Barabasi(2001)より部分性の仮説から全体則を導く(2), (4)式が同時に成立するため必要条件

リンク獲得確率∂k i=m∂t∏ (k ) =imη i k i∑ ηkj

β (η i )(2)

∑η k ≅ ∫ dηηρ (η )∫ dt kη (t, t )j[]p(k ) = −t

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

時刻tで次数kとなる頂点の確率分布(1)式の分母を集団平均で近似jc

時刻tで次数k以上となる頂点の確率分布j次数kは時刻tのべき乗で表されると仮定 t kηi (t , t 0 ) = m  t0 (6)

(1)

nj =1

ηβ (η ) =10∫∂P (kη (t ) > k )0m
=  k∫∂kc /ηρ (η )dηc− −1ctρ (η )dη ∝ k ηηk≅ cmt(3)η c =
ρ (η )dη 
1 − β (η )

(4)スケールフリー（ρ(η)の分布）(5)k i ノード i の次数 ρ (η ) 適応度の確率分布
t i ノード i の生成時刻 η i ノード i の適応度
m ノードの追加の際の生成リンク数∫(3)式を(1)式に代入して∂kη ηkη=∂tct(8)全体を整合させる個の決定モデル

25Behavior
InNetworks

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

26

割合p の枝をランダムにつなぎかえ
1. pkn/2 本をランダムに選ぶ
2. 片方の頂点を切り離す（確率1/2）
3. 新しいつなぎ先をランダムに選ぶ