EigenTrust

редактировать

EigenTrust алгоритм - это алгоритм управления репутацией для одноранговых- одноранговые сети, разработанные Сеп Камвар, Марио Шлоссер и Гектор Гарсия-Молина. Алгоритм предоставляет каждому одноранговому узлу в сети уникальное глобальное значение доверия, основанное на истории загрузок однорангового узла, и, таким образом, направлен на уменьшение количества неаутентичных файлов в сети P2P. Согласно Google Scholar, на него ссылаются еще примерно 3853 статьи.

Содержание

1 Обзор
2 Алгоритм
3 См. Также
4 Ссылки

Обзор

Одноранговое соединение Доступные сегодня одноранговые системы (например, Gnutella ) открыты, часто анонимны и не подотчетны. Следовательно, пользователь со злым умыслом может вводить в одноранговую сеть ресурсы, которые могут быть недостоверными, поврежденными или вредоносными (Malware ). Это плохо отражается на надежности существующих одноранговых систем. Группа исследователей из Стэнфорда создает систему управления репутацией, в которой каждый одноранговый узел в системе имеет уникальное глобальное значение доверия, основанное на его истории загрузок. Любой одноранговый узел, запрашивающий ресурсы, сможет получить доступ к значению доверия однорангового узла и избежать загрузки файлов с ненадежных одноранговых узлов.

Алгоритм

Алгоритм Eigentrust основан на понятии транзитивного доверия: если одноранговый узел i доверяет любому одноранговому узлу j, он также будет доверять одноранговым узлам, которому доверяет j. Каждый одноранговый узел i вычисляет локальное значение доверия s ij для всех одноранговых узлов, которые предоставили ему подлинные или поддельные загрузки, на основе удовлетворительных или неудовлетворительных транзакций, которые он имел.

sij = sat ⁡ (i, j) - unsat ⁡ (i, j) {\ displaystyle s_ {ij} = \ operatorname {sat} (i, j) - \ operatorname {unsat} (i, j)}

s_ {ij} = \ operatorname {sat} (i, j) - \ operatorname {unsat} (i, j)

где sat (i, j) относится к количеству удовлетворительных ответов, которые одноранговый узел i получил от однорангового узла j, а unsat (i, j) относится к количеству неудовлетворительных ответов, которые одноранговый узел i получил от однорангового узла j.

Локальное значение нормализовано, чтобы предотвратить присвоение злонамеренными одноранговыми узлами произвольно высоких значений локального доверия сговорившимся злонамеренным узлам и произвольно низких значений локального доверия надежным узлам. Нормализованное значение локального доверия c ij тогда равно

cij = max (sij, 0) ∑ j max (sij, 0) {\ displaystyle c_ {ij} = {\ frac {\ max (s_ {ij}, 0)} {\ sum _ {j} \ max (s_ {ij}, 0)}}}

c_ {ij} = \ frac {\ max (s_ {ij}, 0)} {\ sum_ {j} \ max (s_ {ij}, 0)}

Значения локального доверия агрегируются в центральном расположении или распределенным образом для создания вектора доверия для всей сети. Основываясь на идее транзитивного доверия, одноранговый узел я бы попросил других одноранговых узлов, которых он знает, сообщить значение доверия однорангового узла k и взвесить ответы этих одноранговых узлов по доверительному узлу, который я помещает в них.

tik = ∑ jcijcjk {\ displaystyle t_ {ik} = \ sum _ {j} c_ {ij} c_ {jk}}

t_ {ik} = \ sum_ {j} c_ {ij} c_ {jk}

Если предположить, что пользователь знал значения c ij для всей сети в виде матрицы C, тогда вектор доверия $t ¯ i {\ displaystyle {\ bar {t}} _ {i}}$ $\ bar t_ {i}$ , который определяет значение доверия для $tik {\ displaystyle t_ {ik}}$ $t_ {ik}$ дается как

t ¯ i = CT c ¯ i. {\ displaystyle {\ bar {t}} _ {i} = C ^ {T} {\ bar {c}} _ {i}. \,}

\ bar t_ {i} = C ^ T \ bar c_ {i}. \,

В приведенном выше уравнении, если предполагается, что C апериодические и сильно связанные, степени матрицы C в какой-то момент сходятся к стабильному значению.

t ¯ = (C T) x c ¯ i. {\ displaystyle {\ bar {t}} = (C ^ {T}) ^ {x} {\ bar {c}} _ {i}. \,}

\ bar t = (C ^ T) ^ x \ bar c_ {i }. \,

Кажется, что для большого значения x вектор доверия $t ¯ i {\ displaystyle {\ bar {t}} _ {i}}$ $\ bar t_ {i}$ будет сходиться к одному и тому же вектору для каждого однорангового узла в сети. Вектор $t ¯ i {\ displaystyle {\ bar {t}} _ {i}}$ $\ bar t_ {i}$ известен как левый главный собственный вектор матрицы C. Мы также отмечаем что, поскольку $t ¯ i {\ displaystyle {\ bar {t}} _ {i}}$ $\ bar t_ {i}$ одинаково для всех узлов в сети, он представляет собой значение глобального доверия.

На основе приведенных выше результатов может быть написан простой централизованный алгоритм вычисления значения доверия. Обратите внимание, что мы предполагаем, что все локальные значения доверия для всей сети доступны и представлены в матрице C. Мы также отмечаем, что, если приведенное выше уравнение сходится, мы можем заменить исходный вектор $c ¯ i {\ displaystyle {\ bar {c}} _ {i}}$ $\ bar c_ {i}$ вектором $e ¯ {\ displaystyle {\ bar {e}}}$ $\ bar e$ , который представляет собой m-вектор, представляющий равномерное распределение вероятностей по всем m партнерам. Базовый алгоритм EigenTrust показан ниже:

t ¯ 0 = e ¯; {\ displaystyle {\ bar {t}} _ {0} = {\ bar {e}};}

\ bar t_ {0} = \ bar e;

повтор

t ¯ (k + 1) = C T t ¯ (k); {\ displaystyle {\ bar {t}} ^ {(k + 1)} = C ^ {T} {\ bar {t}} ^ {(k)};}

\ bar t ^ {(k + 1)} = C ^ T \ bar t ^ {(k)};

δ = ‖ t (k + 1) - t (k) ‖; {\ displaystyle {\ delta} = \ | t ^ {(k + 1)} - t ^ {(k)} \ |;}

{\ displaystyle {\ delta} = \ | t ^ {(k + 1)} - t ^ {(k)} \ |;}

до

δ < e r r o r ; {\displaystyle {\delta }<\mathrm {error} ;}

{\ delta} <\ mathrm {error};

См. также

цепь Маркова
Собственные значения и собственные векторы в математике и физике
Eigen (библиотека C ++), библиотека компьютерного программирования для операций с матрицами и линейной алгеброй
NEM (криптовалюта), проект блокчейна, использующий «EigenTrust ++» для вычислений важность его узлов

Ссылки