ЭйгенТраст

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

Обзор

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

Алгоритм

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

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

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

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

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

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

t_{ik}=\sum _{j}c_{ij}c_{jk}

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

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

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

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

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

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

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

повторить

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

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

до

{\delta }<\mathrm {error} ;

См. также

Цепь Маркова
Собственные значения и собственные векторы в математике и физике
Eigen (библиотека C++) — библиотека компьютерного программирования для операций матричной и линейной алгебры.

Ссылки

^ Камвар, СД; Шлоссер, Монтана; Гарсия-Молина, Х. (2003). «Алгоритм собственного доверия для управления репутацией в p2p-сетях» . Материалы 12-й Международной конференции по Всемирной паутине : 640–651. дои : 10.1145/775152.775242 . ISBN 1-58113-680-3 . S2CID 3102087 . Проверено 5 июля 2015 г.
^ «Гугл Академика» . Проверено 5 июля 2015 г.

[1] Камвар, СД; Шлоссер, Монтана; Гарсия-Молина, Х. (2003). «Алгоритм собственного доверия для управления репутацией в p2p-сетях» . Материалы 12-й Международной конференции по Всемирной паутине : 640–651. дои : 10.1145/775152.775242 . ISBN 1-58113-680-3 . S2CID 3102087 . Проверено 5 июля 2015 г.

[2] «Гугл Академика» . Проверено 5 июля 2015 г.

[1]

[2]