位相不変量によるネットワークの解析

廣田 裕二

2005 年 2 月 24 日

電子情報工学科

i

目次

目次

第1章

序章

1

1.1

はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

ネットワークを特徴付ける指標 . . . . . . . . . . . . . . . . . . . . . .

3

1.3

これまでのネットワーク研究について . . . . . . . . . . . . . . . . . . .

6

1.4

位相幾何学（トポロジー） . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.5

ベッチ数解析 [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

1.6

本研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

ベッチ数解析

15

2.1

はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2

解析対象のネットワーク生成. . . . . . . . . . . . . . . . . . . . . . .

15

2.3

解析方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.4

解析結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.5

まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

攻撃、故障とベッチ数の関係

23

3.1

はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.2

ベッチ数と耐故障性の関係の検証 . . . . . . . . . . . . . . . . . . . . .

24

3.3

ベッチ数と耐攻撃性の関係の検証 . . . . . . . . . . . . . . . . . . . . .

26

3.4

まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

結論

38

第2章

第3章

第4章

ii

目次
付録 A

Pajek

40

データ形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

プログラムソース

41

B.1

ER-Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

B.2

ランダムネットワーク生成プログラム . . . . . . . . . . . . . . . . . . .

42

B.3

BA-Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

B.4

ベッチ数を求めるプログラム. . . . . . . . . . . . . . . . . . . . . . .

43

A.1
付録 B

参考文献

54

iii

図目次

図目次

1.1

インターネットのトラフィック発生の様子 . . . . . . . . . . . . . . . .

2

1.2

航空路線図 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

ネットワークの例. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4

ネットワークの距離を求める手順 . . . . . . . . . . . . . . . . . . . . .

6

1.5

ER-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.6

スケールフリーネットワークの接続辺の頻度分布 . . . . . . . . . . . . .

10

1.7

位相幾何学的に見たときのコーヒーカップとドーナツの関係 . . . . . . .

11

1.8

単体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.9

ベッチ数解析のアルゴリズムの概要 . . . . . . . . . . . . . . . . . . . .

13

2.1

ランダムネットワークの接続辺分布 . . . . . . . . . . . . . . . . . . . .

17

2.2

スケールフリーネットワークの接続辺分布 . . . . . . . . . . . . . . . .

17

2.3

ランダムネットワーク . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.4

スケールフリーネットワーク. . . . . . . . . . . . . . . . . . . . . . .

18

2.5

ランダムネットワークのベッチ数 βn の分布. . . . . . . . . . . . . . .

21

2.6

スケールフリーネットワークのベッチ数 βn の分布 . . . . . . . . . . . .

21

3.1

スケールフリーネットワークに対して辺故障を 200 回行い、各故障回数
におけるベッチ数の変化 . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2
3.3

25

スケールフリーネットワークに対して辺故障を 200 回行い β0 が 43 以上となったときの平均故障回数とベッチ数 β1 の関係 . . . . . . . . . . . .

25. . . . . . . . . . . . . . . . . . . . . . .

26

ネットワークの頂点攻撃の例

iv

図目次

3.4

ネットワークの辺攻撃の例 . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.5

ランダムネットワークに対する辺攻撃回数によるベッチ数の変化. . . .

28

3.6

ランダムネットワークに対する頂点攻撃回数によるベッチ数の変化 . . .

28

3.7

RN-A について各頂点攻撃回数のネットワークの様子 . . . . . . . . . .

29

3.8

RN-B について各頂点攻撃回数のネットワークの様子 . . . . . . . . . .

30

3.9

ランダムネットワークに対して頂点攻撃を行い β0 が 30 以上になったときの攻撃回数とベッチ数 β1 の関係 . . . . . . . . . . . . . . . . . . . .

31

3.10

スケールフリーネットワークに対する辺攻撃回数によるベッチ数の変化 .

33

3.11

スケールフリーネットワークに対する頂点攻撃回数によるベッチ数の変化

33

3.12

SFN-A について各頂点攻撃回数のネットワークの様子 . . . . . . . . . .

34

3.13

SFN-B について各頂点攻撃回数のネットワークの様子 . . . . . . . . . .

35

3.14

スケールフリーネットワークに対して頂点攻撃を行い β0 が 70 以上となったときの攻撃回数とベッチ数 β1 の関係 . . . . . . . . . . . . . . . .

36

v

表目次

表目次

1.1

図 1.3 のクラスター係数 . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

図 1.3 の平均経路長 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.1

ベッチ数解析の結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

第1章

序章

1

第1章

序章
1.1

はじめに

我々の身近には様々なネットワークが存在している。まず、物理的な繋がりを持つネッ
トワークの例を挙げると、インターネット網のネットワーク、送電線のネットワーク、道路網のネットワーク、脳のニューラルネットワークなどが挙げられる。インターネット網のネットワークでは、コンピューターを頂点とし、コンピューター同士が LAN ケーブルで繋っているのを辺で表している。図 1.1 はインターネット網のトラフィック発生の様子を表したもので、図 1.2 は航空路線図を表している。また、このような物理的な関係以外に抽象的な関係を表したネットワークも存在する。例を挙げると、捕食関係にある食物連
鎖、友人・知人関係のネットワーク、リンク関係にある WWW などもネットワークとして見なすことができる。このように我々の身の回りの事象はネットワークとして変換されて表されることが多く、これらのネットワークを解析することは重要である。例として、
化学物質による刺激を与え遺伝子発現変動パターンから遺伝子間の関連構造をネットワー
クに変換し、解析することにより DNA の制御機構の詳細を調べることである。これにより、創薬及び生命機能の解明に役立つ。
またネットワークを解析する指標としては、ネットワークの大きさを表す直径、ネット
ワークの一塊さを表すクラスター係数、ネットワークの平均の距離を表す平均経路長などが挙げられる。これらに加えて、位相不変量を導入することにより、詳細なネットワークの構造を解析することが期待できる。ここで、位相不変量とは位相幾何学（トポロジー）と呼ばれる学問の値のことで、位置と形相に依存しない不変な値のことである。本研究で

第1章

2

序章

図 1.1

インターネットのトラフィック発生の様子

図 1.2

航空路線図

は、その位相不変量の 1 つであるベッチ数 βn を用い解析を試みた。ここでベッチ数 βnとは、独立な n 次元ループの数のことである。具体的には β0 は辺で繋がっている塊り（クラスター）の数、β1 は独立な閉ループの数を表している。このベッチ数の詳細については、後ほど説明する。
この章では、ネットワークの基礎、これまでのネットワーク研究、解析に用いた位相幾何学について解説した後、本研究の目的について述べる。

第1章

序章

3

1.2

ネットワークを特徴付ける指標

この節では、従来ネットワークを特徴付ける指標である直径、クラスター係数、平均経路長について説明する。ここでは、通常グラフと記述されるところを解析対象であるネットワークと置き換えている。

1.2.1

クラスター係数クラスター係数とはネットワークの集合具合を表すものである。ある頂点 i のクラス
ター係数というものは、実際に存在しているクラスターの数 Ei を可能なクラスターの数で割ったもので定義され (1.1) 式で表される。また、ネットワークのクラスター係数 C
は、(1.2) 式のようにすべての頂点のクラスター係数の平均で表わされる。ここで、可能なクラスターの数とは、頂点 i が接続しているすべての頂点から 2 つ選び出す組み合わせの数である。
N

1 X
C=
Ci
N

(1.1)

i=1

Ci =

2Ei
ki (ki − 1)

ki : 頂点 i が持つ辺の数(1.2)

例として図 1.3 のクラスター係数を求めると表 1.1 のようになる。表 1.1 の各頂点のクラ89
スター係数の平均 300= 0.296 が図 1.3 のクラスター係数である。

表 1.1

図 1.3 のクラスター係数

i

1

2

3

4

5

6

7

8

9

10

Ci

2
3

1
3

0

1
2

2
15

1
3

1
3

1
3

1
3

0

第1章

4

序章
3

6

2

10
9

5

8
4
1

7

図 1.3

1.2.2

ネットワークの例

平均経路長ある頂点 i の平均経路長 Li というのは、(1.3) 式に示したように、任意の異なる 2 頂点
間 i, j(i 6= j) の距離 dij の平均である。ここで、距離とは最短経路長のことである。また、ネットワークの平均経路長 L は、(1.4) 式のようにすべての頂点の平均経路長の平均で表
される。

N

L=
Li =

1 X
Li
N
i=1
1 X
N −1

(1.3)
dij

(1.4)

j6=i

図 1.3 を例に考える各頂点の平均経路長 Li は表 1.2 で表され、各頂点の平均経路長の平均 L = 178
90 = 1.98 が図 1.3 の平均経路長となる。
表 1.2

図 1.3 の平均経路長

i

1

2

3

4

5

6

7

8

9

10

Li

17
9

20
9

2

15
9

12
9

16
9

15
9

2

20
9

17
9

第1章

序章

1.2.3

直径

5

ネットワークの直径とは、ネットワーク上の任意の 2 頂点間の距離の最大値であり、さらに一般に、任意の距離空間の部分空間に対して、その集合に含まれる 2 点の距離の上限として直径を考えることができる。つまり、d(x, y) で 2 点 x, y の距離を表すとき、集合S の直径 diam S は次のように与えられる。
diam S = sup d(x, y)

(1.5)

x,y∈S

直径が有限な値を持つとき、その集合は有界であるといわれる。ユークリッド空間の部分集合の場合、有界の定義は原点を中心とする十分大きな球にその集合が含まれることであるとしても同じことになる。
次に 2 頂点間 u, v の距離 d(u, v) を求めるのに用いた Moore’s Breadth First Search
アルゴリズムについて説明する。

Moore’s Breadth First Search Algorithm
始点を u、終点を v, 始点 u からある頂点までの距離を l(v) とする。

Step1. 頂点 u 以外のすべての頂点 i に対して l(i) = ∞ とし、始点 u の l(u) = 0 とする。
また始点 u をキュー Q に追加する。

Step2. Q 6= φ であれば、Q から点を取り出し、これを x とする。また、Q = φ ならば経路はない。

Step3. 始点 u から頂点 x に接続している頂点までの距離が無限大ならば、そこまでの距離を l(x) + 1 にし、Q に頂点 x に接続している頂点を追加する。

Step4. 終点 v までの距離 l(v) が無限大でなければ、l(v) が 2 頂点 u, v の距離となり、無限大ならば Step2. へ
図 1.4 は Moore’s Breadth First Search Algorithm におけるあるネットワークの 2 点間Start,Goal の距離を求めたものである。まず図 1.4 のように、Start に隣接する点の距離を定義し、さらにそれらの点に隣接する点の距離を定義していく。これを繰り返すことにより Goal までの距離が求めることができる。

第1章

6

序章
3

6

2

10
9

5

Goal
8
4
1

1Step
2Steps3Steps4Steps7

5Steps

Start

図 1.4

1.3

ネットワークの距離を求める手順

これまでのネットワーク研究について

ここでは、これまで行われてきたネットワーク研究 [1] について解説する。
まず、1959 年に Erdős と Rényi によってランダムネットワークというモデルが考えだされた。このモデルは、ネットワークの構造が完全にランダムにより、生成されるというものである。その後、1998 年に Watts と Strogatz は、WWW、映画共演ネットワー
ク、電力網、線虫の神経回路網などのネットワークがランダムネットワークや正則ネッ
トワークではなく、両者の特徴を併せ持つ中間的な特徴を持つことを明らかにした。中間的特徴というのは、任意の頂点間の距離が小さく、クラスター化されているということからスモールワールドネットワークと呼ばれている。さらに、1999 年に Albert-Lászió

Barabási らが、WWW のリンク関係について調査した結果、あるドキュメントにリンクが張られている（張っている）数とその頻度の関係がべき乗則に従っていることを明らかにした。これは、Yahoo やニュースサイトなどの有名なサイトの頻度というのは少なく、個人が持っているサイトのような知名度の低いサイトの頻度が大部分を占めるということである。このようなに極端に多くの接続辺（リンク）を持つ頂点（ドキュメント）も存在
し、系に特徴的なスケールを決めることができないためスケールフリーネットワークと呼ばれている。以下、各ネットワークの詳細について述べる。

第1章

序章

7

1.3.1

ランダムネットワーク

ランダムネットワークのモデルである ER モデル [?, er-mode] ついて解説する。
このネットワークは、頂点数を N , 頂点間の接続確率が p でランダムに接続辺が発生することによって生成される。図 1.5 はこのモデルにおいて、10 頂点の接続確率 p を変化させたときの接続辺の変化の様子を表している。

(a) p = 0.0(d) p = 0.75(b) p = 0.25(c) p = 0.50(e) p = 1.0
図 1.5 ER-model

このネットワークの各頂点の次数が k となる確率 p(k) はp(k) = N −1 Ck pk (1 − p)N −1−k(1.6)

となり、二項分布に従う。さらに、N → ∞, p → 0, pN → λ の極限ではp(k) = e−λ

λk
k!

(1.7)

第1章

8

序章

というように、ポアソン分布になる。この分布の平均、分散はともに λ であるので、全ての頂点の次数は統計的に等しい数であるといえる。図 1.5 はこのモデルにおいて頂点数

N = 10, 000, p = 0.0015 を与えて生成したランダムネットワークで、頂点の次数の頻度分布を表している。図のように次数平均 < k > でピークを持つポアソン分布となっているのがわかる。
また、このモデルは次のような性質を持つ。
頂点数 N 、接続辺を張る確率が p(N ) であるランダムネットワークがある。一般にランダムネットワークがある性質 Q を持っている確率を考える。その確率を PN,p (Q) とすると、ある臨界確率 Pc (N ) が存在し、(2.3) の式を満たす。

lim PN,p (Q) =

N →∞




0

if



1

if

p(N )
→0
pc (N )p(N )→∞pc (N )

(1.8)

これは、ランダムネットワークがある性質 Q を持つ確率は、p の変化により緩やかに変化するのではなく、急激に変化するということを表している。

1.3.2

スモールワールドネットワーク

さらに、1998 年に Cornel 大学の Duncan Watts は、(1.2) 節で述べた平均経路長、クラスター係数によりスモールワールドネットワークを次のように定義した。

• スモールワールドネットワークは、頂点数 n が大きく、疎に結合した分散グラフ(n À kmax À 1) であり、L がランダムグラフと近く（L ∼ Lrand ）、C がランダ
ムグラフに比べて極めて大きい（C À Crand ）ものである。
（ただし、Lrand ,Crandは同じ頂点数、辺の数のランダムネットワークにおける平均経路長、クラスター係数であり、kmax は頂点から出ている辺の数の最大値である。）
具体的には、スモールワールドネットワークは β モデルにより定義されている。このモデルは、図 1.3.2 にまず n 個（ここでは 16 個）の頂点がそれぞれ近傍 k 頂点（ここでは 4 頂点）に辺が張られている規則的なグラフを考える。次に、各辺に対して、確率 p でランダムに選んだ頂点と辺の繋ぎなおしを行う。p = 0 のときは、全く繋ぎなおしを行わないことに相当し、p = 1 のときは、全ての辺を繋ぎなおしたランダムネットワークとな

第1章

9

序章

る。この中間の値では、近傍を結ぶ規則的な辺とランダムに繋がれた辺が混在するネット
ワークとなる。このとき、C が大きく L が小さいネットワークとなり、これをスモール
ワールドネットワークと呼ぶ。
さらに Watts は、映画俳優の共演ネットワーク、送電線網、線虫の神経回路を例にとって C と L を調べたところ、このスモールワールドネットワークの性質を持つことがわかった。また、その後、WWW、インターネット網、食物連鎖のネットワーク、科学論文の共著関係、生物の代謝ネットワーク、航空路線、Java の class diagram など様々なネットワークがスモールワールドネットワークであると報告されている。

(a) p = 0

1.3.3(c) p = 1.0

スケールフリーネットワーク

さらに、1999 年に Albert-Lászió Barabási は、Web ページのリンク関係において、各ドキュメントがどのくらい他のドキュメントからリンクされているかを調べた。その結果、あるドキュメントにリンクされている数 n とその頻度 p の関係が p ∝ nγ （典型的には −2.5 ≤ γ ≤ −1）となるべき乗則に従うことがわかった。
これはほとんどのドキュメントは数個以下のリンクしか持たないが、Yahoo!などのごく少数のドキュメントは 100 万個もの多数のリンクを持つということを表している。
また、スケールフリーネットワークの生成には、次のような性質を持つ BA モデルを用いた。。

• 成長性:初期頂点から頂点を 1 個ずつ追加していく• 優先的選択:次数 ki 大きいほど、頂点 i へ接続される確率が高くなる
BA モデル [3] のアルゴリズムは次の通りである。

第1章

10

序章

• 初期頂点として、m0 個の頂点を配置する。
• 頂点数が N 未満である場合、以下を実行する。
– 頂点を 1 個追加する。
– 追加した頂点から（1.9）式の確率に従い、他の（m ≤ m0 ）個の相異なる頂点へ接続する。

ki + 1Π(ki ) = X(kj + 1)(1.9)

j

このアルゴリズムにより生成されたスケールフリーネットワークの各頂点の接続辺の頻度分布を両対数で表したのが図 1.6 である。このように、次数が多い頂点の頻度は少な
く、次数が少ない頂点が大部分を占めていることがわかる。次数が多い頂点はある一塊のネットワークであるクラスター同士を繋ぐ重要な頂点であり、ハブと呼ばれる。このようなハブを持つネットワークは、全ての頂点（辺）に対して等確率で起こる故障には強いが、ハブを意図的に攻撃されることには弱いという性質を持っている。
4

10

p 102

0

10 0
10

図 1.6

1

10

2

n

10

スケールフリーネットワークの接続辺の頻度分布

第1章

序章

11

1.4

位相幾何学（トポロジー）

1.4.1

概要

次に、今回解析に用いた位相幾何学の概要について説明する。位相幾何学とは、長さ・大きさなどの量的関係を無視し、図形相互の位置や繋がり方などを、変形させることによりその図形の不変な性質を見つけたり、そのような変形のもとでどれほど異なる図形があるかを研究する幾何学である。
例として、位相幾何学的に見たときのコーヒーカップとドーナツの関係を図 1.7 に示した。図 1.7 においてコーヒーカップは、柄のところに一つの穴が開いており、一つの物体である。また、ドーナツも真ん中に穴が開いた一つの物体であり、位相幾何学的にはコーヒーカップとドーナツは同形と見なすことが出来る。

図 1.7

1.4.2

位相幾何学的に見たときのコーヒーカップとドーナツの関係

基礎

単体

a0 , a1 , . . . , ar を n 次元空間に置かれた r + 1 個の点で、全てが r − 1 次元以下の部分空間に含まれないものとする。これら r + 1 この点の凸結合で表しえる点全体の集合を点ai (0 ≤ i ≤ r) によって生成される r 次元単体といい∆r = |a0 , a1 , · · · , ar |で表す。図 1.8 に例を挙げる。

複体

r 次元単体に対して、a0 , a1 , . . . , ar から任意の s + 1 個の点を選んだとき、この s + 1
個の点によって精製される単体を ∆r の面といい、s を個の面の次元という。複体は単体

第1章

12

序章
a1

a1

a1

a0

a3

a0
a0

a0

a2
a2

図 1.8

単体

を面と面で張り合わせて出来る図形のうち特に数学的性質のよいものであり、有限個の単体集合 K が次の二つの性質を満たすとき、K を複体という。

(i)

K に属する任意な単体の各面は K に属する。

(ii)

K に属する任意な二つの単体 ∆r1 と ∆r2 の非空な交わり ∆r1 ∩ ∆r2 は単体 ∆r1
および ∆r2 の面である。

K に属す単体の次元の最大値をこの複体の次元と呼び、dim(K) で表す。また、複体 Kに属する全ての単体の合併を複体 K の多面体といい、|K| と書き次のように表される。

|K| = {x|x ∈ ∆r ∈ K}

ホモロジー群
ベッチ数は位相不変量の 1 つである。これはホモロジー群と呼ばれるものの階数であり、複体 K の r 次元ホモロジー群は

Hr (K) =Zr (K)Br (K)(1.10)と表される。ここで、Zr (K) は輪体群、Br (K) は境界輪体群と呼ばれるものである。この量について次の性質が成り立つ。

• K と K 0 を二つの複体とする。図形 |K|, |K 0 | が位相同型なら、全ての r =0, 1, 2, . . . に対して Hr (K) ∼= Hr (K 0 ) である。

第1章

13

序章

複体 K の r 次元ホモロジー群 Hr (K) は加群であるので、加群の基本定理より

Hr (K) ∼= Z ⊕ · · · ⊕ Z ⊕ Zq1r ⊕ Zq2r ⊕ · · · ⊕ Zqsr

(1.11)rと表すことができ、Zq1r は位数 q1r の巡回群、i = 1, 2, . . . , s − 1 に対して qir は qi+1の約数である。しかも、この表現は一意である。上式の右辺の整数加群 Z の個数が Hr (K) の階数であり、K の r 次元ベッチ数といい、これを βr (K) と表す。

1.5

ベッチ数解析 [4]近年、計算トポロジーという分野が誕生しつつある。これは、計算機の進歩により単体複体のホモロジーが計算機により求めることが出来るようになったからである。これにより、トポロジーの位相不変量などを用いて画像認識、DNA などの巨大な分子の構造の解析などに用いられている。
本研究では位相不変量の 1 つであるベッチ数を求めることで解析を行った。そのアルゴ
リズムについて次節で解説する。

1.5.1

アルゴリズム図 2.3 がベッチ数を求めるアルゴリズムの概要である。

図 1.9

ベッチ数解析のアルゴリズムの概要

Step1. ネットワークからクリーク（完全部分グラフ）を調べ上げる。
Step2. q 頂点クリークを q − 1 次元単体とみなし、複体を構成する。
Step3. 複体のベッチ数を求める。

第1章

序章

1.6

本研究の目的14

我々の身の回りには物理的な繋がり以外にも、ある事象を抽象的な関係からネットワー
クに変換することができる。しかし、現実のネットワークを解析する場合、頂点数、辺の数が多いため、ネットワークの詳細な特徴を知ることは難しい。そこで、本研究では位相不変量の 1 つであるベッチ数を用いて、ネットワークを特徴付けることを目的とする。これにより、ネットワークのクラスターの数、閉ループの数などといった従来解析することが困難であった解析が可能となる。 また、スケールフリーネットワークの構造は、我々の身近なネットワークである。このスケールフリーネットワークの特徴として、全ての頂点（辺）に起こる故障に対しては強いが、頂点への意図的な攻撃には弱いことが知られている。よって、攻撃による耐性を高めることは、重要な課題であるといえる。以上のことより、スケールフリーネットワークについて攻撃、故障を行い、ベッチ数と耐攻撃性、耐故
障性の関係について調べることも目的とする。

第2章

ベッチ数解析

15

第2章

ベッチ数解析
2.1

はじめに1 章で述べたようにランダムネットワークは各頂点の接続辺の頻度分布があるところでピークを持つポアソン分布となる。また生成条件である頂点数と接続確率を同じにした場
合、各頂点の接続辺の頻度分布はスケールし、それに着目すると同じネットワーク構造を持つランダムネットワークであるといえる。このことはスケールフリーネットワークについても同様のことが言える。
ここでは、ランダムネットワーク、スケールフリーネットワークにおいて頂点数、辺の数を固定し、さらにネットワークの生成条件をそれぞれ同条件にすることで、同じネット
ワーク構造を持つネットワークをそれぞれ複数生成した。これらのネットワークを位相幾
何学（トポロジー）を用いて解析することより、ネットワークの分断されている数、独立な閉ループの数など、従来よりさらに詳細にネットワークを解析することが出来る。これ
により、ネットワークを特徴付けることを行った。

2.2

解析対象のネットワーク生成

まず、解析を行うネットワークの生成方法について説明する。ランダムネットワーク、
スケールフリーネットワークを比較するため、両方とも頂点数 200 個、辺の数 500 辺をそれぞれ 1000 個ずつ生成した。
ランダムネットワークの生成には、ER モデル [2] があるがこのモデルでは辺の数が全第2章

ベッチ数解析

16て一定とならないため用いなかった。代わりに頂点数、辺の数を指定し辺の数が目的とする 500 辺となるように、200 頂点から無作為に 2 頂点選び、その 2 頂点間を接続することにより生成した。また、生成されたランダムネットワークから無作為に 3 つ選び、それらの接続辺（頂点の次数）の頻度分布を表したのが図 2.1 である。このように、3 つのラン
ダムネットワークはほぼ同じようにスケールしており、ポアソン分布となっていることより目的とするランダムネットワークが得られていることを確認した。
スケールフリーネットワークの生成には、BA モデル [3] を用いている Tel Aviv

University の TANG[5] を用いた。生成条件には頂点数 200、初期頂点数 0 個、平均接続次数 5 を与え、1000 個のスケールフリーネットワークを生成した。また、生成された1000 個のスケールフリーネットワークの中から無作為に 3 つ選び、それらの接続辺の頻度分布を両対数で表したのが図 2.2 である。このように、3 つのスケールフリーネット
ワークはほぼ同じようにスケールしていることがわかる。また、傾き γ を最小二乗法で求めたところ、a = −1.16, b = −1.23, c = −1.30 となり、目的とするスケールフリー
ネットワークが得られていることを確認した。また生成されたネットワークをネットワー
ク解析ソフトウェアである pajek[6] を用いて表示させたところ、ランダムネットワーク
は図 2.3, スケールフリーネットワークは図 2.4 のようになった。図は頂点を赤、頂点間を辺で結ばれている様子を表している。また、(a) は頂点をサークル上に並べたときの接続の様子を表しており、(b) は pajek に実装されているアルゴリズムである Fruchterman

Reingold モデルを用いて表されている。このように、特別なアルゴリズムを用い表示したとしても複雑に絡み合っているのでネットワークの分割数がわかるくらいであり、閉ループの数など詳しいことはわからない。

17

ベッチ数解析

Number

40

a
b
c

20

0

10
Output Link Number
図 2.1

ランダムネットワークの接続辺分布

2

10

a
b
c

Number

第2章

1

10

0

10 0
10

図 2.2

1

10
Output Link Number
スケールフリーネットワークの接続辺分布

10

2

第2章

18

ベッチ数解析

(a) 頂点をサークル上に並べたときの接続(b) Fruchterman Reingold モデルでの接

の様子

続の様子
図 2.3

ランダムネットワーク(a) 頂点をサークル上に並べたときの接続(b) Fruchterman Reingold モデルでの接

の様子

続の様子
図 2.4

スケールフリーネットワーク

第2章

ベッチ数解析

2.3

解析方法

19

2.2 節において生成したランダムネットワーク、スケールフリーネットワークそれぞれ
1000 個のネットワークについて 1.5 で述べたベッチ数解析を行い、各ベッチ数の頻度分布を調べた。

2.4

解析結果

図 2.5, 2.6 はランダムネットワーク、スケールフリーネットワークのベッチ数解析の結果で、各ベッチ数の頻度分布を表している。スケールフリーネットワークの結果において、ネットワークの数を表す β0 が全てのスケールフリーネットワークで 1 となり、

β0 = 1 となる頻度が 1000 となったため省略している。
まず、ランダムネットワークの結果において、ネットワークの数を表す β0 に注目すると、ネットワークはほとんど分割されておらず、多いものでも 6 個程度であることがわかる。また、独立な閉ループの数を表す β1 に注目すると、平均 280 程度の閉ループが存在し、密なネットワークである。このことより、ランダムネットワークは接続辺を多く持
つ頂点への攻撃や全ての頂点に対して等確率で起こる故障に対して耐久性を持つことが予想される。さらに、β2 以上の高次元ベッチ数は得られなかったことより、単純なネット
ワークであることわかる。
次にスケールフリーネットワークの結果において、独立な閉ループの数を表す β1 に注
目すると分布を持つことがわかる。この β1 の分布（62 ≤ β1 ≤ 134）は、ランダムネット
ワークの分布（264 ≤ β1 ≤ 295）と比べると広い分布であるといえる。このような結果となったのは、ネットワークの生成に与える条件の数の違いからであると考えられる。ランダムネットワークにおける生成条件は、頂点数、辺の数であり、一方、スケールフリー
ネットワークにおける生成条件は、頂点数、辺の数、初期頂点数、平均接続次数となっている。また、このように β1 の分布が現れたことより、頂点数、辺の数が同じで、接続辺の頻度分布がスケールするようなネットワーク、つまり同じネットワーク構造を持つネットワークであっても、ネットワーク構造の疎密さが異なることを示している。このことより、同じ構造を持つスケールフリーネットワークであっても、閉ループの数を表す β1 の

第2章

20

ベッチ数解析

違いにより、ネットワークの耐久性に違いが出ることが予想される。よって、ベッチ数を用いて耐久性が高いネットワークの構築に期待できる。また、この解析結果より、ランダ
ムネットワークにおいて β1 が最も小さいネットワークを RN-A、最も大きいネットワー
クを RN-B とした。同様にスケールフリーネットワークにおいてもベッチ数 β1 の大小により SFN-A, SFN-B とした。これらのネットワークは 3 章において用いる。
表 2.1

ベッチ数解析の結果

network

β0

β1

β2

β3

RN-A

2

264

0

0

RN-B

4

295

0

0

SFN-A

1

62

3

0

SFN-B

1

134

3

0

21

ベッチ数解析

200

number

β0
β1

100

RN−A
(β1=264)

0

100
図 2.5

βn

200

RN−B
(β1=295)

300

ランダムネットワークのベッチ数 βn の分布

200
β1
β2
β3

number

第2章

100

SFN−A
(β1=62)

0

図 2.6

50

SFN−B
(β1=134)

βn

100

150

スケールフリーネットワークのベッチ数 βn の分布

第2章

ベッチ数解析

2.5

まとめ

22

生成された複数のネットワークは、頂点数、辺の数が大きく、我々人間の目ではどのよ
うなネットワークであるか判別することは難しい。しかし、ベッチ数で解析することにより、ネットワークの分断数や閉ループの数を求めることが出来た。
また、今回生成したネットワークは各頂点の次数分布、つまり各頂点の接続辺の分布がランダムネットワーク、スケールフリーネットワークのそれぞれのネットワークにおいて、ほぼスケールしていた。このことより、スケールフリーネットワーク、ランダムネッ
トワークそれぞれが同じネットワーク構造を持っているとできる。しかし、同じネット
ワーク構造を持つネットワークであっても、ベッチ数解析により閉ループを表すベッチ数

β1 の分布がみられた。よって、ネットワークの疎密さが異なることがわかった。このことより、同じ構造を持つネットワークであっても、β1 の違いより、攻撃や故障に対する耐性が異なると予想される。さらに、このベッチ数の分布は特にスケールフリーネットワー
クにおいてみられた。スケールフリーネットワークはインターネット網、WWW などの身近なネットワークの最適なモデルとして考えられている。しかし、このネットワークは全ての頂点に対して等確率に発生する故障には強いが、接続している辺の数が多い頂点への意図的な攻撃には大変弱いという問題がある。つまり、このスケールフリーネットワー
クの耐攻撃性、耐故障性を高めることにより、より耐久性の高いインターネット網の構築に期待できる。

第3章

攻撃、故障とベッチ数の関係

23

第3章

攻撃、故障とベッチ数の関係
3.1

はじめに

1 章において述べたようにスケールフリーネットワークは我々の身近なネットワークであるインターネット網、WWW などを表す最適なモデルとして考えられている。このス
ケールフリーネットワークは、ある頂点の接続辺の頻度分布を表したとき、べき乗則に従うというものであった。これは、接続辺を多く持つ頂点というのは少数だが、接続辺をほとんど持たない頂点が大多数を占めるという構造を表している。しかし、そのネットワー
ク構造よりスケールフリーネットワークは全ての頂点に対して等確率に発生する故障に対して強いが、接続している辺の数が多い頂点への意図的な攻撃には大変弱いといった問題がある。このスケールフリーネットワークの耐攻撃性、耐故障性を高めることにより、より頑丈なインターネット網の構築などに期待できる。

2 章でのベッチ数解析の結果より、頂点数、辺の数が同じで、接続辺の頻度分布がスケールするようなネットワーク、つまり同じ構造を持つネットワークであっても、閉ループの数を表すベッチ数 β1 の分布が見られることがわかった。特に、スケールフリーネッ
トワークでベッチ数 β1 の分布がみられた。このことは、同じ構造を持つネットワークであってもネットワークの疎密さが異なることを表している。つまり、ネットワークに対す
る攻撃、故障についての耐久性も異なることが予想される。
そこで、この章ではネットワークのベッチ数と耐攻撃性、耐故障性の関係について検証を行う。検証に用いるネットワークは、2 章のベッチ数解析の結果においてベッチ数 β1の最小値、最大値により定義した RN-A, RN-B, SFN-A, SFN-B の 4 つのネットワーク
を用いた。

第3章

攻撃、故障とベッチ数の関係

3.2

ベッチ数と耐故障性の関係の検証

24

まず、故障という現象についてインターネット網を例に取り解説する。インターネット
網は中継局を頂点とし、中継局同士を光ケーブルなどにより繋げたスケールフリーネット
ワークである。しかし、スケールフリーネットワークの構造的特徴より、多くの中継局と繋がっている中継局というものは少数で、少数の中継局としか繋がっていない中継局というものが大多数を占める。ここで、故障は全ての中継局に対して等確率で起こると考えられる。よって、少数の中継局としか繋がっていないような中継局が故障する確率が高くなる。しかし、このような中継局が故障したとしてもネットワークの重要な役割を担っていないため、ネットワークが一度に分断されてしまうということにはならない。
ここでは、スケールフリーネットワークに対して、等確率で辺が故障するという辺故障行うことで、ベッチ数と耐故障性の関係について検証した。今回、ランダムネットワーク
ではベッチ数と故障回数による関係が表れにくいと予想したため、スケールフリーネット
ワークのみ行った。
最初に 2 章の結果において、ベッチ数が最も小さいスケールフリーネットワーク（SFN-A）とベッチ数が最も大きいスケールフリーネットワーク（SFN-B）、2 つのスケールフ
リーネットワークに対して、等確率で辺が故障するという辺故障を 200 回行い、各故障
回数でののベッチ数の平均を求めた。その結果が図 3.1 である。この結果より、僅かだがベッチ数と閉ループの数を表す β1 の関連性が出ているのがわかる。よって、辺故障を200 回行いネットワークの分断数を表す β0 が 43 以上となったときの平均故障回数を求めた。図 3.2 は横軸に β1 、縦軸に平均故障回数を取り、ベッチ数 β1 と耐故障性の関係を表したものである。

第3章

25

攻撃、故障とベッチ数の関係

200
β0

β1

SFN−A
SFN−B

βn 100

0
図 3.1

250
number of fault

500

スケールフリーネットワークに対して辺故障を 200 回行い、各故障回数に

average number of fault

おけるベッチ数の変化

250

200

150
60
図 3.2

80

100
β1

120

スケールフリーネットワークに対して辺故障を 200 回行い β0 が 43 以上となったときの平均故障回数とベッチ数 β1 の関係

第3章

攻撃、故障とベッチ数の関係

3.3

ベッチ数と耐攻撃性の関係の検証

26

次に、攻撃という現象についてインターネット網を例に考え解説する。インターネット
網は中継局を頂点とし、中継局同士を光ケーブルなどにより繋げたスケールフリーネット
ワークである。しかし、スケールフリーネットワークの構造的特徴より、多くの中継局と繋がっている中継局というものは少数で、少数の中継局としか繋がっていない中継局というものが大多数を占める。ここで、攻撃は多数の中継局と繋がっている重要な中継局を意
図的に破壊することである。このような重要なところをハブというが、これを破壊されることにより、ネットワークが一度に分断されてしまう。その攻撃の様子を頂点数が 18 個の簡単なネットワークの例で示したのが図 3.3 であり、赤で表した頂点が意図的に攻撃対象となった頂点を表している。この頂点が攻撃により消えることで、ネットワークが分断されていっている。このように頂点ごと破壊することを以後、頂点攻撃という。また、頂点攻撃以外に、接続辺を多く持つ頂点の接続辺を意図的に攻撃し破壊する、つまり頂点を残す攻撃のことを辺攻撃ということにする。辺攻撃の様子を図 3.4 に表した。この図 3.4において、攻撃によって残された頂点は青で表している。
このような頂点攻撃、辺攻撃をランダムネットワークとスケールフリーネットワークに対して行い、各攻撃回数に対するベッチ数の変化を調べることにより、ベッチ数と耐攻撃性の関係を検証した。

(a) 初期状態(b) 頂点攻撃 1 回目
図 3.3(a) 初期状態

ネットワークの頂点攻撃の例(b) 頂点攻撃 1 回目
図 3.4(b) 頂点攻撃 2 回目

ネットワークの辺攻撃の例(b) 頂点攻撃 2 回目

第3章

攻撃、故障とベッチ数の関係

3.3.1

ランダムネットワーク

27

β1 が最も小さいランダムネットワーク（RN-A）、 最も大きいランダムネットワーク（RN-B）に対して辺攻撃、頂点攻撃をそれぞれ行い、各攻撃回数のベッチ数の変化を調べた。辺攻撃、頂点攻撃の結果はそれぞれ図 3.5, 3.6 に示している。
辺攻撃の結果において、攻撃回数が 50 回までネットワークの分断数を表す β0 の増加率
は 1 か 2 程度である。辺攻撃であるので頂点が残ることを考慮すると、ネットワークはほとんど分断されていないことがわかる。このことは、頂点攻撃の結果からもわかる。しかし、攻撃回数が 50 回以上となったとき、ネットワークの分断数を表す β0 は急に増加し始める。これは、攻撃によりネットワークの構造が変化したためであると考えられる。そこ
で、図 3.7, 3.8 に RN-A, RN-B に対してそれぞれ頂点攻撃を行ったときのネットワークの変化の様子を示した。頂点攻撃 50 回後の RN-A, RN-B のネットワークの様子からわかるように、スケールフリーネットワークのようなネットワーク構造になっていることがわかる。
さらに、ネットワークの分断数を表す β0 が 30 以上となったときの攻撃回数を調べることで、β1 と耐攻撃性の関係について検証した。その結果が図 3.9 である。ベッチ数 β1 が同じでも、ネットワークの分断数 β0 が 30 以上となったときの攻撃回数が異なるネット
ワークがあったため、平均攻撃回数を求め、エラーバーで最小、最大攻撃回数を表している。しかし、エラーバーが大きくベッチ数 β1 との関係性は低い。

第3章

28

攻撃、故障とベッチ数の関係

300
RN−A

β0

β1

200

RN−A

β0

β1

RN−B

RN−B

βn

βn

200

100

100

0

100
number of attack

0

200

80

(b) 拡大図(a) 全体図
図 3.540number of attack

ランダムネットワークに対する辺攻撃回数によるベッチ数の変化

300
RN−A

β0

200

β1

RN−A

β0

β1

RN−B

RN−B

βn

βn

200

100

100

0

100
number of attack(a) 全体図
図 3.6

200

0

40
number of attack(b) 拡大図

ランダムネットワークに対する頂点攻撃回数によるベッチ数の変化

80

第3章

29

攻撃、故障とベッチ数の関係

Pajek(a) 初期状態

Pajek(b) 頂点攻撃 10 回後

Pajek(d) 頂点攻撃 30 回後

Pajek(c) 頂点攻撃 20 回後

Pajek(e) 頂点攻撃 40 回後

Pajek(f) 頂点攻撃 50 回後Pajek(g) 頂点攻撃 60 回後
図 3.7 RN-A について各頂点攻撃回数のネットワークの様子

第3章

30

攻撃、故障とベッチ数の関係

Pajek(a) 初期状態

Pajek(b) 頂点攻撃 10 回後

Pajek(d) 頂点攻撃 30 回後

Pajek(c) 頂点攻撃 20 回後

Pajek(e) 頂点攻撃 40 回後

Pajek(f) 頂点攻撃 50 回後Pajek(g) 頂点攻撃 60 回後
図 3.8 RN-B について各頂点攻撃回数のネットワークの様子

第3章

31

攻撃、故障とベッチ数の関係

number of attack

70

60

50

図 3.9

270

280
β1

290

ランダムネットワークに対して頂点攻撃を行い β0 が 30 以上になったときの攻撃回数とベッチ数 β1 の関係

第3章

攻撃、故障とベッチ数の関係

3.3.2

スケールフリーネットワーク

32

β1 が最も小さいスケールフリーネットワーク（SFN-A), 最も大きいスケールフリー
ネットワーク（SFN-B）に対して辺攻撃、頂点攻撃をそれぞれ行い、各攻撃回数のベッチ数の変化を調べた。辺攻撃、頂点攻撃の結果はそれぞれ図 3.10, 3.11 に示している。また、図 3.12, 3.13 は各攻撃回数によるネットワークの変化の様子を示した。
頂点攻撃において、ネットワークの分断数を表す β0 が 25 となるときの攻撃回数は、ランダムネットワークが 50 回程度かかるが、スケールフリーネットワークでは 4 から 8 回の攻撃で β0 が 25 となってしまう。このことより、一般的に言われていたように、スケー
ルフリーネットワークは攻撃に大変弱いことがわかる。しかし、スケールフリーネット
ワークにおいて閉ループの数を表す β1 の違いにより、ネットワークの分断数を表す β0の増加率が 1 回目の攻撃から異なることがわかる。よって、ネットワークの分断数を表す

