アメリカの電力線網 United Airlines の路線図

社会における様々なネットワーク
 インターネット
 World Wide Web
 ツイッター
 電力線網
岡山情報通信技術研究会
岡山大学大学院自然科学研究科
高橋 規一
２０１５年１月２８日
 航空路線網
 神経回路網
 知人関係（人と人のネットワーク）
1
アメリカの電力線網
http://www.lbl.gov/cs/html/exascale4energy/grid.html
2
United Airlines の路線図
3
http://content.united.com/ual/asset/UAL_NA_Map.pdf
4
複雑ネットワーク科学とは
ネットワークはつながり方が重要
 インターネット
 遠隔地のコンピュータに一瞬でアクセス
 コンピュータウィルスの拡がり
 電力線網
 安定な電力供給
 大停電の発生
 知人関係のネットワーク
 うわさ（口コミ）や伝染病の拡がり
 航空機の路線
 羽田・成田の国際ハブ空港化
 脳内の神経回路網
 人間の記憶メカニズム
現実社会にある様々なネットワークに共通の性質（つながり
方）とその生成メカニズムを明らかにしたい
 様々な現象の発生メカニズムの理解
 AIDSやSARSはどのようにして拡がったのか？
 ヒット商品を生み出す効率的な宣伝方法は？
 安全または効率的なネットワークの設計
 コンピュータウィルスに強いネットワークを構築するには？
5
6
グラフ理論の起源
グラフの数学的表現
 ケーニヒスベルグの問題
 ブレーゲル川に架けられた７つの橋を一度ずつ通る経路は
存在するか？
 １７３６年に Leonhard Euler がグラフを用いて解決
 グラフ
 : 頂点集合
 : 辺集合
１
４
２
例


1,2,3,4
1,2 , 1,2 , 1,4 , 2,3 , 2,3 , 2,4 , 3,4
３
 以下では単純無向グラフだけを考える
 単純：自己ループや多重辺がない
 無向：すべての辺は向きをもたない
7
8
グラフの数学的表現（続き）
Erdős‐Rényiのランダムグラフ
 ２頂点の組
のそれぞれに対して，「確率 で辺を張
る」という規則で生成されるグラフ (Erdős & Rényi 1959)
 ２つの頂点 , を結ぶ辺が存在すると
き と は隣接している（頂点 , は辺
, に接続している）
 次数 ：頂点 に接続している辺の本
数
 道：辺の列
, , , ,…,
,
（ただし , , … ,
はすべて異なる）
１
３
２
４
 辺の本数を道の長さ
 頂点間距離
, ：頂点 から への
最短路（道）の長さ（道がなければ∞）
５
頂点１から５への最短路
1,5
3
9
Paul Erdős (1913‐1996)
My Erdős Number is 4!
1.
 ハンガリー出身の数学者
 数論，組み合わせ論，グラフ理論
 生涯に１５００篇あまりの論文を発表
（そのうち５０７篇が共著）
 １日１９時間数学の問題に没頭

10
2.
3.
アンフェタミンを常用
 伝記「放浪の天才数学者エルデシュ」
4.
 Erdős Number（Erdős自身は０，共著
者は１，共著者の共著者は２ …）
http://jp.Wikipedia.org/wiki/ポール・エルデシュ
11
P. Diaconis and P. Erdős, “On the distribution of the greatest common divisor,” Technical Report, Stanford University, 1997.
S. Boyd, P. Diaconis and L. Xiao, “Fastest mixing Markov chain on a graph,” SIAM Review, vol.46, no.4, pp.667‐689, 2004.
S. Boyd and L.O. Chua, “Uniqueness of a basic nonlinear structure,” IEEE Transactions on Circuits and Systems, vol.30, no.9, pp.648‐651, 1983.
N. Takahashi and L.O. Chua, “On the complete stability of nonsymmetric cellular neural networks,” IEEE Transactions on Circuits and Systems‐I, vol.45, no.7, pp.754‐758, 1998. Erdős
１
Diaconis
２
Boyd
３
Chua
４
Takahashi
12
社会学者Milgramの実験 (1967年)
出発地点と目標地点
１６０通の手紙
 出発地点


マサチューセッツ州シャロン
ネブラスカ州オマハ
カンザス州ウィチタ
ネブラスカ州オマハ
マサチューセッツ州ボストン
 受取人


マサチューセッツ州シャロンに住む神学部大学院生の妻
ボストンに住む株式仲買人
カンザス州ウィチタ
何人を経由して受取人に手紙が届くか？
13
１９６７年当時のアメリカ合衆国の人口：２億人
14
スモールワールド
平均頂点間距離
 Milgramの実験の結果
 １６０通中４２通が目標人物に到達
 ４２通の平均発送回数は５．５
