無印吉澤（※新エントリはhatenablogに掲載中）

■[ネットワーク][P2P]Small WorldとScale Freeって結局どっちがいいの？

最近、SNS等との絡みでネットワーク構造に関する本が流行っていて、僕も今までに何冊か読んでみました。

• 新ネットワーク思考（Scale Free Networkを提唱したバラバシの著書）
• スモールワールド・ネットワーク（Small World Networkを提唱したワッツの著書）
• SYNC（ワッツの共同研究者のストロガッツの著書）
• 人脈づくりの科学（主にソーシャルキャピタルを扱った和書）

それで、Small World NetworkやScale Free Networkのモデルが、社会、自然界、インターネット等で見られる実世界のネットワークをうまく説明できるというのはなんとなく分かったんですけど……ただ、コンピュータネットワークに関わる人間にとってこれがどういう意味を持つのかは、ほとんど飲み込めないままでした。

ただ、最近DHTオフ会で小島氏の講演*1を聞いてから、そのあたりのモヤモヤした部分がなんとなく整理できそうな気がしています。とはいえ、まだ完全には飲み込めてなくて、この日記を書くのにも1週間以上かかっちゃってるんですが、とりあえず現時点での僕の理解を少しまとめてみます。

■ スモールワールド現象（Small World Phenomenon）

イベント等で会った初対面の人と話してみると、実は自分と共通の知り合いが居たりする。そういう「世間は狭いなあ！（It's a small world!）」と言いたくなる実世界の友人・知人関係を、社会学の世界ではスモールワールド現象と呼んでいます。この現象に対する疑問点は、以下のQ1のように言い換えられます。

Q1. 知人関係にある任意のXとYは、共通の知人Zを持つか？

これは、人間関係のネットワークがどういう形をしているか、という疑問でもあります。

一方、スモールワールド現象と呼ばれるもので更に有名なものとしては、社会心理学者スタンレー・ミルグラムによる「小さな世界」実験から推測された「人はすべての人と平均5.5人を介して繋がっている（Six Degrees of Separation）」という現象があります*2。

この平均値はあくまで知人からその知人へ、そしてまた次の知人へ……と手紙を転送していって「最後まで届けることのできた手紙」の辿った人数の平均値なので、最後まで届かなかった手紙を考慮に入れればもっと平均値は大きくなると思われます。また、人間にはネットワーク全体の構造が分からないため、「最後まで届けることのできた手紙」についてもそれが最短の経路を通ったかどうかは分からない、という意見もあるようです。

ただ、それを考慮しても、この実験は全く関係のない人同士が（人類の総人口と比較して）かなり少ない人数を介して繋がっている可能性を示しています。この現象に対する疑問点は、以下のQ2のように言い換えられます。

Q2. 知り合いでない任意のXとYは、他人を通して繋がっているのか？　またその仲介数は？

任意のノードXからノードYに辿り着くまでに経由しなくてはならないリンクの平均数は、そのネットワークの直径（Diameter）と呼ばれます。従って、上記のミルグラムの実験結果は、社会的なネットワークの直径が人類の総数（全ノード数）と比較して極端に小さいことを示している、と言い換えられます。直径の小さいネットワークは、1つのノードから全体へ効果的にアクセスできるネットワークです。

実世界のネットワークは、Random Networkでもないのに何故直径が小さくなるのか？　それを説明できるモデルとして登場したのが、Small World NetworkとScale Free Networkです。

■ Small World Networkのモデル

これは、ノードが密接に結びついたクラスタ（high clustered）と、それぞれのクラスタを繋ぐ少数のリンク（shortcut links）があれば、ネットワーク直径が小さくなる（low diameter）というモデルです。

high clustered + shortcut links -> low diameter

このモデルでは、ノードがどれくらい密接に結びついているかをクラスタリング係数で示します。クラスタリング係数は、ネットワーク上の任意のノードにリンクされたノード2つを選択したときに、その2つのノード間にリンクが存在する可能性を示す値（Q1を数値化したもの）です。要するに、この値が大きいほど、知り合いの知り合いが知り合いである可能性が高いわけです。

一方、クラスタを繋ぐ少数のリンクがどれくらい効果的かなものかは、単純に数値化できません（違ってたらすみません……）。従って、クラスタリング係数とネットワーク直径を計算することで、そのネットワークのSmall World性を調べることができます。

■ Scale Free Networkのモデル

これは、非常に多くのリンクを持つ少数のハブ（hub node）が存在することで、ネットワーク直径が短くなる（low diameter）というモデルです。

hub node -> low diameter

Scale Free Networkはリンク数xと、x個のリンクを持つノードの数yの関係が、べき乗則（Power Law）に従うという特徴を持っています。従って、各ノードのリンク数の分布（次数分布）を調べることで、そのネットワークのScale Free性を調べることができます。

Small World Networkのモデルとは異なり、こちらのモデルにはクラスタという概念はなく、Q1については何も答えていません。

■ で、どっちがいいの？

ネットワーク構造だけを単純に見てみると、コンピュータネットワーク（やそのオーバレイネットワーク）の構造としてはScale Free NetworkよりもSmall World Networkの方が優れていそうに見えます。どちらの構造にしてもネットワークの小直径性という効果が得られるなら、アクセスが極端に集中してボトルネックになりそうなノード（＝ハブ）をわざわざ作る必要なんて無いのでは？という理屈です（Scale Free Networkのアタック脆弱性）。

かといって、そのコンピュータネットワーク上でデータの送受信を行うことを考えると、Small World Networkでは経路制御の仕組みが複雑になりそうな気がします（Random Networkよりはだいぶましだと思いますけど）。

ノードはSmall World Network全体の構造を知り得ないために、データを運ぶ際にショートカットを利用できず、結果としてそのステップ数がネットワーク直径を大幅に超えてしまう……なんてことが起きても何も不思議ではありません。一方、Scale Free Networkならばハブがルーティングテーブルを管理して、それ以外のノードは経路制御に関与しないという解決方法が取れそうです（例：インターネット上のルータとエンドノードの関係）。

そう考えていくと、結局のところコンピュータネットワークはSmall World Networkであるべきなのか、Scale Free Networkであるべきなのかが、よく分からなくなってきます。もちろん、実際のネットワークは二者択一でどちらか一方のモデルのみに従う、というものでは無いと思いますけど……そう結論づけてしまうのも、あまりにも実入りがなさすぎてイヤな感じです。

■ Kleinbergの問題

上記の疑問のうち、Small World Networkでの経路制御問題について疑問を投げかけたのが、2000年に発表されたJon Kleinbergの論文"The small-world phenomenon: An algorithmic perspective"です。

この研究、僕は小島氏の講演を聞いて初めて実質的な意味が分かったのですが、実際に論文を読んでみても割と参考になることが書かれています。で、この研究の先に、Small World Networkの考え方を導入したDHTであるSymphonyや、Gnutellaよりも性能の良いP2P検索エンジンを目指したTellaGateがあるわけなのですが、ここまでが少し長くなりすぎてしまったので、続きは次回にまとめてみます。

（続く）