アルゴリズムの拡張

上記のアルゴリズムによる信頼値の計算は、他のノードから返される内容の正しさを知ることができないという問題点があります。 悪意のあるノードが紛れ込み、善意のノードの信頼値を低く、不誠実なノードの信頼値を高く見積もった値を返すかもしれません。

この問題は、他のノードの返した値の信憑性(credibility)を評価し、そのノードの報告した信頼値を信憑性で重み付けすることによって改善できます。 そのためにcommon(u,v)common(u,v)を定義します。これはノードuuとノードvvの両方と交信したノードの集合です。 そうすると、2つのノードに返されたフィードバックの類似性sim(u,v)sim(u,v)が以下のように計算できます。

sim(u,v)={(1wcommon(u,v)(suwsvw)2common(u,v))b(ifcommon(u,v)0)0(otherwise) sim(u,v) = \left\{ \begin{array}{ll} \biggl( 1-\sqrt{ \frac{\sum_{w \in common(u,v)}(s_{uw} - s_{vw})^2}{|common(u,v)|} } \biggr)^b & (if \: common(u,v) \neq 0) \\ 0 & (otherwise) \end{array} \right.

ただしbbは正の整数(原著論文ではb=1b=1を示唆)です。

その場合、フィードバックの信憑性は以下のようにして定義されます。

fij={sim(i,j)msim(i,m)(ifmsim(i,m)>0)0(otherwise) f_{ij} = \left\{ \begin{array}{ll} \frac{sim(i,j)}{\sum_m sim(i,m)} & (if \: \sum_m sim(i,m) \gt 0) \\ 0 & (otherwise) \end{array} \right.

最終的にフィードバックの信憑性を考慮に入れた信頼値の行列L=(lij)L=(l_{ij})は以下のように定義されます。

lij={fijcijmfimcim(ifmfimcim>0)0(otherwise) l_{ij} = \left\{ \begin{array}{ll} \frac{f_{ij}c_{ij}}{\sum_mf_{im}c_{im}} & (if \: \sum_mf_{im}c_{im} \gt 0) \\ 0 & (otherwise) \end{array} \right.

これで、前頁の最後の更新式の拡張版を定義することができます。

ti={p(ifi=0)(1a)LTti1+ap(otherwise) \vec{t_i} = \left\{ \begin{array}{ll} \vec{p} & (if \: i = 0) \\ (1-a)L^T\vec{t}_{i-1} + a\vec{p} \:\: (otherwise) \end{array} \right.

これはべき乗法によって、対応する行列の左特異ベクトルに収束します。

Eigentrust++の原著論文では誠実なノードとそうでないノードとの間の信頼値の伝搬に制限を加えるためにもう一点工夫が加えられていますが、この論文はファイル共有ネットワークへの適用を念頭に置いたものです。 そのようなネットワークでは完全でないデータ(ファイルの一部)が共有される場合があり、その正当性をチェックすることができません。誠実に振る舞っているノードでも問題のあるデータを拡散してしまう場合があるのです。 対して、NEMのノードは常にデータを完全な形式でダウンロードし、他のノードに拡散する前にその完全性をチェックします。 悪意のあるノードが存在する場合でも、信頼の伝搬形式にこれ以上付け加える必要がないことは、NEMネットワークのシミュレーションによって確認されています。

図6

常に非誠実に振る舞うノードによる攻撃のシミュレーション

results matching ""

    No results matching ""