大学院共通授業科目「トポロジー理工学特別講義 Ｉ 」
ネットワークトポロジー

複雑ネットワークの統計的性質

北海道大学 工学研究科 応用物理学専攻
矢久保 考介ネットワークとは ．．．

ノード

リンク

ノード： 場所、人、物、言葉、概念、・・・
リンク： ノードとノードの関係

様々なネットワーク
ネットワークノード

リンク

インターネット

コンピュータ

通信回線

WWW

Webページ

リンク

相互作用

電子

クーロン相互作用

人的コミュニケーション 人

友人関係、敵対関係

交通網

空港

路線

映画俳優ネットワーク

映画俳優

共演関係

論文共著

研究者

共著関係

論文引用

論文

引用関係

単語ネットワーク

単語

文中に隣接（次隣接）して位置するネットワークの例１： 地下鉄ネットワーク
ノード：駅
リンク：路線ネットワークの例２： コンピュータ・ネットワーク
ノード：コンピュータ
リンク：回線ネットワークの例3： インターネット
ノード：コンピュータ
リンク：物理回線

ネットワークの例4： WWW
ノード：Webページ
リンク：ハイパーリンク

ネットワークの例5： 単語のネットワーク
ノード：単語リンク：文章中で隣り合うか一つ飛ばしに隣り合う関係
kingyellow

type

land

race

poem
apple

MARCELLUS Good now, sit down, and tell me, he that knows, Why thishistory
same strict and most observant watch So
nightly toils the subject of the land, And why such daily cast of brazen cannon, And foreign mart for implements of war;
Why such impress of shipwrights, whose sore task Does not divide the Sunday from the week; What might be toward,
jobjoint-labourer with the day: Who is't that can inform me?
that this sweaty haste Doth make the night
HORATIO That can I; At least, the whisper goes so. Our last king, Whose image even but now appear'd to us, Was, asblood
you know, by Fortinbras of Norway, Thereto prick'd on by a most emulate
in which ourmanpride, Dared to the combat;
valiant Hamlet-- For so this side of our known world esteem'd him-- Did slay this Fortinbras; who by a seal'd compact,
Well ratified by law and heraldry, Did forfeit, with his life, all those his lands Which he stood seized of, to the conqueror:
Against the which, a moiety competent Was gaged by our king; which had return'd To the inheritance of Fortinbras, Had
he been vanquisher; as, by the same covenant, And carriage of the article design'd, His fell to Hamlet. Now, sir, young
Fortinbras, Of unimproved mettle hot and full, Hath in the skirts of Norway here and there Shark'd up a list of lawlessresolutes, For food and diet, to some enterprise That hath a stomach in't; which is no other-- As it doth well appear unto
our state-- But to recover of us, by strong hand And terms compulsatory, those foresaid lands So by his father lost: andthis, I take it, Is the main motive of our preparations, The source of this our watch and the chief head Of this post-haste
and romage in the land.

ネットワークの例6：
酵母におけるタンパク質間相互作用ネットワーク
ノード：蛋白質
リンク：相互作用ネットワークの例7： 科学論文共著関係ネットワーク
ノード：研究者
リンク：共著関係

ネットワークに関する理論的扱い＝
グラフ理論（１８世紀のオイラーを創始者とする数学：トポロジーの起源）

膨大なノード数をもつ複雑なネットワーク

複雑ネットワーク科学（複雑ネットワークの統計的性質を解明する）
1998〜ネットワークの一般的性質●ネットワーク構造に距離の概念はない
同じ構造●連結性が変われば構造は変わる
異なる構造
連続変形しても繋ぎ替えがなければ同じ構造

トポロジー

ネットワークを特徴付ける様々な量● 総ノード数 N
ネットワークのサイズ● 総リンク数 n● ノードの次数 ki
ノード i から出ているリンク数● 平均次数 <k>k =1ki∑N i2n = k N● ノード間距離 d

ノード対を結ぶリンク数の最小値
jid ij = 2● ネットワーク径 l
ネットワーク内の全てのノード間距離の最大値● 平均ノード間距離 <d>
ネットワーク内の全てのノード間距離の平均値

● クラスター係数 C
ノード i の次数ki
ノード i の近接ノード数kii
近接ノードが互いにリンクする組み合わせの数 : SiS i = ki C2 =iki (ki − 1)2

近接ノードが実際にリンクしている数 ： Ei

ノード i のクラスター係数 ： Ci
Ci =

