Алгоритм распространения доверия

Алгоритм распространения доверия (также известный как алгоритм доверия, trust propagation, или алгоритм вычисления доверия на основе сети) — это класс математических и вычислительных методов, используемых для оценки степени надёжности, авторитетности или правдивости узлов в сети (например, пользователей, веб-сайтов, блокчейн-адресов) на основе их взаимных связей и взаимодействий. Основная идея заключается в том, что доверие передаётся от одного узла к другому по цепочке: если узел A доверяет узлу B, а узел B доверяет узлу C, то узел A может частично доверять узлу C, причём степень этого доверия обычно уменьшается с каждым шагом (затухает). Алгоритмы распространения доверия применяются в системах управления репутацией, рекомендательных системах, социальных сетях, децентрализованных платформах (например, блокчейн) и в задачах кибербезопасности для выявления вредоносных узлов.

История

Концепция распространения доверия возникла в контексте криптографии и сетевой безопасности, но её формализация произошла в конце 1990-х — начале 2000-х годов. Одним из первых и наиболее известных алгоритмов стал PageRank, разработанный Ларри Пейджем и Сергеем Брином в 1996 году. Хотя PageRank изначально предназначался для ранжирования веб-страниц, он использует принцип передачи «веса» (аналога доверия) по ссылкам: страница считается авторитетной, если на неё ссылаются другие авторитетные страницы. В 2004 году был предложен алгоритм TrustRank, который адаптировал PageRank для борьбы с веб-спамом: он начинал с небольшого набора «заведомо надёжных» страниц и распространял их доверие по ссылкам, позволяя отсеивать страницы с низкой репутацией.

В 2000-х годах алгоритмы распространения доверия стали активно применяться в пиринговых сетях (например, в файлообменных сетях) и в системах электронной коммерции для оценки продавцов. В 2010-е годы, с развитием блокчейна и смарт-контрактов, появились децентрализованные системы репутации, такие как EigenTrust (для сетей P2P) и Web of Trust (WoT) в криптовалютах. В России и странах СНГ алгоритмы распространения доверия используются в некоторых социальных сетях и платформах для борьбы с ботами и фейковыми аккаунтами, однако их применение регулируется законодательством о персональных данных и о противодействии экстремизму.

Классификация

Алгоритмы распространения доверия можно разделить по нескольким критериям.

По способу вычисления

• Глобальные алгоритмы: вычисляют единый рейтинг доверия для каждого узла, основываясь на всей сети (например, PageRank, TrustRank). Они требуют полного графа связей и пересчитываются при каждом изменении сети.
• Локальные алгоритмы: вычисляют доверие только для конкретного узла-запроса, используя подмножество сети (например, алгоритмы на основе случайных блужданий). Они более эффективны для больших динамических сетей.

По типу передаваемой информации

• Скалярные алгоритмы: передают одно числовое значение (например, вероятность доверия от 0 до 1). Пример: EigenTrust.
• Векторные алгоритмы: передают несколько значений, например, отдельно доверие и недоверие, или доверие с разными атрибутами. Пример: алгоритмы, основанные на теории субъективной логики (Subjective Logic).

По области применения

• Веб-ранжирование: PageRank, TrustRank, Hilltop.
• Пиринговые сети: EigenTrust, PeerTrust.
• Блокчейн и криптовалюты: Web of Trust, алгоритмы консенсуса на основе репутации (например, Delegated Proof of Stake).
• Социальные сети: алгоритмы вычисления социального доверия (например, TidalTrust, MoleTrust).

Принцип работы

Основная идея алгоритмов распространения доверия заключается в итеративном обновлении значений доверия узлов на основе их связей. Формально, пусть имеется граф G = (V, E), где V — множество узлов, а E — множество направленных рёбер. Каждому ребру (u, v) может быть приписан вес w(u, v), отражающий степень доверия узла u к узлу v (обычно от 0 до 1). Алгоритм вычисляет для каждого узла v значение t(v) — глобальное или локальное доверие.

Пример: PageRank

PageRank моделирует поведение «случайного серфера», который переходит по ссылкам с вероятностью d (обычно 0.85) и с вероятностью (1-d) переходит на случайную страницу. Значение PageRank для страницы v вычисляется по формуле:

PR(v) = (1-d) / N + d * Σ (PR(u) / Out(u)) для всех u, ссылающихся на v,

где N — общее число страниц, Out(u) — количество исходящих ссылок со страницы u. Этот алгоритм является глобальным и скалярным.

Пример: EigenTrust

EigenTrust был разработан для пиринговых сетей, где каждый узел может оценивать других после скачивания файлов. Доверие узла i к узлу j (t_ij) нормализуется, и затем вычисляется глобальное доверие как собственный вектор матрицы локальных доверий. Алгоритм итеративно уточняет значения, пока они не сойдутся. Для борьбы со злоумышленниками, которые могут завышать оценки друг другу, используется предварительно заданный набор «надёжных» узлов.

