大学院共通授業科目 トポロジー理工学特別講義 Ｉ ネットワークトポロジー 複雑ネットワークの統計的性質 北海道大学 工学研究科 応用物理学専攻 矢久保 考介

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

大学院共通授業科目

「トポロジー理工学特別講義 Ｉ 」

ネットワークトポロジー

北海道大学 工学研究科 応用物理学専攻

矢久保 考介

ネットワークとは ．．．

ノード

リンク

ノード： 場所、人、物、言葉、概念、・・・

リンク： ノードとノードの関係

文中に隣接（次隣接）して

位置する

単語

単語ネットワーク

引用関係

論文

論文引用

共著関係

研究者

論文共著

共演関係

映画俳優

映画俳優ネットワーク

路線

空港

交通網

友人関係、敵対関係

人

人的コミュニケーション

クーロン相互作用

電子

相互作用

リンク

Webページ

WWW

通信回線

コンピュータ

インターネット

リンク

ノード

ネットワーク

様々なネットワーク

ネットワークの例１： 地下鉄ネットワーク

ノード：駅

ネットワークの例２： コンピュータ・ネットワーク

ノード：コンピュータ

ネットワークの例

3： インターネット

ノード：コンピュータ

ネットワークの例

4： WWW

ノード：

Webページ

MARCELLUS Good now, sit down, and tell me, he that knows, Why this 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, that this sweaty haste Doth make the night joint-labourer with the day: Who is't that can inform me?

HORATIO That can I; At least, the whisper goes so. Our last king, Whose image even but now appear'd to us, Was, as you know, by Fortinbras of Norway, Thereto prick'd on by a most emulate pride, Dared to the combat; in which our 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 lawless resolutes, 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: and this, 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.

king

land

poem

history

job

apple

man

yellow

type

blood

race

ネットワークの例

5： 単語のネットワーク

ノード：単語

リンク：文章中で隣り合うか一つ飛ばしに隣り合う関係

ネットワークの例

6：

酵母におけるタンパク質間相互作用ネットワーク

ノード：蛋白質

ネットワークの例

7： 科学論文共著関係ネットワーク

ノード：研究者

ネットワークに関する理論的扱い

＝

グラフ理論

（１８世紀のオイラーを創始者とする数学：トポロジーの起源）

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

複雑ネットワーク科学

（複雑ネットワークの統計的性質を解明する）

1998∼

ネットワークの一般的性質

●ネットワーク構造に距離の概念はない

同じ構造

●連結性が変われば構造は変わる

異なる構造

連続変形しても繋ぎ替えがなければ同じ構造

トポロジー

ネットワークを特徴付ける様々な量

● 総ノード数

N

ネットワークのサイズ

● 総リンク数

n

●

ノードの次数

k

_i

ノード i から出ているリンク数

● 平均次数

<k>

∑

=

k

N

k

1

2

n

=

k

N

●

ノード間距離

d

i

j

ノード対を結ぶリンク数の最小値

2

=

ij

d

● ネットワーク径

l

ネットワーク内の全てのノード間距離の最大値

●

平均ノード間距離

<d>

ネットワーク内の全てのノード間距離の平均値

●

クラスター係数

C

i

i

ノード i の次数k

_i

ノード i の近接ノード数k

_i

近接ノードが互いにリンクする組み合わせの数 : S

_i

2

)

1

(

−

=

=

k

k

C

S

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

_i

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

_i

)

1

(

2

−

=

=

k

k

E

S

E

C

ネットワークのクラスター係数 ： C

C

C

=

Cはネットワークがどの程度密に

繋がっているかを表す量

完全グラフ

C=1

ツリー構造

C=0

多くの現実ネットワークに共通の性質

１．スモールワールド性

N

l

∝

ln

ネットワークサイズ

Nに比べて平均ノード間距離が

圧倒的に小さい

高いクラスター性

0

≈

C

C

≈

1

２．スケールフリー性

次数 k

_i

の分布関数がベキ関数

論文の共著関係。

(M)数学、(NS)神経科学

ベキ分布

(A) 俳優の共演関係、(B) WWW、(C) 電力網

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

)