Ei
2 Ei
=
Si ki (ki − 1)

ネットワークのクラスター係数 ： C
C = Ci
Cはネットワークがどの程度密に繋がっているかを表す量

完全グラフ
C=1
ツリー構造
C=0

多くの現実ネットワークに共通の性質
１．スモールワールド性
ネットワークサイズNに比べて平均ノード間距離が圧倒的に小さいl ∝ ln N
高いクラスター性C ≈0C ≈1

２．スケールフリー性
次数 ki の分布関数がベキ関数(A) 俳優の共演関係、(B) WWW、(C) 電力網

論文の共著関係。
(M)数学、(NS)神経科学

ベキ分布

現実のネットワークのベキ分布

P(k ) ∝ k −γ

(k >> 1)

スケールフリー性 （特徴的なkが存在しない）
γ=2.1
γ=2.4
γ=2.1・・・(WWW)(Internet)
(NS)

ハブ構造
巨大なリンク数を持つノード（ハブ）が少数ながら存在する

３．フラクタル性
フラクタル＝自身の一部分と相似な構造（自己相似）＝特徴的長さが無い構造

自然界の至るところに遍在フラクタル構造とフラクタル次元：l1

N ∝ll2

DC

サイズ l の箱に含まれる質量 N （測度）− DB
N B ∝ lB
サイズ lB の箱で被覆するのに必要な最小の箱の数 NBlB

D ・・・ フラクタル次元（非整数）身の回りの複雑ネットワークはフラクタルか？

ネットワーク距離 lB のサブグラフで被覆するのに必要なサブグラフの最小数 NB−D
N B ∝ lB

フラクタル
lB = 6
NB = 4

WWWと俳優のネットワーク−DN B ∝ lB

フラクタル・ネットワーク"Self-similarity of complex networks"
C. Song, S. Havlin, and H. A. Makse
Nature 433, 392 (2005).

蛋白質相互作用ネットワーク−DN B ∝ lB

フラクタル・ネットワーク

細胞内生化学経路ネットワーク−DN B ∝ lB

フラクタル・ネットワーク

インターネット

蛋白質相互作用ネットワーク

N B ∝ exp(l B / l0 )
非フラクタル・ネットワーク

多くの現実ネットワークに共通の性質
１．スモールワールド性
２．スケールフリー性
３．フラクタル性
全ての現実ネットワークがこれらの性質を共有しているわけではない！

何故、このような共通性が存在するのか？

スモールワールド性の起源
Watts-Strogatz （1998）
規則性とランダム性の両方を取り入れたネットワーク・モデルにより大きなクラスター係数と小さなネットワーク径を両立させた。

(1)初めにN個のノードからなるリング状の格子を考え、ノード間はK個の最近接(N>>K>>lnN)まで結合している。
（規則性）
N=83( K − 2)
K=4
C=4( K − 1)

(2) 確率pでランダムにリンクの繋ぎ替えをする。
ただし、二重リンクや自己リンクを禁止する。（ランダムネス）

クラスター係数p=0でのクラスター係数
C ( 0) =3( K − 2)4( K − 1)の３角形が３角形のままでいられる確率(1 − p )33( K − 2)
(1 − p )3C ( p) =4( K − 1)

平均ノード間距離

N 1/ dl=f ( pKN )Kf (u ) =4u 2 + 4u

tanh−1uu 2 + 4u

⎧ const. u << 1f (u ) = ⎨⎩ln(u ) / u u >> 1スモールワールド性K>>1p=0

p=1

34NKKN
ln N
ln KCl次数分布関数f (k ,K )P (k ) = ∑ K / 2 Cn (1 − p ) pnn =0

K / 2− n( pK / 2) k − K / 2− n − pK / 2e(k − K / 2 − n)!

ランダム・ネットワークと本質的に同じ
大きな C と小さな l !

スケールフリー性の起源
Barabasi-Albert モデル（1999）
成長と優先的選択のメカニズムによりスケール・フリー性を有するネットワーク・モデルの構築に成功。

(1) 初めにm0 個（少数）のノードが存在している。
各時間ステップで１個のノードを加える。このノードはm(≦m0)本のリンクを持っており、既存のノードのどれかと結合する。（成長）(2) 新しく加わるノードが既存のノードとリンクで結ばれる確率は、kiΠ ( ki ) =∑ kiiで与えられる。（優先的選択）

2/6
3/10

3/10
2/6
2/10

2/62/10

Barabasi-Albert モデル