β0 が 70 以上となったときの攻撃回数を調べることで、β1 と耐攻撃性の関係について検証した。その結果が図 3.14 である。ベッチ数 β1 が同じでも、ネットワークの分断数 β0が 70 以上となったときの攻撃回数が異なるネットワークがあったため、平均攻撃回数を求め、エラーバーで最小、最大攻撃回数を表している。このように、閉ループの数を表す

β1 と耐攻撃性の関係がみられることがわかる。よって、位相不変量の 1 つであるベッチ数を用いることによって、耐攻撃性に優れるスケールフリーネットワークの生成に期待で
きる。

第3章

33

攻撃、故障とベッチ数の関係

300
SFN−A

β0

200

β1

SFN−A

β0

β1

SFN−B

SFN−B

βn

βn

200

100

100

0

100
number of attack

0200(a) 全体図
図 3.10

10
20
number of attack30(b) 拡大図

スケールフリーネットワークに対する辺攻撃回数によるベッチ数の変化

300
SFN−A

β0

200

β1

SFN−A

β0

β1

SFN−B

SFN−B

βn

βn

200

100

100

0

100
number of attack(a) 全体図

200

0

10
20
number of attack(b) 拡大図

図 3.11 スケールフリーネットワークに対する頂点攻撃回数によるベッチ数の変化

