Document

ネットワーク(結びつき)のお話
物理教室セミナー
肱黒長憲
2005.2.26
1.Introduction
More Is Different
「多は異なり」
P.W.Anderson, Science 177(1972)393
膨大な数の原子・電子からなる物質の性質を理解するには個々
の構成粒子に対する物理法則とは異なる概念が必要である。
科学のそれぞれの階層で知的独立性がある。
単純なものからより複雑なレベルへの創発
単純な構成員の間の相互作用がいかにより複雑な振る舞い
を引き起こすか
複雑系の科学
Networkの科学
• 複雑な系:要素還元主義が通用しない(要素の組み合わせ方が膨大)
• あらゆるものが他のあらゆるものにつながっている→自己組織化
→ネットワークの重要性
• Laws of Form(形式の法則)
ミクロな要素間の結びつき方のパターンから、どのようなマクロな法則性が出てく
るかを問題にする。
(グラフ理論、システム論)
実際のネットワークの例
● 電力網、インターネット
● 映画俳優、WWW、知人関係
● ニューラルネットワーク、etc
ネットワークは、点(vertex or node)と辺(edge or link)からなる。
vertex
edge
ネットワークの点の総数=6
ネットワークの辺の総数=7
A
B
点Aの次数(点に接続された辺の数)=3
点Aと点Bの間の経路長(経過する辺の数の最小値)=2
Mathematica の利用
•
•
•
ネットワークを調べる道具が用意されている
プログラムが簡単である
グラフィックスを使ってイメージが描きやすい
•
計算時間が長い(プログラムにもよる)
•
簡単な Networkプログラム例
Combinatorica
DiscreteMath`Combinatorica`とは,組み合わせ論とグラフ理論における450以上の
関数によってMathematica を拡張するものである.このような関数には,グラフやそ
の他の組み合わせ論的な対象を構成するもの,これらの対象の不変量を計算するも
の,さらにはその結果を表示するものがある.
このパッケージの最善のガイドブックとなるのは,Steven Skiena,Sriram
Pemmaraju共著の「Computational Discrete Mathematics: Combinatorics and
Graph Theory with Mathematica」(2003年Cambridge University Press)であろう.
新しいCombinatorica は1990年のオリジナルバージョンを書き換えたものである.
新バージョンは,以前のものよりもずっと速く実行でき,グラフィックスも向上し新機能
も加わった.
Webのwww.combinatorica.comには,パッケージの最新リリース,Combinatorica
グラフィックスのエディタ,興味深い追加ファイルなどがある.
Combinatorica パッケージをロードしなくてはならない.
<<DiscreteMath`Combinatorica`
(東洋大学工学部環境建設学科 Yoshino のHPに有用なプログラムの解説がある)
2.Regular Network と Percolation
Site Percolation
nXn 正規ネットワークから m 個の生き残る点をランダムに
選んでランダムグラフを作る。
n=10, m=60
Bond Percolation
nXn 正規ネットワークから m 個の削除する辺をランダムに
選んでランダムグラフを作る。
n=10, m=60
Site Percolation
臨界値
(0.5927)
Bond Percolation
臨界値
(0.5)
3.Random Network
ランダム・ネットワークが依って立つ2つの仮説
(1) 多数の節点がすでに存在している。
(2) すべての節点は対等である。
m=50
m=100
N=20
p=0.3
p=0.6
N=20
ネットワークを特徴付ける基本的な量
Random Network のポアッソン分布
ランダムネットワークのリンクの度数分布がポアッソン分布になる。
点の数 N 、連結確率 p のとき、平均次数は p (N-1)
点の数 N 、辺の数 m のとき、平均次数は 2m / N
N = 点の総数
m = 辺の総数
Random Network の Percolation 転移
ランダムネットワークの辺の数を増やしてゆく(平均次数を増やす)と、ある
臨界値で巨大クラスターができることを示す。
平均次数の閾値は1で、このときすべての節点が少なくとも一つの辺を持
つことを意味する。
現実のネットワークは
平均次数の閾値1を大
幅に超えている。
孤立した点は存在しな
い。
Random Network
の
平均経路長と
クラスタリング係数
p の小さいところで、
平均経路長 L : 短い
クラスタリング係数 C : 小さい
完
全
ネ
ッ
ト
ワ
ー
ク
実際のネットワークの特徴
• 緊密にリンクされたクラスターがいたるところにある
(クラスタリング係数が大きい)にもかかわらず、全体
がスモールワールドになっている(平均経路長が短
い)。
• 次数分布が正規分布でない場合がある。
➞実際のネットワークは正規ネットワークでもランダム
ネットワークでもない。
平等主義的➞Small World Network
貴族主義的➞Scale Free Network
4.Small World
• Milgram (Psychology Today 2 (1967) 60)
• 友人のネットワークを通して世界中のどの人へも到達するに
は何ステップ必要か?
• ネブラスカ州オハマの住人160人からボストンの株式仲買人
まで手紙を転送(ただし、手紙を受け取った人はファースト
ネームで呼び合うような人にしか手紙を送ってはならない)
• (6 degrees of separation = 6次の隔たり)
Small World Network
•
•
•
•
Watts,Strogatz (Nature 393 (1998) 440)
Regular networks(クラスタリングは強い、経路長は長い)
Random networks(クラスタリングは弱い、経路長は短い)
Small world networks(クラスタリングは強い、経路長は短い)
Small World Network を作る
Regular network を確率pでランダムにつなぎ替えを行う
Regular Network からのつなぎ替え
N = 10, k = 4
各辺を確率 p で接続されていない
2点間へつなぎ替える
点1の C = 3/6 = 0.5
点1の C = 1/3
点3-点8 の L = 3
点3-点8 の L = 1
Small World
Network の
平均経路長と
クラスタリング係数
ごく少数のつなぎ替え(確率 p が
小さい) でも
平均経路長 L : 短かくなる
クラスタリング係数 C : 大きいまま
5.Scale Free
80対20の法則
Zipf の法則(単語の出現頻度Hardy)
Zipf の法則(単語の出現頻度Dickens)
Zipf の法則(日本の都市人口)
Gutenberg-Richterの関係式(地震)
M : マグニチュード(= 振幅の対数)
Log(地震数) = a – b M
マグニチュードについて
1935年,リヒター(Richter)によって
導入された。震源から100km離れた
地点に置かれた当時の標準地震計
(ウッド・アンダーソン型地震計)で記
録された揺れの最大振幅をミクロン
(μm)単位で表わし、その数値の対
数をマグニチュードとして定義した。
防災科学技術研究所HPより
Web サイトへの通信量の分布
Distribution of traffic referred to useit.com from other websites in a 3-month period.
Blue dots are referrals from search engines; gray dots are all other referrals; red line is
best-fit Zipf curve
Note use of a double-logarithmic scale.
Jakob Nielsen‘s Websiteより
Zipf の法則,Paretoの法則,べき乗則
スケールフリー・ネットワークを生成する2つの原理
(Barabasi)
• (1) 成長(Growth):自律的に新たな節点が追加され
続ける。ネットワークは1度に1つだけ節点を増やす。
• (2) 優先接続(Preferential Attachment):新しい辺
はより多くの辺を持つ節点に結合しやすい。すなわ
ち、ある節点が選択される確率は、その節点がすで
に獲得している辺数kに比例する。
Scale Free Network を作る
m0=3, m=2
Loop=0
Loop=1
Loop=2
Loop=3
Scale Free Network
m0 = 3
m=2
Loop = 100
Scale Free Network の次数分布確率密度
Scale Free Network のべき乗分布
6.Random Growth Network
m0 = 3
m=2
Loop = 100
Random Growth Network の次数分布確率密度
Random Growth Network の指数関数分布
Network の種類と特徴
7.結論
(1)Network の手法で Percolation も扱える。
(Site Percolation、Bond Percolation)
(2)Regular & Random Network では現実の Network を
表せない。
(3)Regular Network に少数の「つなぎ替え」を行うと Small
World Network が作られる。
(4)「成長」と「選択接続」から Scale Free Network が作ら
れて、べき乗分布が得られる。
(5)「選択接続」ではなく、まったくランダムに接続をする
Random Growth Network では指数関数分布が得られる。