[DHT]DHTはスモールワールドか？

スモールワールドが流行してた時に、DHTもスモールワールドであるかどうか議論が盛んであった。そこでDHTが本当にスモールワールドかどうか私なりの議論をしておきたい。

□クラスタリング係数
各種ネットワークを分類するときに、平均到達ホップ数とクラスタリング係数を算出することになる。
ここでクラスタリング係数とは、あるノードAに対してリンクを張ってあるノード群PがP内のノード間でどの程度リンクを張っているか示す数値である。クラスタリング係数Cは一般に０から１まで取り、C=1ならノード間は完全グラフ、つまりとても密にリンクされていることになる。

□スモールワールドとは？
スモールワールドとは平均ホップ数が小さいのにCが大きいグラフを指す。ワッツ＝ストロガッツモデルが有名である。平均ホップ数が小さいモデルとしてはスケールフリーネットワークが有名であるが、こちらはCが小さい。

□Chordにおけるクラスタリング係数の導出

さて、これからが本題である。DHTの手法として有名なChordについてクラスタリング係数を計算してみる。
当初、Chordにおけるクラスタリング係数について具体的な計算を行っている論文を探していたが見つからなかったので、今回の方法は私が独自で計算したものである。間違い等があれば指摘してほしい。

なお、数式を簡略化するため、AのB乗をA^Bと書くこととする。

Chordにおいてハッシュ空間を2^nとする。今、Node_ID=０から見ると、リンクはAノード群：Node_ID=2^0、2^1....2^(n-1)にあることになる。また、Node_ID=0にリンクしているノードも忘れてはいけない。これはBノード群：Node_ID=-2^0,-2^1....-2^(n-1)
である。ただし、簡略化のため　-P=2^n-Pを指すこととした。クラスタリング係数を出すには、
Node_ID=2^0,2^1.....2^(n-1)、-2^0,-2^1......-2^(n-2)間でリンクがいくつあるか計算することになる。ただし、左記で-2^(n-1)=2^(n-1)であることに注意してほしい。

＊Aノード群からAノード群へのリンク数
例えば、Node_ID=2^0は自身から距離2^0,2^1.......2^(n-1)までのリンクを張っている。それではAノード群からAノード群へのリンク総数はいくらだろうか？

ここで一つ補題を出す。
□補題１：
2^a-2^b=2^cが成り立つのはa,b,cが正の整数ならa=b+1、c=a-1に限る。
証明は簡単なので省略。

すると、補題を使って、Node_ID=2^0が他のAノード群とリンクをするノードはNode_ID=2^1に限られる。
同じように、Node_ID=2^aは2^(a+1)のみAノード群とリンクを張る。
つまり、Aノード群からAノード群へのリンク数はn-1である。なお、Node_ID=2^(n-1)から上記方法でリンクをするとNode_ID=0とリンクするので、この部分はリンク数からはずしている。

＊Bノード群からBノード群へのリンク数

先ほどと同じ手順で考えればよい。
□補題2
2^n-2^a-(2^n-2^b)=-2^a +2^b=2^c
はa,b,cが正の整数ならb=a+1,c=aに限る。　

よって、Bノード群からBノード群へのリンク数はn-1である。ここで上記方法だと、Node_ID=-2^1がNode_ID=0とリンクされるので、その部分をリンク数からはずしている。

*Bノード群からAノード群へのリンク数

これも同様な手順を考えばよい。

□補題３
2^a+2^b=2^c となるには、a,b,cが正の整数なら
a=b、c=a+1になる時に限る。

つまり、Node_ID=-2^aはNode_ID=2^aとリンクをすることなる。
リンク数は結局n-1

＊Aノード群からBノード群へのリンク数
リンクで一番距離が長いのは2^(n-1)のときである。Node__ID=2^(n-1)=-2^(n-1)におけるリンク計算はBノード群からBノード群へのリンク計算に既に入っているので、ここでは考慮しなくてよい。

すると、計算で関係するのはNode_ID=2^(n-2)のときである。これよりNode_IDが小さいAノード群はBノード群まで距離が足りないからである。Node_ID=2^(n-2)は距離2^(n-1)でNode_ID=-2^(n-2)とリンクを張る。ところが、このリンクは前述のBノードからAノードへのリンク計算に既に加味されている。

結局、ノード間のリンクは3(n-1)となる。クラスタリンク係数はNode_ID=0からのリンク数が2n-1であることを考えて、

C=3(n+1)/[(2n-1)(2n-2)/2]=3/(2n-1)となる。

□Chordはスモールワールドか？

Cを見てもらうとわかるが、nが十分大きいとCはかなり小さくなる。つまりChordをスモールワールドと考えるのは難しい。Chordにスモールワールド性を取り入れたSymphonyについては同様に計算ができるはずだが、（積分計算が必要）面倒なので途中で計算を止めてしまった。興味のある方はチャレンジしてほしい。

□Pastryはスモールワールドか？

今回は具体的な計算を出さないが、適当な仮定をするとPastryのCは簡単に求まる。こちらもハッシュ空間が大きいとCが小さいという結果になる。興味のある方はチャレンジして欲しい。

□DHTとスモールワールドの関係
DHTとスモールワールドはどちらも平均ホップ数が小さい。今回わかったことはDHTだからといって、スモールワールドであるとは言えないことである。DHTがネットワーク的にどのようなネットワークに分類できるのか、グラフ論的に調査すると、きっと興味深い結論がでるだろう。