30

第3章

34

攻撃、故障とベッチ数の関係

Pajek(a) 初期状態

Pajek(b) 頂点攻撃 5 回後

Pajek(d) 頂点攻撃 15 回後

Pajek(c) 頂点攻撃 10 回後

Pajek(e) 頂点攻撃 20 回後

Pajek(f) 頂点攻撃 25 回後Pajek(g) 頂点攻撃 30 回後
図 3.12 SFN-A について各頂点攻撃回数のネットワークの様子

第3章

35

攻撃、故障とベッチ数の関係

Pajek(a) 初期状態

Pajek(b) 頂点攻撃 5 回後

Pajek(d) 頂点攻撃 15 回後

Pajek(c) 頂点攻撃 10 回後

Pajek(e) 頂点攻撃 20 回後

Pajek(f) 頂点攻撃 25 回後Pajek(g) 頂点攻撃 30 回後
図 3.13 SFN-B について各頂点攻撃回数のネットワークの様子

第3章

36

攻撃、故障とベッチ数の関係

number of attack

30

20

60

図 3.14

80

100
β1

120

スケールフリーネットワークに対して頂点攻撃を行い β0 が 70 以上となったときの攻撃回数とベッチ数 β1 の関係

第3章

攻撃、故障とベッチ数の関係