Пример: TrustRank

TrustRank модифицирует PageRank, начиная итерации с набора «заведомо надёжных» страниц (например, сайтов университетов или правительственных организаций). Доверие распространяется только по ссылкам, и его значение затухает с каждым шагом (через коэффициент β). Страницы, до которых доверие не дошло, считаются потенциально спамными.

Применение

Веб-поиск и борьба со спамом

Алгоритмы распространения доверия, такие как TrustRank и PageRank, используются поисковыми системами (например, Google, Яндекс) для ранжирования результатов поиска. Они помогают отсеивать сайты с низким качеством контента или спам-сайты, которые пытаются искусственно нарастить ссылочную массу.

Децентрализованные системы и блокчейн

В блокчейн-сетях, таких как Bitcoin и Ethereum, алгоритмы распространения доверия не применяются напрямую (используется Proof of Work), но в некоторых альтернативных системах (например, в сетях на основе Proof of Stake) репутация узлов может влиять на вероятность выбора для создания блока. В децентрализованных приложениях (dApps) и в системах Web of Trust (например, в проекте Keybase) пользователи могут подтверждать доверие друг другу, создавая граф, который затем используется для проверки подлинности личностей.

Социальные сети и рекомендательные системы

В социальных сетях (например, ВКонтакте, Одноклассники) алгоритмы распространения доверия могут применяться для фильтрации контента: если пользователь доверяет друзьям, то посты от друзей друзей могут получать более высокий приоритет. В рекомендательных системах (например, в интернет-магазинах) доверие к продавцу или товару может распространяться от одного покупателя к другому, улучшая качество рекомендаций.

Кибербезопасность

Алгоритмы распространения доверия используются для выявления вредоносных узлов в сетях (например, в системах обнаружения вторжений). Если узел с низким доверием взаимодействует с другими узлами, его «недоверие» может распространяться, позволяя изолировать потенциально опасные элементы.

Критика и ограничения

Несмотря на широкое применение, алгоритмы распространения доверия имеют ряд недостатков:

• Чувствительность к начальным данным: если начальный набор «надёжных» узлов выбран неверно, алгоритм может дать искажённые результаты. Например, в TrustRank, если в список надёжных попадёт спам-сайт, доверие может распространиться на другие спам-сайты.
• Проблема «холодного старта»: для новых узлов (например, новых пользователей или веб-сайтов) алгоритму сложно вычислить доверие, так как у них нет связей. Это приводит к тому, что новые узлы получают низкий рейтинг, даже если они заслуживают доверия.
• Уязвимость к атакам сговора: злоумышленники могут создать сеть взаимных ссылок или оценок, чтобы искусственно повысить доверие к своим узлам. Против этого используются методы, такие как введение «глобальных доверенных узлов» или использование алгоритмов, устойчивых к сговору (например, Eigentrust с предварительно заданными «пре-доверенными» узлами).
• Затухание доверия: при передаче доверия по длинным цепочкам его значение может стать пренебрежимо малым, что затрудняет оценку узлов, находящихся далеко от начальных доверенных узлов.
• Вычислительная сложность: для больших сетей (миллионы узлов) глобальные алгоритмы требуют значительных вычислительных ресурсов и времени на пересчёт.

Интересные факты

• Алгоритм PageRank, лежащий в основе Google, был запатентован в 1998 году, но срок действия патента истёк в 2018 году, что позволило другим компаниям использовать его без лицензионных отчислений.
• В некоторых системах, например, в криптовалюте IOTA, используется алгоритм Tangle, который, хотя и не является классическим алгоритмом распространения доверия, использует аналогичный принцип: каждый новый транзакционный узел должен подтвердить две предыдущие транзакции, создавая граф доверия.
• В России алгоритмы распространения доверия применяются в некоторых системах электронного голосования, где доверие к избирателям и наблюдателям может распространяться по сети, но такие системы требуют строгого соблюдения законодательства о выборах и о персональных данных.

Источники

• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web. Stanford InfoLab.
• Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004). Combating Web Spam with TrustRank. Proceedings of the 30th International Conference on Very Large Data Bases.
• Kamvar, S. D., Schlosser, M. T., & Garcia-Molina, H. (2003). The Eigentrust Algorithm for Reputation Management in P2P Networks. Proceedings of the 12th International Conference on World Wide Web.
• Josang, A., & Ismail, R. (2002). The Beta Reputation System. Proceedings of the 15th Bled Electronic Commerce Conference.
• Федеральный закон «О персональных данных» от 27.07.2006 № 152-ФЗ.