ゼミ#06
Matthew O.Jackson:

Social And Economic Networks,
PRINCETON UNIVERSITY PRESS, 20082009/05/20(水)M2 浦田淳司

本の構成PART I・BACKGROUND AND FUNDAMENTALS OF NETWORK ANALYSIS
Chapter 1 Introduction
Chapter 2 Representing and Measuring Networks
Chapter 3 Emprical Background on Social and Economic Networks
PART II・MODELS OF NETWORK FORMATION
Chapter 4 Random-Graph Models of Networks
Chapter 5 Growing Random Networks
Chapter 6 Strategic Network Formation
PART III・IMPLICATIONS OF NETWORK STRUCTURE
Chapter 7 Diffusion through Networks
Chapter 8 Learning and Networks
Chapter 9 Decisions, Behavior, and Games on Networks
Chapter10 Networked Markets
PART IV・METHODS, TOOLS, AND EMPIRICAL ANALYSIS
Chapter11 Game-Theoretic Modeling of Network Formation
Chapter12 Allocation Rules, Networks, and Cooperative Games
Chapter13 Observing and Measuring Social Interaction
2

PART IBACKGROUND AND
FUNDAMENTALS OF NETWORKANALYSIS（背景とネットワーク分析の基礎）3

ネットワークモデル？？
Peruzzi

BischeriLambertes

Pucci
Strozzi

Gaudagni
Ridolfi

Castellan

Tornabuon
Albizzi
Bardadori

Medici

Salviati

Acciaiuol

Ginori
Pazzi

Chap.1（フィレンチェの名家の婚姻関係図より）

4

ザンビアの亜鉛精錬工場において（Kapherer 1969）

工場内組織図班長：
ジャクソン(48)剥膜係
アベル(44)剥膜係ダミアン(57)

剥膜係
アブラハム(58)剥膜係
ロトソン(37)

剥膜係補佐
ドナルド(36)

剥膜係補佐
ソフト(33)

剥膜係補佐
ベンソン(52)

剥膜係補佐
マクスウェル(66)

計量取次係
ジョシュア(34)

計量取次係

計量取次係
スチーブン(50)

計量取次係
ノア(26)

ゴッドフリー(34)乾燥係：
ヘンリー(31)

洗浄係：
アンドリュー(52)5
社会ネットワークゼミ（2008.10）より

ザンビアの亜鉛精錬工場において席に戻りなさい

ある日の口論ジャクソン(48)仲裁
アベル(44)
妖術をかけるとアブラハムが脅してくる
ドナルド(36)

怒り

ダミアン(57)
口論

その通り。年上の者を尊敬い
おい、せっかち野郎！俺達にアブラハムが妖術を合わせてゆっくりやれ。
なければ、お前は術にかけらかけるって・・・・
せっかち野郎！
れるぞ！
職場委員

アブラハム(58)ドナルド(36)

ロトソン(37)

ベンソン(52)

マクスウェル(66)抗議

ソフト(33)ドナルドは酔っぱらってる
まあまあ、あんたのことのさ。でなきゃ、あんなこ言ったわけじゃないからと言うわけない戻って戻って。

おしゃべり
俺達、若い者は妖術をかあだ名で呼ばれるけられないように気をつ筋合いはない！
けなきゃな！
ゴッドフリー(34)ジョシュア(34)

スチーブン(50)

ノア(26)

ヘンリー(31)アンドリュー(52)6
社会ネットワークゼミ（2008.10）より

ザンビアの亜鉛精錬工場においてアブラハム？うそでしょ？？
休憩時間に・・

ドナルドの振舞いに酔っぱらいって言われたからって弁解の余地はないな
そんなに怒ることじゃないじゃん
職場委員

ドナルド(36)

ロトソン(37)

事情聴取

事情聴取

酒じゃなくて、あだ名とか妖術とかアブラハムが悪い

ほら、行けって。

説明ゴッドフリー(34)スチーブン(50)

ソフト(33)年下に批判されたかドナルドが悪いら怒ったんだ

アブラハム(58)ドナルド、こっちに来いよ
この仕事を頼める？

頼まれた仕事を終え、元の通りへ、、、と思いきや後日、ドナルドは妖術の件を蒸し返し、他の部門へ7
社会ネットワークゼミ（2008.10）より

社会ネットワーク分析に基づく説
明•エゴを点•相互作用（交換関係）のリンクを線（会話、仕事援助、金銭援助など）

4：ロトソン
9：アベル
11：アブラハム
15：ドナルド