3.4

まとめ

37

2 章の結果より、頂点数、辺の数が同じで、接続辺の頻度分布がスケールするようなネットワーク、つまり同じ構造を持つネットワークであっても、ネットワークの疎密さは異なることがベッチ数解析によりわかった。そこで、ネットワークの耐攻撃性、耐故障性がベッチ数と関係するかどうかを検証した。ランダムネットワークの耐攻撃性について
は、攻撃回数が 50 回くらいまでベッチ数 β1 との関係はなかったが、攻撃回数が 50 回を超えると、ベッチ数 β1 の違いよりネットワークの分断数 β0 の増加率が異なった。これは、攻撃によりネットワーク構造がランダムネットワークからスケールフリーネットワー
クのようなネットワークへと変化していったためと考えられる。しかし、ランダムネット
ワークにおいてはベッチ数と耐攻撃性の関係は弱かった。スケールフリーネットワークの耐攻撃性については、ネットワークの分断数を表す β0 が 70 以上となるときの攻撃回数を調べることにより検証した結果、独立な閉ループを表す β1 が大きいほど、耐攻撃性が大きいことがわかった。このことより、位相不変量の 1 つであるベッチ数を用いることによって、耐攻撃性に優れたスケールフリーネットワークの生成に期待できる。

第4章

