Document

ネットワーク（結びつき）のお話
物理教室セミナー
肱黒長憲
２００５．２．２６
１．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
ネットワークの点の総数＝６
ネットワークの辺の総数＝７
A
B
点Aの次数（点に接続された辺の数）＝３
点Aと点Bの間の経路長（経過する辺の数の最小値）＝２
Ｍａｔｈｅｍａｔｉｃａの利用
•
•
•
ネットワークを調べる道具が用意されている
プログラムが簡単である
グラフィックスを使ってイメージが描きやすい
•
計算時間が長い(プログラムにもよる）
•
簡単な 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に有用なプログラムの解説がある）
２．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)
３．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 転移
ランダムネットワークの辺の数を増やしてゆく(平均次数を増やす）と、ある
臨界値で巨大クラスターができることを示す。
平均次数の閾値は１で、このときすべての節点が少なくとも一つの辺を持
つことを意味する。
現実のネットワークは
平均次数の閾値１を大
幅に超えている。
孤立した点は存在しな
い。
Random Network
の
平均経路長と
クラスタリング係数
p の小さいところで、
平均経路長 L : 短い
クラスタリング係数 C : 小さい
完
全
ネ
ッ
ト
ワ
ー
ク
実際のネットワークの特徴
• 緊密にリンクされたクラスターがいたるところにある
(クラスタリング係数が大きい)にもかかわらず、全体
がスモールワールドになっている(平均経路長が短
い)。
• 次数分布が正規分布でない場合がある。
➞実際のネットワークは正規ネットワークでもランダム
ネットワークでもない。
平等主義的➞Small World Network
貴族主義的➞Scale Free Network
４．Small World
• Milgram (Psychology Today 2 (1967) 60)
• 友人のネットワークを通して世界中のどの人へも到達するに
は何ステップ必要か？
• ネブラスカ州オハマの住人160人からボストンの株式仲買人
まで手紙を転送（ただし、手紙を受け取った人はファースト
ネームで呼び合うような人にしか手紙を送ってはならない）
• (6 degrees of separation = ６次の隔たり)
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 : 大きいまま
５．Scale Free
80対20の法則
Zipf の法則（単語の出現頻度Hardy）
Zipf の法則（単語の出現頻度Dickens）
Zipf の法則（日本の都市人口）
Gutenberg-Richterの関係式(地震)
M ：マグニチュード(= 振幅の対数)
Log（地震数） = a – b M
マグニチュードについて
1935年，リヒター(Richter)によって
導入された。震源から100km離れた
地点に置かれた当時の標準地震計
(ウッド・アンダーソン型地震計)で記
録された揺れの最大振幅をミクロン
(μm)単位で表わし、その数値の対
数をマグニチュードとして定義した。
防災科学技術研究所ＨＰより
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度に１つだけ節点を増やす。
• (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 のべき乗分布
６．Random Growth Network
m0 = 3
m=2
Loop = 100
Random Growth Network の次数分布確率密度
Random Growth Network の指数関数分布
Network の種類と特徴
７．結論
(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 では指数関数分布が得られる。

Download Report