最終更新日　2007/03/28

スモールワールド理論に基づく

リアルタイムP2Pネットワーク

東京電機大学　工学部第一部　情報通信工学科

ネットワークシステム研究室

指導教員　：　坂本直志　助教授

学籍番号：03KC056

鈴木　暁

1 はじめに
1.1 背景
1.2 この研究の動機
1.3 論文の構成の説明

2 前知識
2.1 グラフとは
2.2 隣接行列表現
2.3 代表的なトポロジの特徴
2.4 最短経路問題
2.5 ソケット

3 過去の研究
3.1 スモールワールド現象
3.2 エルデシュ・レーニィ　ランダムグラフ
3.3 (WS）スモールワールドネットワーク
3.4 スケールフリーネットワーク

4 本研究
4.1 本研究の目的
4.2 本研究の方向性

5 シミュレーション実験
5.1 目的
5.2 原理
5.3 計画
5.4 測定方法

5.5 実験1　頂点数1000におけるトポロジ別の性質
5.5.1 目的
5.5.2 手順
5.5.3 結果
5.5.4 考察

5.6 実験2　リングネットワーク＋ランダムリンク(ｘ2)
5.6.1目的
5.6.2 手順
5.6.3 結果
5.6.4 考察

5.7 実験3　1000および10000頂点まで増加
5.7.1 目的
5.7.2 手順
5.7.3 結果
5.7.4 考察
5.8 まとめ

6 P2P通信実験
6.1 目的
6.2 原理
6.3 測定方法
6.4 手順
6.5 結果
6.6 考察

7 まとめ

8 付録
8.1 謝辞
8.2 参考文献

1 はじめに

1.1 背景

ブロードバンド化によりインターネットの通信速度は向上し、また PC も時代と共に性能が向上していった。そして PC は情報を受信するだけでなく、自ら情報を送信するようになってきた。 今後 PC はサーバを介さずに直接 PC 同士対等な立場で相互にやりとりを行うことが増えるであろう。

ネットワークシステムには主に 2 つの形態がある。

・クライアント・サーバ
・ Peer to Peer(P2P)

このうちクライアント・サーバのネットワークはサーバを中心とし、周りにクライアント が つながっているスター型のトポロジを形成する。このシステムにおいてはサーバとクライアントの役割は別々である。 Web を例にするとクライアントは web ブラウザによってサーバにデータを要求 し、 サーバはクライアントからの要求に対してデータの配信を行 う のである。このように役割は固定されている。

サーバはシステムの中心に存在し、サーバによってデータは一元管理される。そのことよりクライアント情報の管理 が単純になり 、クライアント同士をつなげる調停役を担うことが多い。しかしその反面、サーバはクライアントからの要求を一点に請け負うため負担が大きい。

一方 P2P ネットワークは定まったサーバおよびクライアントを持たず、 PC がその状況に応じて両方の役割を使い分ける。そのためトポロジがスター型にならず、動的で柔軟なネットワークが構築可能である。リアルタイムに通信を行う場合は他の 端末 を中継せずにノード同士が直接接続しあう完全グラフを形成することが多い。

通信処理 はサーバのように一点に集中することはない。しかしネットワークを代表的に管理するものがいない 。その ためネットワーク全体の情報を知ることが困難であり、ノード間の管理が難しい。

1.2 この研究の動機

本研究では サーバを介さず リアルタイム に多数の PC で通信 する アプリケーションを作成したい と考える 。 リアルタイム通信とは遅延に関して何秒以内にメッセージが届くかを保障する通信である。つまりリアルタイム通信では、ある遅延時間の許容範囲内で通信を行わなければならない。

遅延を少なくするためには送信ノードから目的ノードまで直接接続してメッセージを届ければよい。 しかし そのような方法では台数の増加とともに接続数も比例して多くなる。またそのことで問題となることがある。 日頃使用している PC の OS 「 Windows 」には最大接続数 に制約が ありその範囲内でしかつなげることができない。

使用許諾書より抜粋　（Windows XP Home Edition）

　接続数に制限があるためある台数以上になると送信ノードから目的ノードへ直接メッセージを送ることができなくなる。そのため中継ノードを介した転送という行為が必須になる。しかし転送回数が多くなれば遅延が生じ、リアルタイム性が損なわれてしまう。
　そこで制限された接続数のなかで も 多数の PC と リアルタイムに 通信 する方法を 考え る 。 この理想のネットワークの要点をまとめると第一に接続数が少ないこと、第二に遅延が少ない、つまり転送回数が少ないことである。
　 このような理想のネットワークはないかと調べた。その結果グラフ理論においてスモールワールドの理論が有効であると考えた。知り合い関係を芋づる式にたどっていけば比較的簡単に世界中の誰にでも行き着くというものである。実験でアメリカ合衆国国民から二人ずつの組を無造作に抽出し、平均すると６の知り合いを解してその二人が繋がった。つまり少数のランダムなリンクを張ることでネットワーク全体の直径（任意の二つの頂点を結ぶ最短経路のうちで長さが最大のものを求め、その長さを直径という）が極めて小さくなるのである。
　 　このような性質をスモールワールド性と呼ぶ。
このようなスモールワールド理論に着想を得てネットワークを作成する。まずスモールワールド性の有効性を確認するために実験を行い、その後に実際にアプリケーションを作成し評価した。

1.3 論文の構成の説明

　はじめに事前に知っておくべき知識 としてグラフやネットワーク構成の性質などを 2 章 にて述べる。次に 3 章にて グラフの構造に関する研究を 紹介する。 ４章にてこの研究の目的や方向性を述べる。 5 章にてスモールワールドの性質を計測するためにシミュレーション実験の結果を、 6 章 に て 実際に P2P 通信を行った実験の結果を述べる 。 最後に７章にまとめを載せる。

2 前知識

2.1 グラフとは

図 1　グラフ基礎

点の集合を V 、辺の集合を E ⊆ V × V とするとグラフを G=(V, E) で表わす。本研究で使用するグラフは無効有限単純連結グラフである。

頂点ｘに対し、次数とは頂点から出入りする辺の数である。

deg(x)=#{y|(x, y) ∈ E }

また、経路 P= とは互いに接続された頂点の列であり、各 i に対して、 { } ∈ E を満たす。

頂点 x, y の距離は x と y の経路のうち、一番短い経路の長さ（ P={ } ∈ E ならば 1 ）を表す。

G の直径とはつまり [ [x と y の距離 ]]

2.2 隣接行列表現

下の図は下の図は頂点数７におけるグラフの一例である。
G=(V, E), V={A, B, C, D, E, F}, E={ {A, B}, {A, E}, {B, C}, {B, E}, {C, D}, {D, E}, {D, F} } 　で表わされる。
頂点数７におけるグラフの一例である。また本研究では有限無向単純連結グラフを取り扱う。

図 2　6つの頂点と7つの辺のグラフ

このようなグラフをコンピュータ上で表現するため隣接行列を用いる。頂点数を |V| としたときに、隣接行列 a とは |V| 行 |V| 列の 2 次元配列で表現する方法である。頂点 x から頂点ｙに辺があるとき 、 a[x][y] と a[y][x] を１、そうでないときを０と表現する。対角成分 a[x][x] （ 1 ≦ x ≦ |V| ）は 0 とする。

表 1　隣接行列表現

2.3 代表的なトポロジの特徴

ネットワークトポロジとはネットワークの 接続をグラフ理論的観点から見たときのグラフの構造を言う。なお、実ネットワークにおいて、実際のコンピュータの配線を示す 物理トポロジと いい 、 各今 p- 他が信号を送りあう関係に着目したのを 論理トポロジ という 。本研究は 実 ネットワーク上で動的に形成する論理トポロジを扱う。 以下に代表的なネットワークトポロジを紹介する。

・ 完全グラフ（フルメッシュ）
複数の頂点間をそれぞれ個別に接続し、網目状の形態をとる。

N 頂点存在すると、それぞれ他の N-1 頂点と接続するので辺の数は無効グラフで N(N-1) / 2 となる。全ての頂点が他の頂点と直接つながっている。

図 3　完全グラフ

・スター
ネットワークの中心部はハブ (Hub) と呼ばれる。クライアント・サーバによるシステムではサーバがハブとして役割を果たす。 スター型の論理トポロジとなる。 ハブが故障した場合、全ての通信が途絶する。 ハブは全てのほかの頂点と接続しているので次数、辺数とも N-1 となる。

図 4　スタートポロジ

・リング
辺 を環状につなげる。 全ての頂点の次数は 2 であり、辺数は N となる。一方からきた情報を他方に流すと全ての頂点に情報を送ることができる。

図 5　リングトポロジ

・木
最小の連結グラフは木と呼ばれる。そのため、 1 本の辺を取り除くと連結性が失われる。 1 つの頂点に対してへんにより頂点を接続すると生成されるので辺数は N-1 となる。また根となる頂点を 1 つ定めて、 2 つずつ頂点を接続するといった木を 2 分木という。このようにすると根から各頂点の距離は logN 以下になる。

図 6　木

表 3　トポロジ別の性質

2.4 最短経路問題

本研究ではグラフの直径の値が重要となるがこの値を求める方法を紹介する。それがウォーシャルフロイド法である。

・全対最短経路（all-pairs shortest-path problem）

ウォーシャル・フロイド法
頂点xから頂点jへの、番号がy+1未満の頂点からなる最短経路として、番号がy未満の頂点からなるxからjへの最短経路と、xからyへの最短経路にyからjへの辺を加えたものとの、短いほうをとる。

アルゴリズム

for (y = 1; y <= N; y++){
  for(x = 1; x <= N; x++){
    if (a[x][y]){
      for(j = 1; j <= N; j++){
        if (a[y][j]>0){
          if (!a[x][j] || (a[x][y]+a[y][j] < a[x][j])){
            a[x][j] = a[x][y] + a[y][j];
          }
        }
      }
    }
  }
}

ステップ数：

表 2　各頂点からの距離

2.5 ソケット

インターネットにおけるトランスポートレイヤの API を接続する仮想デバイスをソケットという。通信相手に対応するソケットを生成すると、 read, write などのディレクティヴを使用し、データの送受信を行うことができる。ただし、 UDP と TC ではディレクティブの用法が異なる。

3 過去の研究

3.1 スモールワールド現象

ハーバード大学の心理学者のスタンレー・ミルグラムが 1967 年に実施した実験によって 実証 された。ミルグラムはネブラスカ州オマハの住人 160 人を無作為に選び、「同封した写真の人物はボストン在住の株式仲買人です。この顔と名前の人物をご存知でしたらその人の元へこの手紙をお送り下さい。この人を知らない場合は貴方の住所氏名を書き加えた上で、貴方の友人の中で知っていそうな人にこの手紙を送って下さい」という文面の手紙をそれぞれに送った。その結果 42 通（ 26.25% ）が実際に届き、届くまでに経た人数は平均 5.83 人であった。

この現象をモデル化すると 1 人の人間の知り合いの数は平均的に分布していると思われ る。また、 知り合いは地域性を無視すれば一様であると考えられる。つまりグラフで考えると、次数が一定で接続先をランダムに決めると、グラフが連結 になる だけでなく小さい直径を持つ性質がある ことを示している 。このような性質をスモールワールド性と呼ぶ。

3.2 エルデシュ・レーニィ　ランダムグラフ

　50 の孤立した町を相互に結ぶ道路を作ろうとした場合、一つずつ結ぼうとすれば 1225 本必要になる。どの二つの町であろうと、道から外れることなく確実に車でいけるようにするには、最低で何本の道路を作ればよいか。これはグラフ理論でよく知られた問題の一つである。 つまり頂点集合に対しグラフを連結にするには何本の辺をランダムに加えればよいかである。 エルデシュが解いたのは 1959 年で、 8 ％の 98 本をランダムに配置すれば十分であることが分かった。
　 彼はどんなに多数の点があろうと、全体が事実上完全に繋がっているネットワークにするには、どんな場合も相対的に少数のリンクをランダムにはれば十分であることを発見した。またネットワークが大きくなるにつれて、必要とされるリンクの比率は次第に小さくなることも分かった。 300 の点を結ぶリンクは 5 万だがそのうち 2 ％弱のリンクで完全に繋がり、 1000 の点では 1 ％に満たない値になる。
　ランダムグラフの作り方は簡単である。まず n 個の頂点を用意する。各 2 点間について確率 p でリンクを張り確率 1 - p でリンクを張らないことにする。 ｐ =1/N とすることでグラフはつながり直径も小さくなる。また p が小さすぎるとネットワークは分断されてしまう。

図 7　ランダムグラフ

3.3 (WS）スモールワールドネットワーク

1998 年にダンカン・ワッツとスティーヴン・ストロガッツが「スモールワールドモデル」（ WS モデル）を発表した。 1 次元格子から単純なアルゴリズムでスモールワールド性を持つモデルを生成した。

スモールワールドモデルでは次のようなアルゴリズムでグラフを生成する。

パラメータ p を0とおけば格子、1とおけばランダムグラフとなる。p を0.1前後とすると、格子とランダムグラフをあわせもったような性質のグラフが生成される。スモールワールドモデルでは、ショートカットが形成される効果によって平均最短距離が飛躍的に短くなる。

図 8　スモールワールドモデル（WS）

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

1999年アルバート＝ラズロ・バラバシとレカ・アルバートはスケールフリー性を持つグラフの数学モデルを考案した。

次のようなアルゴリズムでグラフを生成する。

既存の次数の大きなノードに対して新しいエッジが高い確率で加わってゆき、そのノードがハブへと成長してゆく。モデルはランダムグラフと似たところもあるので、平均最短距離は小さくなる。

図 9　スケールフリーモデル

4 本研究

4.1 本研究の目的

電話やチャットのようなアプリケーションは通信しているノード同士が同じ時間を共有する。時間を共有するということは一定時間内にデータを即座にあるいは高速に相手に伝える必要がある。このような条件を満たす通信をリアルタイム通信と呼ぶ。
　 リアルタイム通信はスピードを重視し、遅延が少なくてはならない。
　 直接全てのノード同士が接続すればメッセージは最短で目的のノードへ届けることができ遅延が少ない。そのときのネットワークトポロジは 完全グラフ になり表 4 のような性質を持つ。

表 4　完全グラフの性質

次数はノード数に比例し、グラフの総辺数は2次関数的に増える。そのため制限された次数内ではノード数に上限が生じる。そのためこのグラフでは多数のノード間で通信することができない。

そこで直接目的のノードへメッセージを送るのではなく、ノードを中継し転送を行うようにする。以下はSから発せられたメッセージがRに届く例である。

図 10　メッセージの転送

このようなリングネットワーク構成することで次数を抑えることができる。リングネットワークの性質は表 5 のようになる。

表 5　リングネットワークの性質

　さきほどの完全グラフのおいては全ノード間で距離が１なのであるのに対し てリングネットワークはそれぞれの頂点間で距離が異なり、またノード数に比例して距離が大きくなる。 グラフの直径 も同様に ノード数に比例して大きくなる。 よってこれでは頂点数が多くなると転送回数が多くなり遅延が生じリアルタイム性が損なわれる。
　リアルタイム性を持つネットワークにするためには転送回数が少ない、つまり直径を小さくなるようにしなければならない。
　 そこで本研究においてはスモールワールドネットワークを応用することで 、少ない接続数で転送回数の少ないネットワークを作成し、制限された接続数内で多数のノードによるリアルタイム通信することを目的とする。

4.2 本研究の方向性

まずネットワークをグラフとして考える。 多数のノードでリアルタイムに通信することの条件として 少ない次数、小さな距離である。さらに追加要素として頂点の増加も可能なネットワークにする。リアルタイム通信のアプリケーション例として チャットソフト があげられるが、 2 人が会話をしているところに後から参加 することがよくある 。 このことは頂点数の増加を意味し、そのことを考慮することで実用性を高めるためである 。そして Peer to Peer の概念として どのノードも平等な条件であることが 重要 である。 そのことから次数のばらつきは少なくなくてはならない。
　 これらのことを考慮して 3 章で取り上げた代表的な ネットワークの特徴を以下の表にまとめる。

表 6　ネットワークモデル別の性質

ランダムグラフ、 スケールフリーは それぞれ 次数にばらつきが あり頂点ごとに平等でない。そのため Peer の概念にふさわしくない。
　 スモールワールドネットワークは 1 次元格子からネットワークを作るという点で、 Peer の概念に適している。しかしネットワークの成長 、つまり頂点の増加 は考慮されていない。

本研究ではリアルタイム通信が可能な P2P ソフトウェアを作成する。そのために適したネットワークのトポロジは次数が小さく、また直径が小さいトポロジが望ましい。この条件に関して 3 章で取り上げたネットワークのトポロジのことから、本研究で構築を目指すネットワークトポロジはスモールワールドネットワークとなる。以後このスモールワールドネットワークトポロジの構築について述べる。

5 シミュレーション実験

5.1 目的

スモールワールド性を持つグラフを作成し、距離や次数を調べる。

5.2 原理

用語定義

まずリング型での頂点の増加を考える。

リング型における頂点増加の主なステップ

図 11　リングの増加

このようにしてリングネットワークにおいて頂点を増加させることができる。

ではこれにランダムなショートカット（参加するときにランダムに頂点を選択）要素を追加する。

頂点増加の主なステップ

図 12　頂点増加による過程

このことより以下のようまとめることができる。

頂点１つあたりのリンクの内訳　

用語定義

図 13　リンクの内訳

リング型（２）＋　能動的ランダム（１）＋受動的ランダム（α）

＝３+α

表 7　グラフの次数および総辺数

この方式ではランダムに選択する際の条件によってαにかたよりが生ずる。なぜなら最初のほうに参加した頂点のほうが受動的ランダムリンクを張る機会が多いためである。そのため古株ほど次数が高くなる性質を持つ。

5.3 計画

実験1： 頂点数1000におけるトポロジ別比較

　頂点の増加を考慮せずにどのようなトポロジが有用であるか距離や次数を元に比較する

実験2： リングネットワーク＋ランダムリンク（x2）

　実験１で性能が優れていたものに対して頂点数に対する距離の増加を計測する

実験3：1000頂点まで増加

　原理で示したアルゴリズムにのっとって10000頂点まで増加させるシミュレーションを行い、距離や次数を計測する

5.4 測定方法

グラフを隣接行列で表し、ウォーシャル・フロイドによる全対最短経路のアルゴリズムを適用することで各頂点間距離および次数を測定する。そのための数値計算シミュレータを作成した。

以下に条件が頂点数12における動作サンプルを載せる

図 14　動作サンプル

よって以下のことがわかる。

表 8　頂点数12におけるパラメータ

5.5 実験1 頂点数1000におけるトポロジ別比較

5.5.1 目的

　リングネットワークにランダム2本で構成するトポロジが優れているかを検証する

5.5.2 手順

　条件

・リング：
・リング+ランダム(x1)：
・リング+ランダム(x2)：
・レギュラー（1次元格子）：
・レギュラー+ランダム(x1)：

5.5.3 結果

表 9　頂点数1000におけるトポロジ別の性質

5.5.4 考察

実験よりリングネットワークに頂点１つあたり平均 2 本のランダムリンクを持つトポロジが次数も小さく、直径も小さい。

5.6 実験2　リングネットワーク＋ランダムリンク(ｘ2)

5.6.1 目的

　実験1では頂点数1000において測定したが、頂点数10～10000においても有用であるか検証する。

5.6.2 手順

リングネットワークを作成し、ランダムリンク（ｘ2）を加えたときの平均距離およびグラフの直径を調べる

また参考として頂点数1000における距離の分布を測定する。

5.6.3 結果

表 10　リング＋ランダム(ｘ2)とリングにおける距離と直径

図 15　リング＋ランダム(ｘ2)とリングにおける距離と直径

表 11　リング＋ランダム(ｘ2)におけるパラメータ（頂点数1000）

表 12　距離による比率（頂点数1000）

図 16　距離による比率（頂点数1000）

5.6.4 考察

リングネットワークでは頂点数と距離に比例関係であるが、考案したトポロジでは頂点数の増加に伴う距離の増加はわずかであり比例関係がないことがわかる。そのことより頂点数が多いときほど有用性が高くなる。頂点数が 10000 のときにおいては平均距離が 7 より 大きくなったが 、スモールワールド の 性 が働いていることがわかる 。

平均距離とグラフの直径は、およそ以下ような関係になっている。

２×平均距離　≒　グラフの直径

5.7 実験3　1000および10000頂点まで増加

5.7.1 目的

頂点数の増加に対してうまくスモールワールド現象が成立するかを検証する。また受動的ランダムリンク（α）の偏りを測定する。

5.7.2 手順

初期条件

3つの頂点がリングネットワークでつながっている。

頂点増加の主なステップ

5.7.3 結果

表 13　頂点数増加におけるパラメータ

表 14　距離による比率

図 17　距離による比率

図 18　次数の偏り

5.7.4 考察

　またわずかではあるがグラフの直径が実験２の測定値より小さくなっている。このことより実験 3 におけるネットワークのトポロジのほうが優れていることがわかった。
　 このシステムでは初期にネットワークに参加した頂点のほうが受動的ランダムリンクが多くなる。図 18 はネットワークに参加した時系列偏差（全体を 20 分割）である。後続のノードの次数は約３であることからαはほぼ 0 であり、ほとんど受動的なランダムリンクがないことがわかる。

5.8 まとめ

リングネットワークにランダムリンクを平均 2 本ネットワークを足すことによってスモールワールド性が再現できることがわかった。また実験３より考案したアルゴリズムで頂点の増加に対応したスモールワールド性をもったネットワークトポロジがつくることが できた 。

6 P2P通信実験

6.1 目的

5 章のシミュレーション 実験 により スモールワールド性の良さを理解することができた 。そこで実際に スモールワールド性を持つがヴァーチャルネットワークを作る P2P ソフトウェアを作成する。

6.2 原理

5 章で実現した頂点増加のネットワークでは受動的ランダムリンクの次数に偏りが生じる。しかし実際には上記のような条件にはならない。なぜなら分散処理として peer の視点に立って考えた場合においてランダムリンクを選ぶ際に 5 章のような条件ではいかないからである。

5章のアルゴリズム

問題は ステップ２においてのランダム選択方法である 。新頂点はネットワークに参加時に能動的ランダムを選択するのだが、その時点で関わりある頂点は NEXT と BACK だけである。隣だけしか知っている情報がないにも関わらず全体のネットワークからランダムに頂点を選択しなければならないのである。
そこでまず考えられるのが隣の NEXT か BACK に選んでもらう紹介方式である。しかしこの紹介方式にも問題が発生する。頂点を人に例えて解説する。
はじめに教室に A 君がいたとする。

これから教室に入る人は必ず自己紹介をしてもらう。
B 君教室入って自己紹介。
A 君は B 君を知る。しかし B 君は A 君のことを知らない。
C 君が教室に入って自己紹介。
A 君、 B 君は C 君を知る。しかし C 君は A 君、 B 君を知らない。
以下このように続けていくと自己紹介のときに名詞を配るとすれば量の関係は単純に以下のようになる。

図 19　情報量の格差

このように頂点ごとに情報量に格差がある。ネットワークに参加するときにどの頂点に申し込むかで、ランダムに選出する頂点が異なる。また上図より後続のノードほど選ばれる確立が高くなるのが推測できる。

そこで別のランダム選出方法を考える。

考案したアイデア：「爆弾ゲーム形式」

新頂点は申し込んだ頂点に例として40カウント付きのメッセージを出す。

受け取った頂点はカウント数を確認し０でなければFRIENDのうちの1頂点にカウントを減らし転送する。そのように転送を繰り返すことではカウント数はやがて0になる。

カウント数が０で受け取った頂点は発行元にランダム確立メッセージを送り、新頂点は能動的、受信した頂点は受動的ランダムリンクを確立する。

メッセージを受け取った側の処理

図 20　ランダムリンク確立の過程

以上のような方法でランダムリンクを選出する。

6.3 測定方法

P2Pチャットソフトを作成し、メッセージを送信しあうことで頂点間距離および次数を測定する。

作成したソフト：「IDOBATA」
種類：チャットソフト
製作ツール：Microsoft Visual Studio .NET 2003
動作環境：OS「Windowsシリーズ」

特徴

各々のノードへメッセージを伝えるのにフラッディングの考え方を採用した。

図 21　ネットワークに参加する際のステップ

表 15　通信メッセージ情報一覧

6.4 手順

１～３を測定するノードの数の分だけ繰り返す。

なおリングネットワークに参加するさいの申し込みノードの選択基準を2つのパターンで比較する。

・ ランダム

これまで5章で行ってきたように既存のノードからランダムで選択する。既存のノードに対して確率は全て同じとする。

1点集中

リングネットワークに参加するときに1点に集中することも想定する。

ランダムに選択するさいのカウント（以後TTL）の初期値を31として計測する。

この値にした理由はグラフの直径の2倍より十分に大きな値とした。

目的のノードの数値に達したらそれぞれの頂点が最低1回メッセージ送信する。

どのノードからメッセージを発しても全てのノードに受信されることを確認する。

終わりに各々のノードがログをとる(CSV形式で保存)。

・FRIEND(NEXT, BACK, ARND, PRND)

・自分からのメンバーへの距離（ノード数分）

ログを集計しネットワークの性能を調べる。

6.5 結果

条件
TTL：31
頂点数：100

表 16　測定値

表 17　距離による分布

図 22　距離による分布

6.6 考察

ノードの増加において新ノードがネットワークに参加する際に、1点に集中するよりばらつきがあったほうがわずかながらよくなる。

7 まとめ

　本研究は 制限された接続数のなかで も 多数の PC と リアルタイムに 通信 する方法を実現するため、スモールワールド理論に着想を得ることからはじめた。そのことでスモールワールドネットワークを応用することで接続数が少なく、遅延の少ないネットワークを試みたのである。
　 5 章で スモールワールド性の有効性を確認するための シミュレーション実験を行 い、 10000 頂点において も 頂点数に 比例して 距離が 増加しない グラフを作成することができた。
　 6 章で 実際にアプリケーションを作成し P2P 通信実験を行うことで WindowsXP の 5 台という接続数の制限の中で 100 台による P2P ネットワークを構築することができた。
　 本研究では、 P2P のヴァーチャルネットワーク構成をするのにスモールワールドの概念を取り入れた。そのようなソフトウェアを実際に作り、動作させることでスモールワールドの性質を持つネットワークを実際に構築できた。

これは Windows OS でもライセンスの制限を守りながら、多数のノードでメッセージ交換が可能であることを示したことになる。

8 付録

8.1 謝辞

お忙しい中ご指導していただいた坂本先生、本当にありがとうございました。

8.2 参考文献

著者：アルバート・ラズロ・バラバシ
翻訳：青木 薫
「新ネットワーク思考―世界のしくみを読み解く」
出版社：NHK出版 (2002年)

著者：ダンカン ワッツ
翻訳：辻 竜平, 友知 政樹
「スモールワールド・ネットワーク―世界を知るための新科学的思考法」
出版社：阪急コミュニケーションズ (2004年)

著者：R. セジウィック
翻訳：野下 浩平, 佐藤 創, 星 守, 田口 東
「アルゴリズムC〈第3巻〉グラフ・数理・トピックス」
出版社：近代科学社 (1996年)

著者：チョン ウンチョル
翻訳：吉野　ひろみ
「オンラインゲームプログラミング」
出版社：ソフトバンクパブリッシング (2005年)

著者：岩田　真一
「なるほどナットク!Ｐ２Ｐがわかる本」
出版社：オーム社 (2005年)

著者：増田直樹　今野紀雄
「「複雑ネットワーク」とはなにか」
出版社：講談社 (2006年)

Albert-Laszlo Barabasi, Reka Albert, Hwoong Jeong
“Mean-field theory for scale-free randomnetworks”
http://www.citebase.org/abstract?id=oai%3AarXiv.org%3Acond-mat%2F9907068　 (1999):

フリー百科事典『ウィキペディア（Wikipedia）』
URL：http://ja.wikipedia.org/

東大で学んだ卒業論文の書き方
URL：http://staff.aist.go.jp/toru-nakata/sotsuron.html

資料

数値計算シミュレーション
チャットソフト「IDOBATA」
http://www.net.c.dendai.ac.jp/~sapoten/