結論

38

第4章

結論
本研究では、位置と形相に依存しない量である位相不変量のうちの 1 つであるベッチ数によりネットワークを解析し、ネットワークを特徴付けることを目的とした。このベッ
チ数は、従来のネットワークを特徴付けていた直径、クラスター係数、平均経路長、接続
辺の頻度分布などの値より、さらに詳細な情報である独立なネットワークの数、独立な閉ループの数、さらには高次元まで解析することができる。そこで、200 頂点、500 辺のランダムネットワーク、スケールフリーネットワークをそれぞれ生成し、これらをベッチ数を用いて解析した。ここで、ランダムネットワークとは、全ての頂点の接続辺がほぼ一定であるネットワークのことで、各頂点の接続頻度はポアソン分布に従う。また、スケール
フリーネットワークとは、1999 年にBarabási らが発見したもので、このネットワークの接続辺の頻度分布はべき乗側に従うというものである。これら 2 つのネットワークを解析した結果、ランダムネットワーク、スケールフリーネットワーク、それぞれ頂点数、辺の数が同じで、接続辺の頻度分布もほぼスケールするようなネットワーク、つまり同じ構造を持つはずのネットワークだが、独立な閉ループの数を表す β1 の分布がみられた。
このことは、ネットワークの疎密さが異なることを表し、ネットワークの耐久性と関係があると考えた。そこで、全ての頂点（辺）に対して等確率で故障してしまうという故障と接続辺の数が多い頂点、つまりネットワークの重要な役割を担っている頂点（ハブ）を意
図的に攻撃するシミュレーションを行い、それぞれのネットワークにおいての耐故障性、耐攻撃性を調べた。その結果、ベッチ数解析において β1 の分布が大きかったスケールフ
リーネットワークは、独立な閉曲面を表す β1 が大きいと攻撃に対する耐久性が高いとい