多重送信性のリンクのみ抽出（2種以上の交換関係）•リンク数 アブラハム3 vs ドナルド1•アベルはロトソンと結節⇒アブラハムはアベルでなく、ドナルドを非難
そして、ドナルドは敗れ去る
8
社会ネットワークゼミ（2008.10）より

ネットワークゲーム？？
1

2

δ +δ 2 +δ 3 −c2δ + δ 2 − 2 c

u i ( g ) = ∑ δ ij

l (g)

j ≠i

3

4

2δ + δ 2 − 2 cδ +δ 2 +δ 3 −c

− di (g ) ⋅ c
δ : benefit from a direct relationsh ip, 0 < δ < 1c : cost for a player of maintainin g a link

23結合の条件

δ 2 <δ −c

非結合の条件δ 2 >δ −c1Chap.1

9

フリーライダー問題●通常のフリーライダー問題
排除不可能かつ非競合的な財の生産とそれによる効用について．
→一部の人の努力によって，それ以外の人も利益を受けること．
ex.温暖化対策に取り組む国と取り込まない国
ex.商店街における駐車場の設置（お金を出す店，出さない店）

n人のうち，k人が生産協力し，他のn-k人はただで利得を得る●ネットワークを利用したフリーライダー問題
12

3・買う→コストがかかる・隣の人が買っている→借りて読める

Chap.22｜3

買う

買わない買う

（2，2）

（1，4）

買わない

（4，1）

（0，0）

・本を買う
・買わないで借りる・読まない

ネットワークの形に戦略が影響を受ける

10

基礎用語
2

3：ノード（アクター，プレイヤー）：パス

1

4 ：グラフ：次数（ノードの持つ人の数）：距離，ノード間のパスの数

完全グラフChap.2スターグラフ

サイクルグラフ11中心性230.31
0.55
0.17

0.42
0.85
0.17

36

0.37
0.73
0.17
190.250.17
5 0.30272800.26
0.08

0.34
0.30
0.17
200.280.0800.28
0.0800.32
0.0830314( Degree) = d (v) N − 1
2900.200.08

1.2

近接中心性：
全てのノードとの距離をもとに導出

1(closeness) = ∑ δ l ( i , j )

32

0.37
0.58
0.25

次数中心性：
各ノードの持つ次数をもとに導出

1.40.461.240.33

j ≠ i 次数中心性

0.8

近接中心性

0.6

媒介中心性

媒介中心性：他ノード間最短経路にノードが入る割合
0.4Pi ( kj ) / P ( kj )0.2 (Betweenne ss) = ∑j ≠ k ( n − 1)( n − 2) / 20

Chap.24 32 30 23 19 29 5 36 2 31 28 27

12

PART II
MODELS OF NETWORK FORMATION（ネットワーク形成過程）

13

ランダムグラフモデル
実グラフ

実グラフの特徴の読み込み

・Internet page link
・SNSリンク
・論文共著

理論グラフ
ランダムグラフ

現実社会のネットワークを表現

・スケールフリー・スモールワールド
・次数分布p (k )p ( k ) ∝ k −γ

Chap.4・大きいクラスター係数（推移性）
・小さいＬ（平均距離）・次数分布のベキ則（スケールフリー性）
k14

スモールワールドネットワーク
Watts & Strogatz(1998)など

生成アルゴリズム

隣接ノードと，二つ隣のノードにリンクをはる

確率ｐで，貼り替える
リンクを選ぶ

新しいリンク先を選んで，つなぐ●小さい平均距離の実現
cf．ベーコン数，6次の隔たり（弱い紐帯の生成による）●大きいクラスター性（推移性）の実現●平均次数はそれほど大きくない，かつ分散小（格子モデルからの生成による空間的な制約）
Chap.4増田直紀ら，複雑ネットワークの科学，産業図書，pp67－72，2005 を一部参考

15

p*ネットワーク

Wasserman & Pattison(1996)など

ネットワークグラフの中で，ij間にリンクがあるかどうかは，他のネットワーク構造に因る

d ij ( z ) =Pr( X ij = 1 | X ijc )Pr( X ij = 0 | X ijc )条件つき確率の比で，リンク生成確率を表す

条件つき確率は，結合数、相互対数などの属性値から与える

exp{ θ L }Pr( X ij = x ) =k (θ )属性値

etc
Chap.416

次数分配法～成長型ランダムネットワーク～生成アルゴリズム
1．ノード数（ｍ＋1）コの完全グラフを与える
2．i 期にノード i を一つ生成，はじめの次数はｍとする
3． t 期のノードの次数をdi(t)とすると，i+1期以降にできたリンクは di(t)ー di(i)4．期ごとにノードが一つずつ増える．
t期にあるノードにリンクができる確率はm/t
ノードiの次数の期待値はm+mmm
11 t ++ L + = m1 + ++ L +  ≅ m 1 + log    ( t十分大)i +1 i + 2
ti +1t i 