1

(

)

(

k

∝

k

−

k

>>

P

γ

スケールフリー性

（特徴的なkが存在しない）

γ=2.1 (WWW)

γ=2.4 (Internet)

γ=2.1 (NS)

・・・

ハブ構造

巨大なリンク数を持つノード（ハブ）が

少数ながら存在する

３．フラクタル性

フラクタル＝自身の一部分と相似な構造（自己相似）

＝特徴的長さが無い構造

フラクタル構造とフラクタル次元：

C

D

l

N

∝

D ・・・ フラクタル次元（非整数）

B

D

B

B

l

N

∝

−

1

l

2

l

_{サイズ l の箱に含まれる質量 N （測度）}

B

l

サイズ l

_B

の箱で被覆するのに必要な

最小の箱の数 N

_B

身の回りの複雑ネットワークはフラクタルか？

D

B

B

l

N

∝

−

ネットワーク距離 l

_B

のサブグラフで

被覆するのに必要なサブグラフの

最小数 N

_B

4

6

=

=

B

B

N

l

フラクタル

WWWと俳優のネットワーク

D

B

B

l

N

∝

−

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

"Self-similarity of complex networks"

C. Song, S. Havlin, and H. A. Makse

Nature 433, 392 (2005).

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

D

B

B

l

N

∝

−

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

細胞内生化学経路ネットワーク

D

B

B

l

N

∝

−

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

インターネット

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

)

/

exp(

l

l

₀

N

_B

∝

_B

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

多くの現実ネットワークに共通の性質

１．スモールワールド性

２．スケールフリー性

３．フラクタル性

全ての現実ネットワークがこれらの性質を

共有しているわけではない！

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

スモールワールド性の起源

Watts-Strogatz （1998）

規則性とランダム性の両方を取り入れたネットワーク・モデルにより

大きなクラスター係数と小さなネットワーク径を両立させた。

(1)初めにN個のノードからなるリング状の格子を考え、

ノード間はK個の最近接(N>>K>>lnN)まで結合している。

（規則性）

N=8

K=4

)

1

(

4

)

2

(

3

−

−

=

K

K

C

(2) 確率pでランダムにリンクの繋ぎ替えをする。

ただし、二重リンクや自己リンクを禁止する。（ランダムネス）

クラスター係数

)

(

/

1

pKN

f

K

N

l

d

=

u

u

u

u

u

u

f

4

tanh

4

4

)

(

2

1

2

+

+

=

−

⎩

⎨

⎧

>>

<<

=

1

/

)

ln(

1

const.

)

(

u

u

u

u

u

f

スモールワールド性

の３角形が３角形のままでいられる確率

p=0でのクラスター係数

)

1

(

4

)

2

(

3

)

0

(

−

−

=

K

K

C

3

)

1

(

−

p

3

)

1

(

)

1

(

4

)

2

(

3

)

(

p

K

K

p

C

−

−

−

=

平均ノード間距離

K>>1

l

C

p=1

p=0

4

3

N

K

K

N

K

N

ln

ln

大きな C と小さな l !

次数分布関数

∑

−

−

−

=

)!

2

/

(

)

2

/

(

)

1

(

)

(

e

n

K

k

pK

p

p

C

k

P

ランダム・ネットワークと

本質的に同じ

スケールフリー性の起源

Barabasi-Albert モデル（1999）

成長と優先的選択のメカニズムによりスケール・フリー性を

有するネットワーク・モデルの構築に成功。

(1) 初めに

m

₀

個（少数）のノードが存在している。

各時間ステップで１個のノードを加える。この

ノードは

m

(≦m

₀

)本のリンクを持っており、

既存のノードのどれかと結合する。（成長）

(2) 新しく加わるノードが既存のノードとリンクで

結ばれる確率は、

∑

=

Π

i

i

i

i

k

k

k )