第4章

結論

39

う関係がみられた。このことより、意図的な攻撃には弱いというスケールフリーネット
ワークの問題を改善することが期待できる。

付録 A Pajek

40

付録 A

Pajek
A.1

データ形式

Pajek のネットワークデータ (*.net) はテキスト形式であり、次のような書式で書かれている。

*Vertices <N>
1 "<label>"
2 "<label>"
3 "<label>"..
.
N "<label>"*Edges<node> <node> <weight> "<label>"

付録 B

プログラムソース

41

付録 B

プログラムソース
B.1

ER-Model■ er-model.cc#include <iostream.h>#include <stdlib.h>#include <time.h>void er model(int N,double p);
int main(int argc, char ∗argv [ ]){int N =atoi(argv [1]);double p=atof (argv [2]);srand(time(NULL));

10

cout << "*Vertices " << N << endl;
cout << "*Edges" << endl;
er model(N,p);return 0;}
20

void er model(int N,double p){for(int i=0;i<N ;i++)for(int j =i+1;j <N ;j ++){
if (p > (double)rand()/RAND MAX ){cout << i+1 << " " << j +1 << " 1" << endl;
}
}
}

付録 B

プログラムソース

B.2

ランダムネットワーク生成プログラム

42■ generate-rn.c#include <stdio.h>#include <stdlib.h>#include <time.h>
int main(void){
int i,j,n;double weight;
char buf [256],filename[18];FILE ∗fp;
10

printf ("Input Vertex Size: ");scanf ("%d",&n);srand(time(0));
sprintf (filename,"%d",n);fp = fopen(filename,"w");fprintf (fp,"*Vertices %d\n",n);fprintf (fp,"*Edges\n");for(i=0;i<n;i++)for(j =i+1;j <n;j ++){
weight = (double)rand()/RAND MAX ;fprintf (fp,"%d %d %f\n",i+1,j +1,weight);}
fclose(fp);return 0;

20

}