k5m

スケールフリーに近い次数分布を実現

k=m(1+log(100/i)

4m
3mｔの大きさによらず，t/ i の値で分布・次数が決まる

2mmi

Chap.517

選好結合
ｔ期にできる新しいノードは次数mを持つPi ( t ) = m→ノードi とリンクする確率はd i (t )∑tj =1d j (t )※次数が多いノードにリンクしやすい∑ d (t ) = 2tm より(期毎にm本のリンクが増⇔次数和は＋2ｍ)，
tj =1jPi ( t ) =d i (t )dd i ( t ) d i ( t )⇔=2tdt2t

12t
d i (i ) = m より， d i (t ) = m i次数ｄ以下のノードの割合はt − t (m d ) 2Ft (d ) == 1 − m 2 d −2t次数ｄのノードの確率密度分布はｔ期にできるノードの数をβとすると，Chap.5f t (d ) = 2m 2 d −3f t (d ) = 2 β ⋅ m 2 β ⋅ d −1− 2 β
スケールフリー18

ネットワークの安定性
リンクを切らないij>

ijfor all i , j ∈ g , u i ( g ) ≥ u i ( g − ij ) and u j ( g ) ≥ u j ( g − ij )リンクを増やさない

ikj>

ij

kfor all j , k ∈ g , u j ( g + jk ) ≥ u j ( g ) then u k ( g ) > u k ( g − jk )Chap.619

最適ネットワーク
000

3

3

3

1

2

12

12

34

3

4

3

40

0

0

3

3

3

3.25

3.25

1

2

Pairwise stable(安定ネットワーク)
Efficiency(全体最適)：∑ u ( g ) ≥ ∑ u ( g ′) (all g ′)iiii

Pareto Efficiency(パレート最適)：
ui ( g ′) ≥ ui ( g ) for all i となるg’が存在しない

全体
パレ
最適ート

パレート

34222222.2

2.5

2.5

121212安定
Chap.6343434222.222.5

2.520

効用の設定1
距離と次数からの効用関数を設定する

u i ( g ) = ∑ b (l ij ( g ) ) − d i ( g ) cj≠i

cf . b(k ) = δ kjik><lijはi, j間の最短距離
diはノードi の次数b(k)>b(k+1)>0k, c >0ji

k・完全グラフになる条件

b(2) < b(1) − c（距離2を維持よりも，リンクしたほうがいい）・スターグラフになる条件

b(2) > b(1) − c かつ (b (1) − c ) +n−2b ( 2) > 02（スターグラフの効用和が正）・空グラフになる条件(b (1) − c ) + n − 2 b ( 2) < 02

Chap.621

効用の設定2●無政府対価モデル
ui ( g ) = ∑ j ≠i − lij ( g ) − d i ( g )cc<1c>1

完全グラフ
スターグラフ距離のよる効用を負に設定
リンクを渡るごとにコストが発生する（その人にたどり着くまでのコスト） ex.情報発信●共著モデル 11
1++ui ( g ) = ∑ j ⋅
d(g)
d(g)
d(g)
d(g)
ijij

次数の逆数を効用として設定
少数の人と密接な関係を結ぶほうが効用が高い（相手も自分も他のことに煩わされない方がいい）
ex.自助＞共助
被災時は強い関係だけが生きる？

●閥接続型モデル
ノード間距離が一定値以上のものはb(k)=0と足切り→クリーク型のネットワークができる
Chap.622

PART IIIIMPLICATIONS OFNETWORK STRUCTURE（ネットワーク構造の影響）

23

影響力モデル
ネットワークのでき方，構造ではなく，与えられてた構造の中で，なにが起こるのか．

プレイヤー間の意見のやりとり，広まりに着目
前期の他のプレイヤーの意見（状態）から影響を受ける

1 / 3 1 / 3 1 / 3 
0 
影響量 T = 1 / 2 1 / 2
 0 1/ 4 3 / 4



1/2
2

1/3
1/3

1/2

1/3

 1 / 3 1 / 3 1 / 3  1   1 / 3 
1   p (0) =  0 , p (1) = Tp (0) = 1 / 2 1 / 2 0  0  = 1 / 2  0
 0 1 / 4 3 / 4  0   0 
   
 5 / 18 
 3 / 11tp (2) = Tp (1) =  5 / 12  , p (t ) = Tp (t − 1) = T p (0) →  3 / 11 1/ 8 
 3 / 11




1/4

1
3

3/4

Tは影響力の強さ，与え方によって結果が異なる
Chap.8

ex. じかに見てきた人の情報を信じる，消防を信じる24

影響力モデル21/2

 2 / 5 2 / 5 1/ 5
 0 1/ 2 1/ 2
1 t


T = 1 00 , T →  2 / 5 2 / 5 1 / 5 
1/2
 2 / 5 2 / 5 1/ 5
0 1022
1p1 (∞) = p2 (∞) = p3 (∞) = p1 (0) + p2 (0) + p3 (0)
5
5
5

1

1
3

どのアクターも同じ割合で，意見を採りいれるようになる
1/4
1/4
1

1/4

2

51/4

1/4

3

1

1/2
2/3

6
Chap.8

3/4

1/3

1

1/2
4

グループ内で意見が集約される
25

Graphical Game(隣人との相互関係ゲーム)
プレイヤー数 N，プレイヤーは行動{0,1}をとる
プレイヤーi の効用は，ui ( xi , x N i ( g ) )x N i ( g )：i の隣のノードの行動プレイヤーの効用は隣接プレイヤーの行動に影響を受ける（行動の影響は，非接続プレイヤーへも波及）●閾値型の効用関数

ui (1, x N i ( g ) ) = ai (∑ j∈N ( g ) x j ) − ciiui (0, x N i ( g ) ) = 0

ある人数より，行動1を取るプレイヤーが多ければ，行動1をとる
cf. 多数派同調バイアス●便乗型の効用関数
00

Chap.9ui (01, x N i ( g ) ) = 1 − c0

1000

10ui (00, x N i ( g0) ) = 1

1if x j = 1 for somej ∈ Ni ( g )0ui (00, x N i ( g0) ) = 0if 0x j = 01 for 1all j ∈ N i ( g0 )0110101000000

隣人が行動1をとれば便乗，自分で取るとコストがかかる．
閾値2の場合の均衡
26cf. 増水の状況を見に行くRandomly Chosen Neighbors and Network Game
→Graphical Gameの定式化
プレイヤーは自分の次数と隣接プレイヤーの次数のみ知ると仮定

σ (d )：次数dのプレイヤーが行動1をとる確率~
P (d )：次数の分布（次数dのノードの出現確率）~pσ = ∑d σ (d ) P (d )ー隣接プレイヤーが行動1を取る確率

プレイヤーi （次数di）が行動xiをとる期待効用は

 di  m
U d i ( xi , pσ ) = ∑ m = 0 u d i ( xi , m )  pσ (1 − pσ ) d i − mmdi（udは，Graphical Gameのプレイヤーごとの効用）（mは隣接プレイヤーのうち，行動1をとるプレイヤーの数）

U d i ( xi , pσ ) について，xi=0or1で比較
Chap.927

公共財ゲーム（行動の拡張）(効用関数)ui ( xi , x N i ( g ) ) = f xi + ∑ j∈N ( g ) x j − cxiixi = [0, ∞ )※f(x)は非減少関数，上に凸→均衡解を求める．総投資額Xの状態から，⊿xを追加投資効用増分

f ′( X )∆x ＜＝＞

追加コスト

c∆x

→均衡解 コストの方が多いので，投資しない
f ( x ) = c となるx が均衡解もっと投資したほうが儲かる**yy = f ( x)y = cxuixx

Chap.9*28

公共財ゲーム→プレイヤーの選択は？

x*･･･効用を最大にする投資を行う

または･･･コストを払わず，効用を受ける（フリーライダー）0( x * = 1とする )

均衡解の例
01

10001

Chap.9

11

1/3
0

1/3

1/3

1/3
100

1/3

1/3

ネットワークがつながっている
プレイヤー間で公共財ゲーム
ex. 災害時避難路の確保

1/329

A Networked Trading Model
Seller(商人)

価値0→利益p
条件：・値段pは交互に提案・リンクがある相手とのみ交渉可能

商品Aを売買（値段p)Buyer(顧客)価値1→利益1-p

1/2

100

1/2

1/2

1

1/2

1/2

商人

顧客
1/2
Chap.100030

A Networked Trading Model Based on Auctions
・売り手（商人）は一人，買い手は複数のオークションを考える
・形式はsecond-price auction（入札額1位の人は2位の人の額で購入）
買い手の評価価格は[0, 1]をランダムに決定①②SB

S
期待評価額：1/2

期待評価額：2/3, 1/3

購入額：0

購入額：1/3

Bの期待効用：1/2
Sの期待効用：0

Bの期待効用：1/6
B

B

Sの期待効用：1/3

リンク形成コストcを設定 →安定なネットワークは？

B
S
Chap.10

②

①
1/6

1/12
②なし
1/4なし
31

終32