スケール・フリー性

ハブ構造

● ネットワーク径ln Nl≈ln ln N（スモールワールド性）● クラスター係数

ランダム・ネットワークと同程度
現実のネットワークと不一致

さらなるネットワーク・モデルの必要性

フラクタル性の起源
Song el at. (Nature, 2005)
複雑ネットワークにフラクタル性があることを発見
DCN ∝ll ∝ log N（フラクタル性）（スモールワールド性）− DBN B ∝ lB
Yook el at. (PRL, 2005)
フラクタルネットワークはdisassortative
Goh el at. (PRL, 2006)
フラクタル・ネットワークのスケルトン構造は臨界的Song el at. (Nature Phys., 2006)
モージュールの入れ子構造
フラクタル性の起源は?

フラクタル構造
臨界現象
平衡系臨界現象非平衡系 自己組織化臨界性 (SOC)

特徴的長さの無い
支配方程式

フラクタル・ネットワークの形成∆φ = 0適応度モデルにおける臨界的性質とフラクタル性
N=2000N=4000N=6000N=8000N=10000

15.0

あるパラメータαに対する相関長
α=0.26 (=αc) が臨界点

10.0

5.00.00.00.5

α1.0

1.5

1.00.5Pc(s)M

Average node-pair distance (lNP)

20.0

0.0
0.0 1.0 2.0 3.0 4.0 5.0 6.0

α/αc

秩序変数

10410310210110010-110010s

1102

クラスター・サイズ分布

Atα=αc
310210Box-covering

Cluster-growing

210Nc

NB101110010 010010110210 010lB110lc

ネットワークは臨界点でフラクタル構造

DB = DC = 1.77

210

フラクタル性とスモールワールド性との関係
複雑ネットワークの臨界現象

フラクタルフラクタルDD

dユークリッド

log lBlog N Blog N B

通常の臨界現象d →∞− lB / l0
スモールワールド N B ∝ elog lB複雑ネットワークの科学の展開● SF、SW、フラクタル性の相互関係
スケールフリー性

同時成立する
モデルは？

γとDに関係があるか

スモールワールド性

クロスオーバー

フラクタル性● スケールフリー性とスモールワールド性
知人モデル
J. Davidsen et al.: Phys. Rev. Lett. 99, 128701 (2002).

閾値モデル
・・・

M. Boguna et al.: Phys. Rev. E 68, 036112 (2003).

● スケールフリー性とフラクタル性
繰り込まれたノードの次数k’とそのノードの繰り込み前のノード集合の最大次数kが比例し、比例係数が繰り込みサイズのdk乗に比例するスケールフリーなフラクタル・ネットワークの場合、DBγ = 1+dk

その他の問題● 自己組織化臨界による複雑ネットワーク形成
何故現実のネットワークがフラクタル構造を取るか？
● 重み付けられたネットワークの性質
0.3

4 .3

1.5

0.
1

2.1

航空路線ネットワーク
株価の相関ネットワーク
血管網・・・・● ネットワーク上の物理
噂の蔓延
お金の流通拡散問題

世論形成

スピン問題

参考書
一般書
「新ネットワーク思考 ー世界のしくみを読み解く」
バラバシ （日本放送出版協会）「複雑な世界、単純な法則 ーネットワーク科学の最前線」
マーク・ブキャナン （草思社）「私たちはどうつながっているのか ーネットワークの科学を応用する」
増田直紀（中公新書）

やや専門的「複雑ネットワークの科学」
増田直紀、今野紀雄 （産業図書）

専門的“Characterization of complex networks: A survey of measurements”
L. da F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas,Adv. Phys. 56, 167 (2007).
“The structure and function of complex networks”
M. E. J. Newman, SIAM Rev. 45, 167 (2003).
"Evolution of Networks: From Biological Nets to the Internet and WWW”
S. N. Dorogovtsev and J. F. F. Mendes (Oxford Univ Pr., 2003).
“Statistical mechanics of complex networks”
R. Albert and A. L. Barabasi, Rev. Mod. Phys. 74, 47 (2002).
“Evolution of networks”
S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002).

レポート課題：与えられた N 個のノードに対して、これらの全てのノード対を確率 p で結ぶ（リンクを張る）ことで出来るネットワークを考える。十分大きなNにおけるこのネットワークに対して以下の問に答えよ。
(1) 平均次数を計算せよ(2) クラスター係数を計算せよ(3) 次数分布関数を求めよ