B.3

BA-Model■ ba-model.cc#include <iostream>#include <stdlib.h>#include <time.h>void ba model(int N, int m0, int m);
int sum(int ∗data,int n);
int main(int argc, char ∗argv [ ]){int N =atoi(argv [1]);int m0 =atoi(argv [2]);int m=atoi(argv [3]);cout << "*Vertices " << N << endl;
cout << "*Edges" << endl;
ba model(N,m0,m);
return 0;

10

付録 B

プログラムソース

43}
20

void ba model(int N, int m0, int m){
int output degree[N ]; // あるノードの次数
int edge number ;// 辺の数
double p;// 乱数の初期化
srand(time(NULL));// 次数用配列の初期化
for(int i=0;i<N ;i++)output degree[i] = 0;
for(int i=m0 ;i<N ;i++){edge number =0;
for(int j =0;j <i;j ++){
p = (double)(output degree[j ]+1)/(double)sum(output degree,i);if (p > (double)rand()/RAND MAX ){output degree[i]++;output degree[j ]++;
edge number ++;cout << i+1 << " " << j +1 << " 1" << endl;}
if ( m < edge number )break;}}}
int sum(int ∗data, int n){
int sum=0;
for(int i=0;i<n;i++){sum = sum + data[i] + 1;}
return sum;}

B.4

ベッチ数を求めるプログラム

B.4.1

ネットワークデータ入力部

30

40

50

■ networkio.h#include "matrix.h"#include <stdio.h>using namespace std;
int scan size(char filename[ ]);vector < vector < unsigned int> > edge init(char filename[ ],int size);
vector < vector < unsigned int> >def output link (vector < vector < unsigned int> > edge set, int size);
vector < vector < unsigned int> > def output link (char filename[ ],int size);

10

付録 B

プログラムソース44■ networkio.cc#include <iostream>#include "networkio.h"
int scan size(char filename[ ]){int N ;
char s[256];
FILE ∗fp;// ファイルから読み込む
if ((fp = fopen(filename, "r")) == NULL) {cout << "file open error!!" << endl;
exit(1); /∗ エラーの場合は，異常終了する ∗/}10// 点の個数を読み取る
fgets(s,256,fp);
fclose(fp);sscanf (s,"%*s %d",&N );20

return N ;}vector < vector < unsigned int> > edge init(char filename[ ],int size){
int x,y;int edge number =0;
char s[256];
vector < vector < unsigned int> > edge set;
FILE ∗fp;30// ファイルから読み込む
if ((fp = fopen(filename, "r")) == NULL) {cout << "file open error!!" << endl;
exit(1);}edge set.resize(0);while (fgets(s, 256, fp) != NULL) {if (s[0] == '*' | | s[0] == '#') continue;/∗ ここでは fgets() により１行単位で読み出し ∗/edge number ++;sscanf (s,"%d %d",&x,&y);edge set.resize(edge number );edge set[edge number −1].push back (x −1);edge set[edge number −1].push back (y−1);}
fclose(fp);return edge set;

40}
vector < vector < unsigned int> >def output link (vector < vector < unsigned int> > edge set, int size){
int x,y;// 隣接行列vector < vector <bool> > adjacency matrix ;vector < vector < unsigned int> > output link ;// 隣接行列 初期化

50

付録 B

プログラムソース

adjacency matrix.resize(size);for( int i = 0; i < size; i++){adjacency matrix [i].resize(size);fill(adjacency matrix [i].begin(),adjacency matrix [i].end(),0);}for( int i = 0; i < edge set.size() ; i++){x = edge set[i][0];y = edge set[i][1];adjacency matrix [y][x ] = 1;
adjacency matrix [x ][y] = 1;}// output link 初期化
output link.resize(size);for(int i = 0; i < size; i++)output link [i].resize(0);// output link を作成
for(int i = 0; i < size; i++){for(int j = 0; j < size; j ++)if (adjacency matrix [i][j ] == 1)
output link [i].push back (j );}return output link ;

45

60

70

80

}
vector < vector < unsigned int> > def output link (char filename[ ],int size){
int x,y;char s[256];
FILE ∗fp;// ファイルから読み込む
if ((fp = fopen(filename, "r")) == NULL) {cout << "file open error!!" << endl;
exit(1);}// 隣接行列vector < vector <bool> > adjacency matrix ;vector < vector < unsigned int> > output link ;// 隣接行列 初期化
adjacency matrix.resize(size);for( int i = 0; i < size; i++){adjacency matrix [i].resize(size);fill(adjacency matrix [i].begin(),adjacency matrix [i].end(),0);}
while (fgets(s, 256, fp) != NULL) {if (s[0] == '*' | | s[0] == '#') continue;/∗ ここでは fgets() により１行単位で読み出し ∗/sscanf (s,"%d %d",&y,&x );adjacency matrix [y−1][x −1] = 1;
adjacency matrix [x −1][y−1] = 1;}
fclose(fp);

90

100

110

// output link 初期化
output link.resize(size);for(int i = 0; i < size; i++)output link [i].resize(0);// output link を作成

付録 B

プログラムソース

for(int i = 0; i < size; i++){for(int j = 0; j < size; j ++)if (adjacency matrix [i][j ] == 1)
output link [i].push back (j );}return output link ;

46

120

}

B.4.2

クリークを求めるプログラム■ clique.h#include "matrix.h"#include <stack >#define CLIQUE MAX DIMENSION 7
using namespace std;
void init c set(int N );vector < vector < unsigned int> >def a set(vector < vector < unsigned int> > output link,int size);
void all cliques(vector < vector < unsigned int> > output link, int N );vector < unsigned int >intersection(vector < unsigned int > a set, vector < unsigned int > b set);
void cliques(int l, vector < vector < unsigned int> > a set);10■ clique.cc#include <iostream>#include "clique.h"
vector <unsigned int> temp set;
vector < vector <unsigned int> > c set;
vector < vector <vector <unsigned int> > > clique;void all cliques(vector < vector < unsigned int> > output link, int N ){vector < vector < unsigned int> > a set;10// 初期化
c set.resize(CLIQUE MAX DIMENSION );clique.resize(CLIQUE MAX DIMENSION );for(int i = 0; i < clique.size(); i++){clique[i].clear ();for(int j = 0; j < clique[i].size(); j ++){
clique[i].clear ();clique[i][j ].resize(0);}}init c set(N );a set = def a set(output link,N );for(int i=0; i<N ; i++){temp set.clear ();temp set.push back (i);cliques(1, a set);

20

付録 B

プログラムソース

47

}
}

30

void init c set(int N ){// C 0 を定義
for(int i = 0; i < c set.size(); i++){c set.clear ();c set.resize(N );for(int j = 0; j < c set[i].size();j ++){
c set[i].clear ();}}for( int i = N −1; i >= 0; i−−){c set[0].push back (i);}}void cliques(int l, vector < vector < unsigned int> > a set){static vector < unsigned int >::reverse iterator p1 ;if (l < CLIQUE MAX DIMENSION ){// 領域確保
clique[l−1].resize(clique[l−1].size()+1);// クリーク定義
for(int j = 0; j < temp set.size(); j ++)clique[l−1][clique[l−1].size()−1].push back (temp set[j ]);40

50

p1 = temp set.rbegin();// intersection
c set[l].clear ();c set[l] = intersection(a set[∗p1 ],c set[l−1]);
if (!c set[l].empty()){// temp set に要素を追加し、次の次元に移る
for(int i = 0; i < c set[l].size(); i++){temp set.push back (c set[l][i]);cliques(l+1,a set);
}
}

60

}
temp set.pop back ();}70

vector < unsigned int >intersection(vector < unsigned int > a set, vector < unsigned int > b set){
vector < unsigned int > d set;for(int i = 0; i < a set.size(); i++)for(int j = 0; j < b set.size(); j ++)if (a set[i] == b set[j ])d set.push back (a set[i]);return d set;}
80

vector < vector < unsigned int> >def a set(vector < vector < unsigned int> > output link,int size){
vector < vector < unsigned int> > a set;// 隣接行列 a set 初期化
a set.resize(size);for(int i = 0; i < size; i++){

付録 B

プログラムソース48

a set[i].clear ();a set[i].resize(0);}// a set を作成
for(int i=0; i < output link.size() ; i++){for(int j =0; j < output link [i].size() ; j ++)if (output link [i][j ] > i)a set[i].push back (output link [i][j ]);}return a set;

90

}