(

2/6

2/6

2/6

2/10

3/10

3/10

2/10

で与えられる。（優先的選択）

Barabasi-Albert モデル

● ネットワーク径

N

N

l

ln

ln

ln

≈

（スモールワールド性）

● クラスター係数

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

ランダム・ネットワークと同程度

現実のネットワークと不一致

フラクタル性の起源

Song el at. (Nature, 2005)

複雑ネットワークにフラクタル性があることを発見

C

D

l

N

∝

（フラクタル性）

N

l

∝

log

（スモールワールド性）

B

D

B

B

l

N

∝

−

フラクタル性の起源は?

Goh el at. (PRL, 2006)

フラクタル・ネットワークのスケルトン構造は臨界的

Yook el at. (PRL, 2005)

フラクタルネットワークはdisassortative

Song el at. (Nature Phys., 2006)

モージュールの入れ子構造

フラクタル構造

臨界現象

平衡系臨界現象

非平衡系 自己組織化臨界性 (SOC)

特徴的長さの無い

支配方程式

0

=

φ

∆

フラクタル・ネットワークの形成

0.0 0.5 1.0 1.5 0.0 5.0 10.0 15.0 20.0 N=2000 N=4000 N=6000 N=8000 N=10000 Av e ra ge node -pair distance ( lNP )

α

適応度モデルにおける臨界的性質とフラクタル性

あるパラメータαに対する相関長

α=0.26 (=α

_c

) が臨界点

P

(s

)

s

M

α

/

α

秩序変数

クラスター・サイズ分布

10

10

10

10

10

10

N

l

10

10

10

10

10

10

10

N

l

Box-covering

Cluster-growing

Atα=α

_c

77

.

1

=

=

_C

B

D

D

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

通常の臨界現象

B

log l

B

log

N

B

log l

B

log

N

D

d

D

フラクタル

ユークリッド

フラクタル

∞

→

d

スモールワールド

e

N

∝

複雑ネットワークの臨界現象

フラクタル性とスモールワールド性との関係

複雑ネットワークの科学の展開

● SF、SW、フラクタル性の相互関係

スケールフリー性

スモールワールド性

フラクタル性

クロスオーバー

γとDに関係があるか

同時成立する

モデルは？

● スケールフリー性とスモールワールド性

閾値モデル

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

・

・

・

知人モデル

J. Davidsen et al.: Phys. Rev. Lett. 99, 128701 (2002).

● スケールフリー性とフラクタル性

k

B

d

D

+

=

γ 1

繰り込まれたノードの次数k’とそのノードの繰り込み前のノード集合の最大次数

kが比例し、比例係数が繰り込みサイズのd

乗に比例するスケールフリーなフラ

クタル・ネットワークの場合、

● 自己組織化臨界による複雑ネットワーク形成

● 重み付けられたネットワークの性質

4.3

0.

1

2.1

0.3

1

.5

航空路線ネットワーク

株価の相関ネットワーク

血管網

・・・・

● ネットワーク上の物理

噂の蔓延

お金の流通

拡散問題

世論形成

スピン問題

何故現実のネットワークがフラクタル構造を取るか？

その他の問題

参考書

一般書

「新ネットワーク思考 ー世界のしくみを読み解く」

バラバシ （日本放送出版協会）

「複雑な世界、単純な法則 ーネットワーク科学の最前線」

マーク・ブキャナン （草思社）

「私たちはどうつながっているのか ーネットワークの科学を応用する」

増田直紀（中公新書）

「複雑ネットワークの科学」

増田直紀、今野紀雄 （産業図書）

やや専門的

専門的

“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”

レポート課題：

与えられた N 個のノードに対して、これらの全

てのノード対を確率 p で結ぶ（リンクを張る）こ

とで出来るネットワークを考える。十分大きなN

におけるこのネットワークに対して以下の問に

答えよ。

(1) 平均次数を計算せよ

(2) クラスター係数を計算せよ

(3) 次数分布関数を求めよ