定義： 頂点からなるグラフ の平均頂点間距離
/
, ∈ ,
１
例：
世界中のどの２人も間に５人を介せばつながる！
３
最短路長
「スモールワールド（小さな世界）」
「6次の隔たり」
15
頂点対
１
（１，２），（１，３），（２，３），（２，４），（３，４），（４，５）
２
（１，４），（２，５），（３，５）
３
（１，５）
２
４
５
16
ランダムグラフの平均頂点間距離
現実ネットワークの平均頂点間距離
平均頂点間距離
平均次数
203,549,046
10.46
16.18
インターネット
10,697
5.98
3.31
論文引用関係
27,865
3.69
40
1,520,251
18.1
4.6
共著関係
俳優共演関係
449,913
113.443
3.48
単語同時出現
478,773
74.2
2.63
1,989
3.98
6.2
320
3.175
5.06
3,880
9.7
4.37
2,115
2.12
6.80
ソフトウェア
デジタル回路
航空路線網
蛋白質相互作用
代謝
765
9.64
矢久保考介，複雑ネットワークとその構造，共立出版，2013
12
p=2/n
8
8
p=4/n
6
6
n=1600
4
4
2
2
0
0
200
400
800
1600
n
2.56
3200
6400
1
2
3
4
5
6
7
8
9
10
11
平均次数
ネットワーク解析ソフト gephi による実験結果
17
18
複雑ネットワーク科学の誕生
Mark S. Granovetter, “The strength of weak ties”, The American Journal of Sociology, vol.78, no.6, pp.1360‐1380, 1973. •
10
10
弱い絆の強い力
•
12
14
L
WWW
頂点数
L
ネットワーク
マサチューセッツ州の２８２
人のホワイトカラー労働者
を無作為に選び，現在の職
を得るために力になってく
れた人は誰かを調査
1.
D. J. Watts and S. H. Strogatz, “Collective dynamics of `small‐world networks”, Nature, vol.393, pp.440‐
442, 1998. 2. A.‐L. Barabasi and R. Albert, “Emergence of scaling in random networks”, Science, vol.286, pp.509‐512, 1999.
回答：ちょっとした知り合い
（＝弱い絆でつながる人）
19
20
メトロノームの同期
Watts & Strogatz の当初のテーマ
コオロギはどうやって鳴き声を
そろえるのか？
同期 (synchronization)
21
ホタルの同期
YouTube “Synchronisation” (http://www.youtube.com/watch?v=W1TMZASCR‐I)
22
Watts & Strogatz の疑問
コオロギはなぜ鳴き声を同期できるのか？
• 近くにいるコオロギの鳴き
声は聞いているはず
• 鳴き声がすぐに同期する
のは平均頂点間距離が
短いからでは？
• そんなネットワークはどん
な構造？
YouTube “fireflies sync” (http://www.youtube.com/watch?v=sROKYelaWbo)
23
24
クラスター係数
Watts‐Strogatzモデル
 定義（頂点 のクラスター係数(Clustering Coefficient)）
頂点を円周上に配置し，各頂点から右側と左側それぞ
れ 個の頂点に辺を張る
2. 各辺を確率 でランダムに張り替える
1.
(Watts & Strogatz, Nature, 1998)

は頂点 を含む三角形の個数
 意味：頂点 に隣接している２頂点が隣接している割合
 定義（グラフのクラスター係数）
クラスター（塊）構造と短い平均頂点間距離の同時実現？
25
クラスター係数の計算例
26
現実ネットワークのクラスター係数
ネットワーク
頂点数
WWW
インターネット
論文引用関係
1
1
1
1
1
1
26
30
0.11
3.31
0.39
40
0.24
4.6
0.60
俳優共演関係
449,913
113.443
3.48
0.78
単語同時出現
478,773
74.2
2.63
0.687
蛋白質相互作用
代謝
27
16.18
5.98
18.1
航空路線網
0.866 ⋯
10.46
10,697
3.69
デジタル回路
1
1
203,549,046
27,865
ソフトウェア
1 2
5 6
クラスター係数
1,520,251
共著関係
1
5
平均頂点間距離
平均次数
1,989
3.98
6.2
0.08
320
3.175
5.06
0.053
3,880
9.7
4.37
0.3
2,115
2.12
6.80
0.071
765
9.64
2.56
0.67
矢久保考介，複雑ネットワークとその構造，共立出版，2013
28
Watts‐Strogatzモデルの性質
ランダムグラフのクラスター係数
 クラスター係数
辺の張り替え確率 が
小さい間
• 短い平均頂点間距離
• 大きいクラスター係数
を同時に実現
スモールワールド
ネットワーク
（ は辺を張る確率）
 頂点
は 個の頂点と隣接

個の頂点のうちの２頂点 ,
 頂点 , を結ぶ辺が存在する確率は
確率
で存在
ランダムグラフのクラスター係数は小さい
（D.J. Watts and S.H. Strogatz, Nature, 1998)
29
30
Wattsの疑問
次数分布
 与えられた頂点数と平均次数をもつグラフの中でクラス
 次数分布関数：頂点の次数が
 完全グラフ
,
 ‐正則グラフ
,
ター係数が最も高いグラフは？
(D. Watts, Small World, Princeton University Press, 1999)
 星グラフ
• Wattsは解の候補として
結合穴居人グラフを解析
,
である確率
,
• １５年たった現在でもこの
問題は未解決
完全グラフ
31
3‐正則グラフ
星グラフ
32
様々なネットワークの指数
現実のネットワークの次数分布
 次数分布関数はべき則
ネットワーク
に従う
頂点数
WWW
インターネット
長距離電話
論文引用関係
203,549,046
10.46
2.1/2.7
150,000
2.7
2.3
47,000,000
3.16
2.1
783,339
8.57
2.5
18.1
2.5
俳優共演関係
449,913
113.443
2.3
単語同時出現
478,773
74.2
2.7
ソフトウェア
1,989
3.98
2.85
航空路線網
3,880
9.7
1.8
蛋白質相互作用
1,870
2.4
2.5
778
7.5/7.3
2.2/2.1
代謝
矢久保考介，複雑ネットワークとその構造，共立出版，2013
33
ランダムグラフの次数分布
34
Watts‐Strogatzモデルの次数分布
（D.J. Watts and S.H. Strogatz, Nature, 1998)
である確率
0.2
0.18
0.16
0.14
0.12
60
50
0.06
40
0.04
20
0
10
5
10
15
20
25
30
0.1 の場合の次数分布（二項分布）
0.1
0
0
10
20
30
d
35
0.15
0.05
0
d
50,
0.2
30
0.02
0
0.25
P(d)
0.1
0.08
P(d)
P(d)
 頂点の次数が
指数
1,520,251
共著関係
A.‐L. Barabási and R.Albert, “Emergence of scaling in random network,” Science, vol.286, no.5439, pp.509‐512, 1999.
平均次数
40
50
0
10
スモールワールドネットワークは二つの中間
20
30
40
50
d
36
Barabási‐Albertモデル
Barabási‐Albertモデルの次数分布
 ネットワークは成長と優先的選択という法則に支配
 次数分布関数：
(Balabási & Albert, Science, 1999)
 頂点を１個ずつ追加し，それから
0.6
本の辺を張る
(Dorogovtsev, Mendes and Samukhin, 2000)
0.5
1
 頂点
から頂点
に辺を張る確率
P(d)
0.4
∑
2
4
8
16
32
64
0.3
0.1
m=2, n=1000
0.2
0.1
0.01
m=2, n=1000
0
10
20 30 40 50 60 70 80 90 100
d
次数分布関数を特徴づける
ような変数 の値がない
P(d)
0
0.001
0.0001
0.00001
頂点と辺の追加
スケールフリー性
0.000001
d
37
Barabási‐Albertモデルの性質
Barabási‐Albertモデルの拡張
 次数分布関数：べき則（指数３）
2
 BAモデルはクラスター係数が非常に小さい
 現実ネットワークの特徴を完全に再現していない
1
1
2
(Dorogovtsev, Mendes and Samukhin, 2000)
 平均頂点間距離：短い
log
log log
 クラスター係数：小さい
8
 大きいクラスター係数をもつスケールフリーネットワークを
生成する方法
 P. Holme and B. J. Kim, “Growing scale‐free networks with tunable (Bollobás and Riordan, 2004)
1
38
log
clustering,” Physical Review E, vol. 65, no. 2, 26107, 2002.
 K. Klemm and V. M. Eguiluz, “Highly clustered scalefree networks,” Physical Review E, vol. 65, no. 3, 36123, 2002.
 K. Klemm and V. M. Eguiluz, “Growing scale‐free networks with small‐world behavior,” Physical Review E, vol. 65, no. 5, 57102, 2002.
(Klemm and Eguíluz, 2002)
39
40
各頂点の重要度を表す指標
私の研究テーマ
 PageRank (Google)
 頂点数，辺数，次数等の制約の下でクラスター係数を極大に
するグラフの特徴づけ
 中心性
 次数中心性：次数に比例して中心性（重要度）が高い
 媒介中心性(Betweenness Centrality)：グラフ内のすべて
の頂点対を結ぶ最短路が特定の頂点を通る割合
 Saki Koizuka and Norikazu Takahashi, “Maximum clustering coefficient of graphs with given number of vertices and edges,” Nonlinear Theory and Its Applications, vol.2, no.4, pp.443‐457, 2011.
 Tatsuya Fukami and Norikazu Takahashi, “New classes of clustering coefficient locally maximizing graphs,” Discrete Applied Mathematics, vol.162, pp.202‐213, 2014.  構造が変化するネットワークにおける媒介中心性の効率計算
,


: 頂点 と頂点 を結ぶ最短路の個数
: 上記の最短路の中で頂点 を通るものの個数
法の開発
 Ulrik Brandes, "A faster algorithm for betweenness centrality," Journal of Mathematical Sociology, vol.25, no.2, pp.163‐177, 2001.
41
42