B.4.3

直径を求めるプログラム■ diameter.h#include "matrix.h"
using namespace std;
int diameter (char filename[ ]);int diameter (char filename[ ],int N );int diameter (vector < vector < unsigned int> > output link, int N );vector < vector < unsigned int> > def output link (char filename[ ], int size);intbfs(unsigned int u, unsigned int v, int N, vector < vector < unsigned int> > output link ); 10■ diameter.cc#include <iostream>#include <queue>#include "diameter.h"#include "networkio.h"
int diameter (char filename[ ]) {int diameter =0;
int length = 0;vector < vector < unsigned int> > output link ;10

int N = scan size(filename);
output link = def output link (filename,N );for (int u = 0; u < N ; u++) {for (int v = u+1; v < N ; v ++) {length = bfs(u,v,N,output link );if (diameter < length)
diameter = length;}}
return diameter ;20}
int diameter (char filename[ ],int N ) {int diameter =0;
int length = 0;vector < vector < unsigned int> > output link ;output link = def output link (filename,N );for (int u = 0; u < N ; u++) {for (int v = u+1; v < N ; v ++) {length = bfs(u,v,N,output link );if (diameter < length)
diameter = length;

30

付録 B

プログラムソース

49}}
return diameter ;}int diameter (vector < vector < unsigned int> > output link, int N ) {int diameter =0;
int length = 0;
for (int u = 0; u < N ; u++) {for (int v = u+1; v < N ; v ++) {length = bfs(u,v,N,output link );if (diameter < length)
diameter = length;}}
return diameter ;

40

50

}
int
bfs(unsigned int u, unsigned int v, int N, vector < vector < unsigned int> > output link ){int diameter =0;
unsigned int x ;queue< unsigned int > queue;
vector < int > l;// u:Start , v:Goal , l:Length// Step1.
60// 距離の初期化
l.resize(N );fill(l.begin(),l.end(),−1);l[u] = 0;
queue.push(u);// queue が空ならルートはない
while (!queue.empty()){// queue から 頂点 x を取り出す
x = queue.front();
queue.pop();// 頂点 x に接続している頂点数繰り返す
for (int i=0; i<output link [x ].size(); i++) {// 頂点 x に接続している頂点の距離の判定
if (l[output link [x ][i]] == −1){// 頂点 x に接続している頂点の距離を定義
l[output link [x ][i]] = l[x ]+1;// queue に頂点 x の出力リンクを追加
queue.push(output link [x ][i]);}}// ルートが見つかったかどうか判別
if (l[v ] != −1) {return l[v ];}}return 0;
}

70

80

付録 B

B.4.4

プログラムソース

50

クリークから境界作用素行列を定義しベッチ数を求めるプログラム■ betti.h#include "matrix.h"#ifdef DIMENSION#else#define DIMENSION 6#endifusing namespace std;
void def betti(vector < vector <vector <unsigned int> > > clique);
vector < vector <short> >def boundary matrix (int l, vector < vector <vector <unsigned int> > > clique);int rank (vector < vector <short> > matrix );10■ betti.cc#include <iostream>#include <math.h>#include "betti.h"
int betti[DIMENSION ];void def betti(vector < vector <vector <unsigned int> > > clique){
vector < vector <short> > boundary matrix ;int dim boundary[DIMENSION ]={0};10for( int l = 1; l < DIMENSION ; l++){boundary matrix = def boundary matrix (l,clique);dim boundary[l] = rank (boundary matrix );}for(int l=0;l<DIMENSION −1;l++){betti[l] = clique[l].size() − dim boundary[l] − dim boundary[l+1];}}
vector < vector <short> >def boundary matrix (int l, vector < vector <vector <unsigned int> > > clique){
vector < vector <short> > boundary matrix ;// 境界作用素行列の初期化
boundary matrix.resize(clique[l−1].size());
for(int i = 0; i < clique[l−1].size(); i++){boundary matrix [i].resize(clique[l].size());
fill(boundary matrix [i].begin(),boundary matrix [i].end(),0);}// 境界作用素行列の定義
for(int j = 0; j < clique[l−1].size(); j ++)for( int k = 0; k < clique[l].size(); k ++){
int counter [clique[l].size()];int sum = 0;
int indicator = 0;
for( int m = 0; m < clique[l][k ].size(); m++)

20

30

付録 B

プログラムソース

counter [m]=0;
for( int m = 0; m < clique[l−1][j ].size(); m++)for( int n=0; n < clique[l][k ].size(); n++){if (clique[l−1][j ][m] == clique[l][k ][n])counter [n]++;}for( int m = 0; m < clique[l][k ].size(); m++){sum += counter [m];if (counter [m] == 0)
indicator = m;}if ( sum != l)boundary matrix [j ][k ] = 0;else{
if (indicator % 2 == 0)boundary matrix [j ][k ] = 1;
elseboundary matrix [j ][k ] = −1;
}

51

40

50

}
return boundary matrix ;}int rank (vector < vector <short> > matrix ){// ランクを求める// ピボット数をもつ行を見つけ出す
short temp;
int m;
for(m=0;m<min(matrix.size(),matrix [0].size());m++){// pivot が 1 でないならば
if (matrix [m][m] != 1){// pivot が 0 ならば pivot を探し行列を交換し pivot を 0 以外にする// 列 (左右) 方向にループ
for(int j =m;j <matrix [0].size();j ++){
if (matrix [m][m] != 0) break; // pivot が決まったらループを抜ける// 行 (上下) 方向にループ
for(int k =m;k <matrix.size();k ++){
if (matrix [k ][j ] != 0){ // [k][j] の所で 0 でない要素発見// 列を置換する
if (m != j ){for(int n=m;n<matrix.size();n++){temp = matrix [n][m];matrix [n][m] = matrix [n][j ];matrix [n][j ] = temp;}}// 行を置換する//printf printf(“行 %d と %d を置換する \n”,m,k);for(int n=m;n<matrix [0].size();n++){temp = matrix [m][n];matrix [m][n] = matrix [k ][n];matrix [k ][n] = temp;}
break; // pivot が見つかったら行方向のループを抜ける}}}
if (matrix [m][m] == 0)

60

70

80

90

付録 B

プログラムソース

52

break;// pivot を 1 にする
temp = matrix [m][m];for(int n=m;n<matrix [0].size();n++)matrix [m][n] /= temp;}// 探しても見つからなかったら、ループを抜ける
if (matrix [m][m] == 0)
break;
if (isnan(matrix [m][m]))break;// pivot が定まった// m 列 の pivot 以外の要素を 0 にする
for(int k =m+1;k <matrix.size();k ++){
if (matrix [k ][m] == 0){
continue;}
while(matrix [k ][m] < 0){for(int j =0;j <matrix [0].size();j ++)matrix [k ][j ] += matrix [m][j ];}while(matrix [k ][m] > 0){for(int j =0;j <matrix [0].size();j ++)matrix [k ][j ] −= matrix [m][j ];}}}return m;
}

100

110

120

付録 B

謝辞

53

謝辞
本研究を行うにあたり、多大な御指導、御助言を頂いた小田部荘司助教授、有明高専電子情報工学科松野哲也助教授に深く感謝します。また、結果について助言をくださった
松下照男教授、木内勝助手に深く感謝します。
最後に色々と支援を頂いた小田部研究室、及び松下研究室の皆さんに深く感謝します。

54

参考文献

参考文献
[1] R. Albert and A. Barabási Statistical Mechanics of Complex Networks, (2002).
[2] M. E. J. Newman, Random Graphs as Models of Networks, ch. 2, pp. 35.68.
Berlin: WILEY-VCH, 1 ed., Nov. 2002.
[3] A. L. Barabási and R. Albert,

Emergence of scaling in random networks,

SCIENCE, vol. 286, pp. 509.512, Oct. 1999.
[4] G. Vegter: Computational Topology, CRC Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O’Rourke (eds.). CRC Press, LLC, Boca
Raton, Florida, chapter 28, pag. 517-536, 1997.
[5] http://www.eng.tau.ac.il/˜yash/[6] http://vlado.fmf.uni-lj.si/pub/networks/pajek/