今日の井原

久しぶりに論文など紹介してみようと思う。

偉そうに論文紹介のカテゴリを作っておきながら、一年でたった５本しか紹介していないとなると、「こいつは論文もまともに読まないうんこ院生なのではないか」と思われそうだが、もちろんもっと色々と読んでいるのだ。ただここに書いていないだけだ、ということを断っておきたい。でも僕がうんこ院生だというのはその通りだと思いますけれど:-)

で。今回紹介する論文のタイトルは「The EigenTrust Algorithm for Reputation Management in P2P Networks」。 スタンフォード大のKamvarらによってWWW2003で発表された論文である。

たとえ話から入る。気になる商品があるが、その商品の分野について自分には十分な知識がない。 そういう場合、その分野に詳しい知り合いに声を掛けて、「あれが気になるんだけどどう思う？」と聞くのはよくあることである。

これをもう少し一般化して換言すると。つまり、自分にとって未知の対象を評価するのに、それを知る（１人、あるいは複数の）誰かにクエリを投げてその誰かの評価値を受け取り、それを自分の中で統合して間接的に評価値を決定するわけである。未知の対象を評価するのに、間に誰かを挟むところがミソだ。

この論文では、そういう「間接的な評価」を定式化し、P2Pのノード管理やらWeb検索やらに適用するスコアリングアルゴリズム"EigenTrust"として提案している。

元々はP2Pなファイル交換ネットワークでうんこなノードを見つけるために、各々のノードについてunique global trust valueを算出しましょう、という話から出発している。……のだが、定式化されたアルゴリズム自体は広く応用が利きそうな、なかなか興味深いものになっている。お勧めの論文である。

アルゴリズム自体もシンプルで、高度な応用数学を使ってどうこう、というようなことはしていないので、すんなり理解できるとおもう。途中、CAN（P2Pネットワークで使われる分散ハッシュの形態の一つ）をあれこれする部分が出てきて、その辺りの知識がないとわけわかめだと思うが、この辺りはすっ飛ばしてかまわない。

P2Pネットワークや検索技術に興味があるなら、読む価値のある論文だと思う。

The EigenTrust Algorithm for Reputation Management in P2P Networks
http://www.stanford.edu/~sdkamvar/papers/eigentrust.pdf

You can ping this entry by using http://windy.ac/MT/mt-tb.cgi/696 .