автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метрики репутации

ГРИЩЕИКО Викюр Сергеевич

МЕТРИКИ РЕПУТАЦИИ

V

модели и алгоритмы построения открытых информационных сред

05 13 18 — математическое моделирование, чисчсппые методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на юпекание )чспой степени кандидата физико-математических паук

Екялсршгбур!

2007

003069795

Работа выполнена на кафедре алгебры и дискретной математик математико-механического факулыета ГОУ ВПО "Уральский государственный университет им А М Горькою"

Научный руководитель доктор физико-математических наук, профессор М В Волков

Официальные оппоисшы

доктор технических наук, профессор Л А Захаров

кандидат физико-математических наук, доцент С И Кацман

Ведущая организация Уфимский государственный авиационный технический университет

Защита состоится 23 мая 2007 I в 15-00 часов на заседании диссертационного совета К 212 286 01 по присуждению ученой степени кандидата физико-магемагических наук при ГОУ ВПО "Уральский государственный университет им А М Горького" по адресу 620083, I Екатеринбург, пр-1 Ленина, 51, коми 218

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО "Уральский государственный университет им А М Горького"

Автореферат разослан "30" 2007 г

Ученый секретарь диссертационного совета, доктор физико-математических наук, профессор

В Г Пименов

1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Ситуация, сложившаяся в наши дни в области производства и обработки информации, часто характеризуется как "информационный взрыв" Такие наблюдаемые параметры, как количество научных публикаций и изданий, количество страниц во Всемирной Сети, трафик в inirepiieie, растут экспоненциально [12, 14] В подобных условиях становятся все более важными средства автоматического упорядочения и обработки информации - такие, как поисковые машины, рекомендующие системы и т п

Тенденция последних лет заключается в том, что широкое распространение уже собранной информации (публикация) более не представляет проблемы Всемирная паутина для íencia, однорашовые (peer-to-peer, Г2Р) сети для мультимедийного содержимого приблизили издержки распространения к нулю На первый план поэтому выходят проблемы сбора рассеянной информации и распространения немассовой (г с интересной относительно узкому кругу лиц) информации При этом становится популярной так называемая концепция "Длинного хвоста" Под этим названием подразумеваются наблюдаемые в самых различных сферах степенные распределения популярности [3], когда многочисленные источники немассовой информации в совокупности представляют не меньший интерес, чем относительно малочисленные источники - "звезды" В ответ на указанные запросы возникли сначала форумы и блоги (веб-дневники) с комментариями-репликами, а затем вики с совместной правкой содержимого

Сбор мнений от неопределенно широкого круга лиц требует значительной открытости среды, те возможности дико вносить свои мнения При этом неизбежно столкновение с принципиальной проблемой, чрезвычайно актуальной для Cein последние десять лег, - засорением информационных срсд, действующих по принципу push (проталкивание содержимого к потребшелю) Для злонамеренного проталкивания нерелевантных материалов в рекламных или мошеннических целях принят термин "снам" Спам существует в почте, интернет-пейджерах, блогах, вики, поисковых машинах — везде, где есть элемент push В средах, действующих но принципу pull (вытягивание информации пользователем), например, в FTP (протокол передачи файлов) или в "чистом" WWW, спама нет Но в них и сбор рассеянной информации непрост

Итак, фокус инноваций переместился на сбор, фильтрацию и адресное pacripocipaiiciiiie информации, чаще локального либо узкоспециального значения, и основное препятствие на этом пути - это засорение, ограничивающее открытость информационных сред

Один из подходов к борьбе с засорением - метрики репутации, отслеживание прошлого поведения участников Для борьбы со спамом в электронной почте, например, широко применяются репутационные инструменты - 1ак называемые белые и черные списки (i е списки добросовестных и недобросовестных почтовых серверов соответственно) В том или ином виде метрики репутации также используются в поисковых машинах, онлайновых аукционах, на "социальных" сайтах и т д

С изменением задач изменилась и топология информационных взаимодействий от централизованного распространения центр тяжести смещается к социальным сетям, сообществам и группам В плане осуществления контроля как замена централизованным механизмам, имеющим свой потолок масштабирования, активно опробуется общий подход "сети доверия" (Web-of-Trust) или социальных сетей, заключающийся в использовании транзитивных свойств устоявшихся социальных связей [1, 8, 15, 17] Подход базируется на механизмах, доказавших свою работоспособность в реальном мире именно для решения проблем интересующего нас типа Тем не менее, его использование в онлайновых сервисах пока имеет имеет частный, ограниченный характер

Диссертация затрагивает такие темы, как совместное фильтрование, социальные сети, системы доверия и репутации, одноранговые сети Все эти направления активно исследуются в последние 8-10 лет [2, 4-7, 9-11, 13, 16] По каждому из них существуют уже вполне удавшиеся продукты и проекты, 1акие, как рекомендующие системы Amazon и Epimons, онлайновая социальная сеть Linkedln, алгоритм PageRank, одноранговая сеть BitTorrent, открытая онлайновая энциклопедия Wikipedia

Цель работы Используя математическую модель распространения информации в среде с социальной топологией, разработать алгоритмы функционирования распределенной вики-сети, использующей явную работу с мнениями читателей и репутационные механизмы для массивной распределенной обработки и фильтрации материала Оценить вычислительную сложность разработанных алгоритмов Реализовать алгоритмы в программе-прототипе

Задачи

• Разработать адекватную формальную модель мнений, репутации и рекомендаций, образующих сеть доверия

• На основе построенной формальной модели социальной сети создать алгоритмы для сбора, распространения, фильтрации и обработки информации в максимально открытой среде

• Дап> теоретические оценки вычислительной сложности разработанных алгоритмов

• Реализовать алгоритмы в виде работающих программных комплексов или их прототипов

• Реализовав ceib доверия для персональных коммуникаций (в первую очередь, e-mail) как репутационпый механизм для борьбы со спамом

Направления исследования

1 Репутационная аксиоматика, основанная на теории нечетких множеств, отражающая все требуемые явления ответственность, репутацию, рекомендации, и определяющая математическую модель - основу дальнейшей работы

2 Маршрутизация в безмасштабных сетях как метод построения ре-комендационных цепочек на социальном графе

3 Топологические аспекты распространения общего знания в социальных сетях в предположении бсзмасштабной топологии

4 Создание алгоритмов среды обработки информации, действующих поверх социальной сети и использующих эту сеть для распространения, фильтрации и хранения произвольной информации

Этапы работы На теоретическом этапе исследования была разработана полностью персонализованная репутационная аксиоматика Затем на основе теории сложносш вычислений и анализа топологических осо-бенпосюй целевою семейства графов были разработаны полностью де-цешралиюванные алюритмы, реализующие принципы репутационных вычислений применительно к информационным средам С использованием модели социальной сети на основе графов Эрдсша-Репьи и безмас-шгабных графов была получена оценка вычислительной сложности разработанных алгоритмов, оказавшейся приемлемой с точки зрения возможностей практической реализации На закчючигельном этапе исследования разрабоганиые алгоритмы составили ядро программных комплексов, имеющих практическую ценное ть

Методы исследования В работе используются методы теории графов н нечеткой логики, а также методы дискретной оптимизации, оценки вычисли (ельной сложности алгоритмов и экспериментальные данные по функционированию С01евых протоколов интернета

Основные результаты, выносимые на защиту

• Репутационная аксиоматика

• Теорема о достижимости информации в сеги с социальной топологией

• Социальная вики-сеть Бульон - модель, алгоритмы и программное обеспечение

• Маршру шзационная схема с топонимами для безмасшт абных сетей решение задачи о кратчайших путях на безмаенпабном графе с сублинейной вычислительной нагрузкой на узел

• Репутационная система Р2Р\¥Ь (общие белые списки для почтовых серверов) - модель, алгоритмы и программное обеспечение

Достоверность и обоснованность Работоспособность алгоритмов проверяется как аналитически, так и через создание реально работающих программ Значительная часть работы посвящена вопросам вычислительной сложности алгоритмов Эффективность маршрутизаци-онных алгоритмов проверяется через вычислительные эксперименты на реальных и синтетических топологиях и сверку результатов с классическими алгоритмами Ключевые аспекты работоспособности сети Бульон рассматриваются на аналитических моделях, общая работоспособность проверяется через создание работающего прогошпа Теоретическая работоспособное I ь репутационной сети обмена белыми списками РЗРМ'Ь вытекает из работоспособности вышеупомянутых маршрутизационных алгоритмов Базовый прототип Р2Р\¥Ь запущен в промышленную эксплуатацию на клике почтовых серверов г Екатеринбурга

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

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

Разработанный автором оригинальный алгоритм маршрутизации с именами малого сублинейного размера (топонимами) впервые решает

задачу о кратчайших путях для безмасшгабиых графов с сублинейной сложностью в расчете па узел (Задача о всех кратчайших путях для произвольных графов имеет линейную сложность па узел, и известно, что чтог результат в общем случае неулучгпаем ) Наблюдения за реальными сегямгг и аналитические резулыагы показывают, что сети безмас штабной топологии распространены весьма широко, в силу чего предлагаемый алюритм маршрутизации имеет большое практическое значение

Предложена модель издержек коммуникации, иллюстрирующая фундаментальную важность бсзмасштабпой топологии дчя информационных сетей различного рода

Разработанная автором среда Бульон, а также лежащий в ее основе протокол, впервые реализуют совместную работу с редактируемым гипертекстом в одноранговой сети (внесение, правку, фильтрацию, распространение гипертекста) Ранее известные среды (например, rreenct) позволяли чишь хранить документы в одноратновой сети

Разработанное автором программное обеспечение P2PWL является, по-видимому, первой попыткой расширить возможности "белых списков", основанной на открытом решении в одноранговой архитектуре

Практическая значимость и внедрение результатов Разработанный автором программный комплекс Бульогг, а также лежащий в его оеггове протокол, характеризуются следующими особенностями

• это гипертекстовая среда, где документы связаны гиперссылками,

• это редактируемая среда с возможностями совместной обработки документов (wiki),

• это открытая одноранговая есть с юциальной топологией (такой тип сети также называется F2F, Iriend-lo-friend),

• в этой среде репутации и мнения пользователей (рекомендации) используются для совместного фильтрования материала

По ггабору возможностей среда Бульогг является уникальной, по-видимому, нет онлайновой среды, имеющей более двух из перечисленных характеристик По полезному функцнонату Бульон сочетает возможности Р2Р сети, рекомендующей системы, онлайновой социальной сети, браузера и текстового процессора В отношении базовых принципов распространения информации среда Бульон использует как pull ("вытягивание'' информации пользователем), так и push ("проталкивание" информации к пользователю) Характерная проблема push-сред, а именно засорение, решается фундаментальным образом, через отсутствие гголггой связности участников Участник имеет возможность протолкнуть информацию

лишь в нскоюрую свою социальную окрестность Э101 подход, имитирующий социальные процессы реальною мира, является принципиально новым для сетевых сред

Если опыт эксплуатации среды Бульон большим количеством пользователей подтвердит теоретические оценки, данная техпол01 ия может стать основой хранилища знаний, значительно превосходящего существующие образцы по охвату и глубине представленных знаний и удоб-ст ву использования Такая среда може г бы гь более полным воплощением метафор "социальною вики", "Редактируемой Паутины", а икже "Социальной Паутины", чем все теперешние модели социальных сетей

Использование P2PWL в объеме самого базового функционала уже сегодня позволяет преодолеть основной недостаток "серых списков" - задержку писем от ранее неизвестных отправителей (что также означает и задержку практически всех писем первое время после установки) Так, белый список почтового сервера plotmka ru, сформированный с помощью F2PWL, на сегодня включает порядка 10 тысяч других почтовых серверов, т е практически все местные, заметные федеральные и самые значимые из мировых почтовых серверов представлены в этом списке

Апробация и публикации Все основные результаты диссертации отражены в 8 публикациях, среди которых 2 развернутых журнальных статьи, 3 развернутых статьи в трудах международных конференций и 3 тезисов докладов на отечественных конференциях и семинарах Все публикации выполнены без соавторов

Результаты диссертации представлялись и докладывались на международных конференциях в Ирландии (Workshop on Friend of a Friend, Social Networking and the Semantic Web, Голуэй, 2004), Японии (Workshop on Trust, Security, and Reputation on the Semantic Web, Хиросима, 2004) и Греции (SecureComm Workshop on the Value of Security through Collaboration, Афины, 2005), а также на конференциях молодых ученых в Москве и Екатеринбурге и на научных семинарах "Теоретические компьютерные науки" (рук Д С Ананичев, М В Волков) и "Системный семинар" (рук М В Баклановский, В Ю Попов) в Уральском государственном университете

Структура работы Диссертационная работа состоит из 124 страниц машинописною текста, включающего введение, пять глав и заключение, а также приложение, глоссарий, рисунки, таблицы и список литературы из 120 наименований

2 ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 дается краткий обзор современных результатов d смежных с тематикой диссертации областях - онлайновых социальных сетях, метриках доверия и репутации, рекомендующих системах, одноранговых сетях и пр Рассматриваются особенности тополотии социальных сетей, а именно, безмасштабной (scale-free) тополопш

В качестве основного признака безмасштабной топологии сети обычно указывается степенное распределение степеней вершин число вершин степени х есть величина порядка х-7, где 2 < 7 < 3 В частности, что у основной массы вершин связей мало, но у некоторого малого количества вершин ("хабов") связей очень много Другим признаком безмасштабно-сги считается некоррелированность степеней соседей В безмасштабных сетях реального мира наблюдается высокий коэффициент кластеризации, т е высока вероятность того, что два соседа случайной вершины будут соседями и между собой Тем не менее, все указанные признаки недостаточны для строгого определения, и понятие безмасштабного графа на сегодня скорее естественно-научное, чем математическое К классу безмасштабных относят граф ссылок в WWW, 1раф маршрутизаторов в интернете, граф автономных систем интернета, граф академических соавторств, граф e-mail контактов и т д

В 1лаве 2 дается анализ общих вопросов, (вязанных с распространением информации в социальных сетях, репутационными метриками и пр Выделяется типовой подход к решению некоторых задач на графах, названный "степенной разлом" Степенной разлом - это разделение задачи сложности O(N) на две задачи сложностей О(Р) и 0(Q) - так, что N ~ PQ, а сложность "разложенной" задачи имеет порядок 0(Р + Q), т е сублинейный Приводятся различные примеры применения разломов на практике, в основном - в задачах о маршрутизации Исследуются подходы к решению задач сложностного и топологическот о характера, связанных с реализацией метрик репутации на безмасштабных графах, в основном, это задачи о маршрутизации и распространении информации Па основе известных свойств безмасштабной топологии делается вывод о том, что принцип подтверждения сообщения промежуточным узлом, лежащий в основе Вульон, позволит передавать сообщение из одной произвольной точки сети в другую произвольную, в идеале, за два

промежуточных прочтения и подтверждения - независимо ог размера сети Затем из моделей распространения информации на основе графов Эрдеша-Реггьи и безмпешгабпых графов, а также других соображений выводится основная теорема о достижимости материал в сети вггда Бульон доступен ботышптству участников, если он распространился на сублинейную дотто узлов N", а каждый участник может запрашивать свою соответствующую сублинейную окрестность Nb (здесь N - число узлов сети, a a f Ь < 1)

Из свойств скелета безмасшгабтюто графа делается заключение, что его коммуникационное ядро, образуемое хабами, имеет сублинейный размер относительно всего графа

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

В главе 3 предлагается репутационная аксиоматика, основанная на теории нечетких множеств В основе предтоженной репутационной теории лежит определение репутации как средней меры соответствия прежних сообщений, за которые были ответственны те же участники, и гипотеза, состоящая в том, что прошлое поведение (т е репутация) в некоторой степени преде казывает будущее поведение Па основе этих положений конструируется многоуровневая репутационная модель, где каждый следующий уровень - репутационная рефлексия относительно предыдущего уровня Таким образом, если путевой уровень - это ответственность за собственные сообщения, то первый уровегть - это мнения относи гель-но чужих сообщений, второй - мнения относительно чужих мнений (т е мнения о репутации других участников), а аналогом третьего уровня могут служить рейтинги ишернет-каталогов или кредитных бюро, т е мнения о качестве рекомендаций рекомендателей Затем рассматриваются случаи групповой и персональной коммуникации и многоуровневая модель применяется к этим случаям В результате возникают две модели работы с сообщениями модель групповых коммуникаций ("горизонтальная", соответствует таким средам, как Usenet, списки рассылок, форумы) и модель персональных коммуникаций ("диагональная", соответствует e-mail)

Глава 4 посвящена проекту Бульон, реализующему горизонтальную

модель Бульон имеет целыо создание среды, в наибольшей степени сочетающей принципы открытости и контроля С технической точки зрения, Бульон - это одноранговая вики-сеть, работающая в социальной топологии, где содержимое распространяется вдоль доверительных связей с помощью репутации и рекомендаций С пользовательской точки зрения, Бульон - гибрид браузера, текстового процессора и интернет-пейджера, позволяющий как просмотр, так и совместное редактирование гипертекста в режиме почти-реального времени

Распространение сообщений в сети Бульон ограничивается таким понятием, как репутационное расстояние (согласно горизонтальной модели) Изначально находясь на узле автора, сообщение может быть доступно его друзьям и друзьям друзей, конечно, если репутация автора высока В случае, если кто-то из них ею прочитал и подтвердил, оно начинает быть доступно уже друзьям друзей подтвердившего, т е распространяется в социальной сети В отличие от клиент-серверного общения, которое сводится к диалогу, многосторонний обмен информацией в одноранговой сети представляет из себя менее тривиальный процесс, включающий распространение запросов и возврат ответов В главе рассматриваются различные архитектурные выборы и связанная с ними вычислительная сложность алгоршмов Нормальное функционирование системы предполагается при условии обработки каждым узлом до 100 сообщений в секунду, чю незначительно в топологии Р2Р (100 со-общ/сек на одну машину) и довольно дорого в серверном решении (100л сообщ/сек на сервер, где п - количество пользователей сервера)

IIa настоящий момент разработанное автором программное обеспечение Бульон версии 2 вполне функционально и доступно для публичного тестирования но адресу http //ос-со org

В главе 5 излагается принцип работы антиспамовой технологии P2PWIj - обмен автоматически создаваемыми "белыми списками" между почтовыми (SMTP) серверами "Белые списки" включают те почювые сервера, письма от которых принимаются безусловно Им противоположны "черные списки", которые суть просто списки контролируемых спа-мерами машин Под "серыми списками" понимается механизм задержки получения почты от ранее неизвестных отправителей, создающий ряд труднопреодолимых проблем для спамеров Технология P2PWL расширяет возможности белых списков и является вспомогательным инструментом к системе серых списков, общие белые списки P2PWL исключают задержки писем в подавляющем большинстве случаев В перспективе P2PWL реализует диа1 опальную модель Необходимые системе P2PWL вычислительные затраты на каждом узле (SMTP-сервере) оцениваются как сублинейные относительно количества участников и, принимая во

внимание прочие соображения, являются не только посильными, но и не очень значительными

IIa настоящий момент созданная авюром система P2PVVL действует на нескольких серверах и доступна но адресу http //ос-со org/p2pwI

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

3 ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

Разработана репутационная аксиоматика на основе нечетких множеств На базе аксиоматики построены горизонтальная и дна!опальная модели информационных пространств со встроенными метриками репутации Полученные и привлеченные результаты по сложности маршрутизации, распространения и поиска информации в безмасгатабных графах убеди 1ельно свидетельствуют в пользу вывода о практической применимости горизонтальной и диагональной моделей в сетях с произвольно большим количеством участников

Разработана концепция топонимов (имен матого сублинейною размера) для задачи о маршрутизации на безмаепттабном графе Вычислительный эксперимент доказал эффективность алгоритма - задача о кратчайших путях решена с сублинейной нагрузкой на узел

Разработан про юкол для социальной одноранговой сети обработки произвольного XML, реализующей горизонтальную модель Разработан программный комплекс, использующий этот протокол для поддержки однорангового вики в социальной сети - сис тема Бульон В принципах устройства сети Б}льон удалось отойти от классических ограничений онлайновых сред - серверных i раниц и использования аккаунтов в качестве механизма контроля доступа Пробтема сбора, фильтрации и распространения информации решается через явное вовлечение мнений пользователей н механизм социальных сетей

Основан новый репугациопный инструмент, дополняющий серые и черные списки - система общих белых списков P2PWL Уже на сеюдня P2PWL представляет значительную практическую ценность В дальнейшем эта система способна развиться до полноценной реализации диагональной модели

Работы автора по теме диссертации

1 В С Грищенко Исчисление мнений // Известия Уральска о государственного университета Серия Компьютерные пауки и информационные технолга ии 2006 №43 С 139-153

2 В С Грищенко Некоторые новые подходы к маршрутизации в Интернете // Извеоия Уральскою государственного университета Серия Компьютерные науки и информационные технологии 2006 №43 С 198

3 В С Грищенко Метрики репутации и борьба за релевантность // Материалы Международной научно-практической конференции студентов, аспирантов и молодых ученых "Безопасность информационного пространства" - Изд-во УрГУПС Екатеринбург, 2006 С 89

4 В С Грищенко Черви Уорхола и модульные черви перспективы эпидемий в Интернет // Труды XXIV конференции молодых ученых механико-математического факультета МГУ им М В Ломоносова, Т I Изд-во МГУ Москва, 2002 С 62-64

5 V S Grishchenko Redefining web-of-trust reputation, lecom-mendations, responsibility and trust among peers // Proceedings of the First Workshop on Friend of a Friend, Social Networking and the Semantic Web National University of Ireland, Galway 2001 P 75-81

6 V S Grishchenko A fuzzy model for contert-dependent reputation // Proceedings of the International Semantic Web Confeience 2001 Woikshop on Trust, Security, and Reputation on the Semantic Web Hiroshima, 2004 (Электронное издание CEUR Workshop Proceedings, ISSN 1613-0073, Vol 127)

7 V S Grishchenko Computational complexity of one reputation metric // Proceedings of IEEE/Create-Net SecureComm 2005 Workshops SECOVAL Workshop Athens, 2005 (Электронное издание, ISBN 0-78039469-0 )

8 V S Grishchenko Distance-based reputation metrics are practical in p2p environments // International Journal of Metadata, Semantics and Ontologies 2006 Vol 1, №2 P 133-140

Список литературы

|1] Abdul-Rahman Л , Ilailes S A distributed trust model // NSPW '97 Proceedings of the 1997 workshop on New security paradigms — New York, NY, USA ACM Press, 1997 - P 48-60

[2] Abdul-Rahman Л , BailetS Using recommendations for managing trust m distributed systems // Proceedings of the IEEE Intl Conference on Communication, Malaysia — 1997

[3] Anderson С The Long Tail — Random House Business Books, 2000 — July

[4] Chord a scalable peer-to-peer lookup protocol for internet applications / I Stoica, R Morris, D Liben-Nowell et al // IEEE/ACM Trans Netw - 2003 — Vol 11, no 1 -P 17-32

15] Cohen В Incentives build robustness m bit torrent —■ http //www bittorrent org/bittorrentecon pdf

[6] Despotovic Z, Aberer К P2p reputation management Probabilistic estimation vs social networks // Computer Networks — 2006 — March — Vol 50, no 4 - P 485-500

[7] Evaluating collaborative filtering recommender systems / J L Ilerlocker, J A Konstan, I, G Terveen, J T Riedl // ACM Trans Inf Syst - 2001 - Vol 22, no 1 - P 5-53

[8] Golbeck J , Ilendler J Accuracy of metrics for inferring trust and reputation m semantic web-based social networks // Lecture Notes in Computer Science - 2004 - January - Vol 3257 — P 116-131

[9j Kamvar S D, Schlosser M T, Garcia-Molma H The eigentrust algorithm for reputation management in p2p networks // WWW '03 Proceedings of the 12th international conference oil World Wide Web - New York, NY, USA ACM Press, 2003 - P 640-651 http //poital acm org/citation cfm?id—775242

[10] Marti S, Garcia-Mohna II Taxonomy of trust Categorizing p2p reputation systems // Computer Networks —2006 —March — Vol 50, no 4 - P 472-184

[11] Massa P , Avesam P Controversial users demand local trust metrics An experimental study on epmions com community // Proc of

Twentieth National Conference 011 Aitifiual Intelligence (AAAI-05), Pittsburgh, Pennsylvania- 2005 - P 121-126 http //dblp um-tner de/dl>/conf/aaai/aaai2005 html#MassaA05

[12] Odlyzko A Tiagic loss or good riddance? the impending demise of traditional scholaily journals // Inttm J Human-Computer Studies — 1995 - P 71-122

[Id] Personalized reputation management m p2p networks / P-A Chirita, W Nejdl, M T Schlosser, O Scurtu // ISWC Workshop on Trust, Secunty, and Reputation on the Semantic Web / Ed by J Golbeck, P A Bonatti, W Nejdl et al - Vol 127 of CEUR Workshop Piocealmgs - CEUR-WS org, 2001 hltp//dblp umtrier de/db/couf/semweb/iswc2001trust html#ChintaNSSO 1

|14] Price D J The exponential curve of science // Discovery — 1956 —■ P 240-243

[15] Rahman A A The pgp trust model // EDI-Foium The Journal of Electronic Commerce — 1997 — April

[16[ Reputation systems / P Resmck, K Kuwabara, R Zeckhauser, E Friedman // Commun ACM- 2000 —December — Vol 43, no 12 -P 45-48 http//dx doi org/10 1145/355112 355122

[17] Richardson M, Agtawal R, Domingos P Trust management for the semantic web // Lecture Notes in Computer Science — 2003 -January — Vol 2870 -P 351-368

0 Введение

0.1 Информационный взрыв.

0.2 Открытость и контроль.

0.3 Цели работы.

0.4 Основные методы.

0.5 Основные результаты.

0.6 Структура и содержание диссертации.

0.7 Апробация и публикации.

0.7.1 Апробация.

0.7.2 Список публикаций.

1 Обзор существующих подходов

1.1 Открытость и контроль: примеры из истории.

1.1.1 Пример: потери в ВОВ.

1.1.2 Пример: Википедия и Британника

1.1.3 Пример: история WWW.

1.1.4 Пример: WWW и поисковые машины.

1.2 О современной технологии доверия.

1.2.1 Проблема: сигнал/шум.

1.2.2 Проблема: дублирование усилий.

1.2.3 Проблема: фрагментация.

1.3 Ранее предложенные решения.

1.4 Модели доверия/репутации.

1.4.1 Действующие модели.

1.4.2 Теоретические модели.

1.5 Рекомендующие системы.

1.6 Социальные сети.

1.7 Р2Р.

1.8 Репутационные механизмы в Р2Р сетях.

1.9 Топология социальных сетей

1.9.1 Безмасштабный (scale-free) граф.

1.9.2 Мир тесен.

1.9.3 Уязвимость безмасштабных сетей.

1.9.4 Маршрутизация в безмасштабных сетях, скелет сети

1.9.5 Распространение информации в безмасштабных сетях . . 42 1.10 Степенные распределения (power-law).

2 Топологические вопросы

2.1 Степенной разлом.

2.1.1 Степенной разлом и поиск путей в графе

2.1.2 Теорема о достижимости.

2.1.3 Степенной разлом и IPv4.

2.1.4 Форсирование экспоненциального роста.

2.2 Маршрутизация.

2.2.1 Имена как инструмент разлома.

2.2.2 Алгоритм.

2.2.3 Результаты.

2.3 Модель издержек коммуникации

2.4 Необходимое (глобальное) покрытие

2.5 Сравнение: PageRank и "просачивание".

3 Репутационная модель

3.1 Репутация.

3.1.1 Простая репутационная аксиоматика.

3.1.2 Почему не вероятности?

3.2 Обобщенная (рефлексивная) аксиоматика мнений.

3.2.1 Формальное и нечеткое.

3.2.2 Мера схожести.

3.3 Рефлексивные множества.

3.3.1 Мера схожести в рефлексивных множествах.

3.3.2 Геометрическая интерпретация

3.4 Многоуровневая модель.

3.4.1 Уровни.

3.4.2 Ожидание.

0.1 Информационный взрыв Информационный взрыв - естественное состояние информационной среды. ВXV веке информационный взрыв был вызван изобретением книгопечатания[16], в XVII веке появлением газет, в XIX веке - изобретением телеграфа, впервые промьппленно передававшего информацию со световой скоростью. В 50-хмного говорилось об информационном взрыве в связи с экспоненциальным ростом количества научных публикаций. Как пишут А. Одлыжко [62], а ранее- Д. Прайс [68], последние два века скорость появления новых научных работудваивается каждые 10-15 лет. Прямое следствие экспоненциального характера роста - то, что около половины всех научных работ издано в последние 10 лет. В 90-х информационный взрыв ассоциировался с распространением WWW. Для Всемирной Паутины также отмечен экспоненциальный роет[59, 41]. Экспоненциально растут вaJЮвoй траффик в интернете [63] и количество страниц в Википедии [58] и т.д.В каждый период этого информационного взрыва вырабатывались своисредства упорядочения и обработки информации. Газеты, журналы, редакторы, рецензии, библиотековедение, каталоги и рубрикаторы и т.д., и т.п. Вполном согласии с логикой экспоненциального развития довольно большое количество новых подходов возникло лишь в последние десять-двадцать лет.Самое старое из таких новейших средств - гипертекст Всемирной Паутины,затем идут поисковые машины, совместное фильтрование и рекомендующиесистемы, последнее модное средство - онлайновые социальные сети.Гипертекст внес такие новшества, как легкая и моментальная публикацияматериала, легкое и моментальное его получение, а также ссылки, объединяюпще отдельные страницы в одну обшую сеть. Поисковые машины (и Google,сегодняшний лидер, в частности), позволили еш,е более легкий поиск материала. Следующий шаг в облегчении поиска - технологии совместного фильтрования (collaborative filtering), подразумеваюпще объединение усилий большогоколичества людей через доведение до конкретного пользователя мнений схожих с ним пользователей. Например, в интернет-магазине, основываясь насодержимом вашей покупательской корзины, рекомендующая система может"вспомнить" тех, кто покупал то же, что и Вы, и посоветовать Вам те товары,которые они купили, а Вы еще нет (см. Разд. 1.5). Использование социальныхсетей в целях совместной обработки информации подразумевает, что существующее либо специально сформированные сощальные связи используютсядля совместного аннотирования и тэгирования (помечивания), решения вопросов бизнеса, найма, знакомств, обсуждения профессиональных вопросов ипросто тусовки. На настоящий момент наблюдается бум онлайновых сощальных служб: Linkedin, Priendster, Flickr, MySpace, LiveJournal, Yahoo MyWebи многие, многие другие. Подробней эта тема рассмотрена в Разд. 1.6. Легкозаметить, что все рассмотренные технологии имеют своей целью более эффективное накопление, поиск, доставку, в общем - обработку информации.Волее общий подход, применяемый в некоторых вышеперечисленных типахсистем - доверие и репутация. В последние годы многие онлайновые службы успешно использзтот различные репутационные модели. Например, оригинальной особенностью Google, а теперь и всех поисковых машин, являетсяприменение репутационной модели PageRank, которая сродни ранее применявшемуся в бумажной цериодике академическому индексу цитирования. В числепионеров числятся также еВау и Epinions, см. Разд. 1.4. Сегодня тематике доверия и репутации посвящено огромное количество работ (см. Разд. 1.4.2) - и скаждым годом это количество стремительно (по-видимому, экспоненциально)увеличивается.Еще один интересный технологический подход, используемый на сегоднядля обработки больших объемов информации - это peer-to-peer сети и протоколы. Под "информацией" в данном случае подразумеваются байты и гигабайты,большие мультимедийный файлы и т.п. В Р2Р сетях разделение на серверы иклиентов отсзггствует - в отличие, например, от Всемирной Сети и протоколаHTTP или протокола FTP. Участники в таких сетях равны (потому и называются peers, т.е. "равные") и нагрузка раскладывается по возможности поровну.Подробней о Р2Р технологиях написано в Разделе 1.7.Топология сетей обмена информацией и математическое ош1сание происходящих в них процессов заинтересовали множество исследователей и практиков. В числе достижений последних лет можно указать на теорию безмасштабных (scale-free) графов (см. Разд. 1.9.1), а также на новые результаты иприложения степенных распределений (Парето, Ципфа - т.н. "длинный хвост",см. Разд. 1.10).Для всех информационных сред, включая вышеперечисленные, характерна проблема масштабирования - грубо говоря, хорошо организованные средымалы, а большие среды хуже организованы. В этой работе проблема масштабирования будет исследоваться в ключе наилучшего совмеш,ения открытостии контроля в информационной среде, подразумевая под этим как легкостьрасширения (пополнения) информационной среды с одной стороны, так и контроль качества и поддержание порядка с другой.0.2 Открытость и контрольИмеется обширное поле информационных сред, полезная нагрузка которыхсводится к обмену информацией и мнениями: многочисленные сайты, портвглы, форумы, списки рассылок, блоги, конференции Usenet и т.д. и т.п. А еслисмотреть шире, то также и газеты, журналы, книги, разговоры, танец пчел. Вто время как обш;ее назначение этих сред весьма схоже, конкретные технологии и процессы весьма различны. Для этих сред, а также и для этой работы,центральными являются два вопроса:• Открытость - простота и дешевизна внесения нового содержимого, доведения его до адресата• Контроль - поддержание качества содержимого, удаление мусора, отсев,поддержание порядкаВ различных подходах наблюдается различный баланс между открытостьюи контролем. Например, в печатных издани5гх и на традиционных тематических сайтах есть некоторый редакционный процесс, в ходе которого решениео публикации принимает редактор. Упрощенный вариант - премодерация, когда редактор-модератор может либо принять, либо отклонить готовый текст.Более открытые решения - списки рассылки, форумы, где модератор можетлишь апостериорно вмешаться в процесс, удаляя откровенно несоответствующие сообщения (спам, ругань и т.п.). Существует ряд решений, где модерациюосуществляют сами пользователи (напр. Slashdot, см. Разд. 1.4.1). В системахwiki и конкретно в Википедии модерация осуществляется с помои^ью автоматически действзтощих правил, редакторами же и авторами выступают пользователи.Если обратиться к более архаичным средствам обработки информации, томы также обнаружим механизмы, описываемые в понятиях открытости и контроля. Например, переход от пергамента к бумаге и изобретение печатногостанка безусловно повысили открытость, а Дж. Бруно и Г. Галилей попалипод жернова контроля.10Для разных уровней баланса открытость-контроль характерны разные проблемы. Из того, что лежит на поверхности: более закрытые среды хуже масштабируются и медленней развиваются. Более открытые, очевидно, сильнеезасоряются - вплоть до потери практической полезности. По-видимому, эталоном бесполезности является наиболее закрытая и неконтролируемая информационная среда.Отсутствие контроля однозначно способствует открытости, а закрытость- один из механизмов контроля. Может показаться, что усиление контроляоднозначно ведет к закрытости, а открытость - синоним бесконтрольности.По мнению автора, это не так. Открытость и контроль не являются противоположными полюсами; есть не только выбор баланса между открытостьюи контролем, но и проблема совмещенуя открытости и контроля. Развитыеинформационные системы как раз отличаются большей степенью совмещенияоткрытости и контроля - тем же образом, каким демократия отличается отанархии. Безусловно, понятия открытости и контроля - очень общие и, чтобы лучше понять эту концепцию, полезно было бы рассмотреть некоторыепримеры. В Разд. 1.1 рассматривается несколько случаев эволюции информационных сред и траектория, которую они при этом описали в координатахоткрытость-контроль.0.3 Цели работыЦель данной работы - разработать более развитую технологию доверия дляоткрытой сети, нежели домены физического контроля. Систему предполагается построить на репутационных принципах, не требующих человеческогоучастия (административного вмешательства) в штатных ситуациях. Цельюявляется система, в которой любое сообщение взвешено мерой доверия/ репутации/ ответственности/ релевантности. Такая система должна позволитьперешагнуть границу собственного домена контроля, как экспортируя, так иимпортируя мнения, а не тексты. Таким образом, степень доверия любой информации, в т.ч. и производной (доверии информации о доверии), должнауказываться явно и обрабатываться автоматически.Итак, основной целью данной работы является разработка методов прямого учета и выражения мнений (доверия, репутации и релевантности) в Сети,реализацию рапределенных систем поиска, обмена и публикации информации,позволяющих решить проблему контроля качества содержимого информационной среды с минимальным ущемлением ее открытости.Требуемая среда должна удовлетворять требованиям легкости внесениясодержимого, легкости доведения его до читателя (потребителя), что такжевключает поиск, надежности фиксирования (сохранения) содержимого, а так11же отсева мусора.0.4 Основные методыИспользование репутационных механизмов предполагает, что каждое сообщение будет передаваться только от известных и доверенных лиц, только известным и доверенным лицам. А поскольку возможности каждого узла по поддержанию связей и отслеживанию поведения {репутаищи) других узлов ограничены, неизбежно придется эксплуатировать некоторую социальную сеть, черезкоторую мы будем передавать как информацию вообще, так и репутационную (мета)информацию. Это тем злободневней, если мы з^тем все современные проблемы распределенных Р2Р-систем, связанные с технологиями доверия (главным образом, спам, конечно), а также вынужденный олигополизмрынка социальных служб, вызванный, в основном, технологической необходимостью централизации данных.Опора на сощальные сети, образуемые отношениями доверия (web-of-trnst),делает проблему маршрутизации одной из ключевых для предполагаемой системы: неизбежно возникает вопрос вычисления цепочек поручителей, дажеесли бы мы использовали централизованное, а не Р2Р решение. Этот вопросможет быть решен либо передачей сообщений по цепочке, когда каждый следуюпщй y^ iacTHHK подправляет значение репутационного расстояния, либо это- вопрос маршрутизации, т.е. когда получено сообщение и возникает проблема вычисления цепочки рекомендателей до отправителя. В любом случае, длятаких задач первостепенное значение имеет топология социальных сетей, вопросы маршрутизапри и распространения сигнала в таких сетях, и прочиеподобные вопросы, см. Гл. 2.Возможность передачи по цепочке соответствует групповым средствам коммуникации, когда сообщения публичны (форумы, списки рассылки, блоги,Usenet - то, что также называется тапу2шапу). Соответственно, в персональных коммуникациях (e-mail) передача по цепочке если и не исключена, тосвязана с неоправданными трудностями. Поэтому наша основная задача разделяется на две - основанные на репутации и доверии среды для групповыхи персональных коммуникаций.В случае групповых коммуникаций практической целью работы будет среда распределенного социального редактируемого гипертекста Бульон (также"социальное Р2Р wiki", см. Гл. 4). Участниками этой среды и источникамимнений будут люди, пользователи, поскольку, в отсутствие ИскусственногоИнтеллекта, только люди могут проделать необходимую когнитивную работу.Теория такого механизма с точки зрения репутационных метрик изложена ваксиоматической части под названием горизонтальной модели, см. Разд. 3.5.2.12В случае персональных коммуникаций, будет предложен новый проторепутационный механизм общих белых списков P2PWL (см. Гл. 5), дополняющиймеханизмы черных и серых списков. В данном случая, по некоторым соображениям, участниками будут SMTP-сервера. Соображения заключаются втом, что электронная почта чрезвычайно популярна и широко распространена. Поэтому, будет сделан максимальный упор на обратную совместимость, аиспользуемые данные будут иметь сугубо технический характер. Теория этого механизма изложена в аксиоматической части под названием диагональноймодели, см. Разд. 3.5.1.Итак, цели предполагается достичь с помощью репутационных и рекомендационных, социальных механизмов. Сначала, исходя из некоторых, частьютривиальных, частью идеалистических соображений, разрабатывается полностью персонализованная репутационная аксиоматика (2004-2005 гг). Затем, отталкиваясь от сложностных соображений и топологических особенностей целевого семейства графов, разрабатываются полностью децентрализованные алгоритмы, реализующие принципы репутационных вычислений применительнок информационным средам (2005 г). На основе алгоритмов создаются программы, имеющие пользовательскую ценность (2005-2006 гг).0.5 Основные результаты• Репутационная аксиоматика, построенная на основе нечетких множеств.Основное достоинство аксиоматики - простота и непротиворечивость, атакже достаточная выразительность для работы с целевыми понятиями- репутащей и рекомендациями.• Сеть Бульон: архитектура, алгоритмы и программное обеспечение. Полученные результаты позволяют надеяться на создание информационнойсреды, более совершенной в отношении совмещения открытости и контроля, нежели ньше существ)тощие, а также, что среда Бульон способна к неограниченному масштабированию (росту). В плане используемыхалгоритмов Бульон - проект совершенно новаторский, и, насколько мнеизвестно, первый, обеспечивающий распределенное хранение и редактирование страниц.• Репутациопная система P2PWL (общие белые списки для SMTP). Также,архитектура, алгоритмы и программное обеспечение. Обище белые списки дополняют семейство проторепутационных инструментов, используемых на почтовых серверах, а именно обпще черные (DNS BL) и местныесерые списки. Общие белые списки призваны исключить основной недостаток серых списков - задержку писем от добросовестных отправите13лей. Полученные в данной работе результаты позволяют надеться, что вперспективе возможно объединить в подобие социальной сети и, такимобразом, учесть все добросовестные почтовые серверы, а значит - четкоотделить их от машин-зомби, ответственных за рассылку подавляющеймассы современного спама.0.6 Структура и содержание диссертацииДиссертация состоит из введения, пяти глав, заключения, приложения и списка литературы. Главы обозначены номерами и разбиты на разделы и подразделы. Разделы пронумерованы в пределах главы, подразделы - в пределахраздела. Вкратце, содержание глав таково.В главе "Обзор существующих подходов" рассматриваются современные достижения в областях, имеющих отношение к теме данной работы: социальных сетях, рекомендуюшзих системах, моделях доверия и репз^гации, Р2Рсетях в целом и репутационных системах для Р2Р-сетей. Иллюстрируютсяпрактическими примерами введенные ранее концепции открытости и контроля. Рассматриваются недостатки современных технологий доверия, основанных на доменах физического контроля.В главе "Топологические вопросы" рассматривается ряд топологических и сложностных вопросов, связанных с сетями обмена информацией. Вчастности, рассматриваются особенности топологии социальных сетей, а именно - безмасштабной (scale-free) топологии. Выделяется типовой подход к решению некоторых задач на графах, названный "степенной разлом". Исследуютсяпути к решению задач сложностного и топологического характера, связанныхс реализацией метрик репутации на безмасштабных графах - в основном, этозадачи о маршрутизации и распространении информации.Первый результат главы заключается в том, что в распределенных одноранговых {Р2Р) средах метрики репутации, основанные на цепочках поручителей, рассчитываются, самое большее, с сублинейными затратами на узелотносительно размера системы, а значит, практически применимы. Этот результат относится к системе P2PWL (см. ниже). В контексте безмасштабныхсетей вообще, данный подход является оригинальной схемой маршрутизации,использующей метки малого-сублинейного размера и дающей сублинейнуювычислительную нагрузку на узел для задачи о кратчайших путях.Второй результат заключается в том, что в социальных сетях с их безмасштабной топологией система Вульон (см. ниже) будет эффективна относительно таких параметров, как скорость распространения сообщения и затраты наглобальное распространение сообщения. Более детальное рассмотрение ресурсоемкости алгоритмов Вульон производится в Разд. 4.4. Также получен один14вспомогательный результат для Р2Р сетей вообще, а именно, что локализэ/ция траффика чрезвычайно эффективна, с точки зрения нагрузки на сетевуюинфраструктуру.В главе "Репутационная модель" предлагается репутационная аксиоматика, основанная на теории нечетких множеств. На основе аксиоматикипредлагаются две модели работы с сообщениями: модель групповых коммуникаций ("горизонтальная", соответствует таким средам, как Usenet, спискирассылок, форумы) и модель персональных коммуникаций ("диагональная",соответствует e-mail). На этих двух моделях основаны программы, предложенные в следующих двух главах.Глава "Групповые коммуникации" посвящена проекту "Бульон", реализующему горизонтальную модель. Бульон имеет целью создание среды групповых коммуникаций, в наибольшей степени сочетающей принципы открытостии контроля. Достоинства сети Бульон в том, что, хотя и каждый пользовательи может править любую из страниц (в отличие от WWW), но злоумышленник не может написать что-то не-релевантное для кого-то кроме своих друзей.В то же время, ценные правки могут распространиться на глобальную аудиторию очень быстро. С технической точки зрения. Бульон - это Р2Р wiki,работающее в социальной сети, где содержимое распространяется вдоль социальных связей с помощью рекомендаций. С пользовательской точки зрения.Бульон - гибрид браузера, текстового процессора и интернет-пейджера, позволяющий как просмотр, так и редактирование содержимого сети Бульон врежиме почти-реального времени. Среда Бульон - нечто абсолютно новое икардинально отличающееся даже от ранее известных сред Р2Р публикации(напр. Freenet) - в том числе, и по широте возможностей.В главе "Персональные комммуникации" рассказывается про антиспамовую технологию P2PWL. Это - инструмент для обмена автоматическисоздаваемыми белыми списками между SMTP-серверами. P2PWL являетсявспомогательным инструментом к антиспамовой системе серых списков, исключающим главный ее недостаток - задержки писем - в подавляющем большинстве случаев. Б перспективе, P2PWL реализует диагональную модель.В главе "Результаты и выводы" подводятся итоги работы, рассказывается о текущем статусе проектов и их практическом использовании.В приложении А детализируется вычислительный эксперимент по маршрутизации на безмасштабном графе с использованием имен малого сублинейногоразмера, описываемый в Разд. 2.2.1.150.7 Апробация и публикации0.7.1 АпробацияПервоначальные результаты работы по модели доверия, построенной на нечетких множествах (Разд. 3.1.1), докладывались на FOAF 2004 в Голуэе, Ирландия. Результаты по схеме маршрутизации с топонимами (Разд. 2.2) докладывались на SECURECOMM 2005 в Афинах, Греция. Также, статья по моделидоверия была принята на International Semantic Web Conference 2004 в Хиросиме, Япония, где автор не смог присутствовать. Была опубликована статья помаршрутизации в безмасштабных графах и реализации диагональной моделив International Jomrnal for Metadata and Semantic Organizations в 2006. Статья о системе Бульон версии 1 (см. Гл. 4) была принята на World Wide WebConference 2006 в Эдинбурге, Шотландия, где автор не мог присутствовать.Статья по расширенной модели доверия (см. Гл. 3), диагональной и горизонтальной моделям транзитивного доверия (см. Разд. 3.4, 3.5) была опубликована в Известиях УрГУ в 2006.0.7.2 Список публикаций1. В. Грищенко. Исчисление мнений // Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. 2006. №43. 139-153. [111]2. В. Гриш;енко. Некоторые новые подходы к маршрутизации в Интернете /1 Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. 2006. №43. 198. [ИЗ]3. В. Гршценко Метрики репутации и борьба за релевантность // Материалы Международной научно-практической конференции студентов, аспирантов и молодых ученых "Безопасность информационного пространства".Изд-во УрГУПС: Екатеринбург, 2006. 89. [112]4. В. Грищенко Черви Уорхола и модульные черви: перспективы эпидемий в Интернет // Труды XXIV конференции молодых ученых механикоматематического факультета МГУ им. М. В. Ломоносова, Т. I. Изд-во МГУ:Москва, 2002. 62-64. [110]5. V. S. Grishchenko. Redefining web-of-trust: reputation, recommendations,responsibility and trust among peers // Proceedings of the First Workshop onFriend of a FViend, Social Networking and the Semantic Web. National Universityof Ireland, Calway. 2004. P. 75-84. [37]166. V. S. Grishchenko. A fuzzy model for context-dependent reputation //Proceedings of the International Semantic Web Conference 2004 Workshop onTrust, Security, and Reputation on the Semantic Web. Hiroshima, 2004. (Электронное издание CEUR Workshop Proceedings, ISSN 1613-0073, Vol 127) [36]7. V. S. Grishchenko. Computational complexity of one reputation metric 11Proceedings of IEEE/Create-Net SecureComm 2005 Workshops. SECOVALWorkshop. Athens, 2005. (Электронное издание, ISBN 0-7803-9469-0.) [38]8. V. S. Grishchenko. Distance-based reputation metrics are practical in p2penvironments // International Journal of Metadata, Semantics and Ontologies.2006. Vol. 1, №2. P. 133-140. [39]17

4.7 Выводы

Итак, решая задачу о групповых коммуникациях, мы получили вполне работающее социальное Р2Р wiki. Данное wiki имеет открытость, превосходящую современные серверные wiki (в т.ч. Wikipedia). В то же время, присутствуют весьма мощные механизмы контроля. Насколько эти возможности будут востребованы рынком - интересный вопрос. Этот вопрос во многом зависит от другого вопроса - как скоро и в какой потолок роста упрется Википедия. Когда, например, добавление нового материала уравновесится порчей старого, либо скорость обновления материала в Wikipedia не будет поспевать за изменениями в предметной области. Уже сейчас слышны жалобы на то, что механизмы Википедии не справляются с наплывом некомпетентных пользователей, а пользователи компетентные порой не готовы биться за качество материала непонятно с кем. Другой путь выхода на рынок заключается в поиске ниш, сейчас не занятых.

В целом же, Бульон, как технология - безусловно, новое слово в области Р2Р публикации. До сих пор, заметным явлением в этой области был лишь FreeNet [32] со всеми его ограничениями. Ныне популярные DHT сети, по-видимому, не могут использоваться для Р2Р публикации из-за проблем с честным использованием (fair use) - пользователь не имеет контроля либо права выбора - что хранить, а что не хранить, что порождает возможность злоупотреблений.

В заключение, один очень интересный факт. В качестве имевших место par нее обращений к подобным же архитектурным принципам следует упомянуть проект Folk Memory [25] изобретателя wiki Варда Каннингэма. Хотя проект так и не пошел дальше общего замысла, как это ни странно, большинство принципов устройства Folk Memory присутствуют в Бульон.

Глава 5

Персональные коммуникации.

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

Репутационная модель прикладывается к электронной почте (e-mail) - наиболее популярному сегодня средству персональной коммуникации.

5.1 Черные, белые и серые списки

Среди различных методов борьбы со спамом есть такие примитивные репута-ционные механизмы, как белые и черные списки. Белый список включает тех МТА (mail transfer agent, грубо - почтовый сервер), которым администратор данного сервера полностью доверяет и чьи письма будут всегда приняты. Черные списки представляют из себя, по сути, базы данных по "засветившимся" рассылыцикам спама с доступом по протоколу DNS (DNS BL, они же RBL). Механизмы включения в черный список на разных RBL-серверах могут быть различными - жалобы от пользователей, попытка передачи письма на адрес-ловушку, принадлежность сети к пулам динамических адресов провайдеров широкополосного доступа и т.д. Черный список позволяет не принимать письма от заведомых спаммеров.

Особое место занимает такой гибридный механизм, как серые списки. Суть этого решения в том, что МТА-получатель не принимает сразу письма от незнакомых серверов, а возвращает временную ошибку (transient error), смысл - сейчас письмо принято быть не может, попробуйте передать позже. В классическом варианте [40] серых списков, ошибка выдается для каждой ранее не встечавшейся тройки (МТА-отправитель, адрес отправителя, адрес получателя). МТА, действующие согласно стандарта SMTP [76] должны повторить попытку передачи через некоторое время. ПО, используемое спаммерами, как правило, не обладает такими возможностями. Кроме того, за время ожидания (от нескольких минут до часа) компьютер-спаммер может попасть в списки черные - и его письма будут отклоняться безусловно. На настоящий момент (апрель 2006) серые списки обеспечивают очень хорошую эффективность, отсеивая более 95% спама. Недостатком серых списков является то, что вполне желательная почта порой опаздывает на время от десяти минут до нескольких часов, поскольку время, через которое МТА должен попробовать повторную передачу жестко не регламентировано.

Сумеют ли спаммеры в массе своей найти средство против серых списков

- пока неясно; на сегодня этот инструмент весьма эффективен. По-видимому, здесь ключевое значение имеет соотношение задержки серых списков tg и характерного времени попадания спамера в черный список Маленькая задержка tg -С U позволяет спаммеру вскорости передать письмо повторно; большая задержка tg Ц передачу спама чрезвычайно затрудняет, однако может надолго задержать получение хорошего письма, а в очень редких случаях даже привести к потере корреспонденции.

Тем не менее, на сегодняшний день разумное применение серых списков позволяет снизить количество получаемого спама до вполне приемлемых величин - 1 письма в день и менее (личный опыт автора).

5.2 Общие белые списки

В данной работе предлагается создать механизм автоматического составления белых списков известных, зарекомендовавших себя МТА, который, с одной стороны, позволял бы устранить задержки в большинстве случаев, с другой

- использовать большие номинальные задержки, tg > tb - для тех, кто в белый список не входит. Подразумевается возможность обмена автоматически составленными белыми списками между разными МТА. В идеале, принимающий МТА должен иметь возможность при получении письма найти цепочку рекомендателей до передающего МТА, что позволит принимать письма от мало-мальски зарекомендовавших себя МТА без задержки, остальным же будет назначена брутальная задержка по серым спискам (скажем, 1 час или более), которая позволит поместить спаммера в черный список раньше, чем он разошлет существенное количество писем. Вновь созданный МТА будет вынужден, таким образом, зарабатывать себе репутацию, чтобы передавать письма без задержек.

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

5.2.1 Этап I: плоские списки goodmtal.senderA.dom[ll.22.33.44] goodmtaZ.senderB.dom[ZZ.33.44.55]

Рис. 5.1: Этап I. Используемый формат данных крайне прост - это просто список IP-адресов МТА, которые хорошо себя зарекомендовали.

Первый этап; в работу вовлекается лишь техническая информация. Белые списки отвечают на вопрос, является ли данный МТА соответствующим RFC, а именно - производит ли он повторную передачу. Первичная информация собирается из логов почтового сервера либо из иным образом полученной истории транзакций. Те МТА, что преодолели серые списки и появлялись достаточное количество раз в течение некоторого промежутка времени - заносятся в белый список. Практический эффект близок к серым спискам, однако базовый критерий, помимо прохождения серых списков, включает известность в течение некоторого времени, т.е. простейший вариант "технической" репутации. Между отдельными МТА налаживается обмен такими списками, список серверов для обмена списками определяется вручную.

Следует заметить, что механизм (не-общих) автоматических белых списков не является новым и используется в ряде реализаций серых списков (напр., postgrey [67]).

5.2.2 Этап II: транзитивные списки

Шаг к диагональной модели - введение транзитивного распространения информации о SMTP серверах. МТА включает в свой публичный белый список не только тех, кого знает, как соответствующих RFC, но и тех, кого они рекомендуют - и этот процесс рекурсивен. good-mtal.senderA.dom[ll.22.33.44] good-mta2.senderB.dom[22.33.44.55] good- recommender. senderC. dotn [33.44.55.66] good-recommended-mtal.s ende rD.dom[44.55.66.77] good-recommended-mta2.senderE.dom[55.66.77.88]

Рис. 5.2: Этап II. В собственный список рекомендованных МТА включаются такие же списки доверенных МТА. Т.е. информация о зарекомендовавшем себя SMTP-сервере начинает распространяться по "социальной сети" SMTP-серверов.

5.2.3 Этап III: диагональная модель good-mtal. senderA. dom[U. 22.33.44] 1.0 good-mta2.senderB.dom[22.33.44.55] 0.98 good-recommender.senderC.dom[33.44.55.66] 1.0 0.95 0.7 good-recommended-mtal.senderD.dom[44.55.66.77] 1.0 0.82 recd-by-recd-mta.senderF.dom[66.77.88.99] 0.92 good-recommended-mta2.senderE.dom[55.66.77.88] 0.93

Рис. 5.3: Этап III. Полная реализация диагональной модели, г-тая колонка соответствует р^%\х) сервера.

Третий этап предполагает вовлечение анализа содержимого писем - либо информации от Байесовских анализаторов, либо (что лучше) непосредственно пользовательских отзывов. Это позволит создать уже полноценную реализацию диагональной модели. Также, от проверки соответствия поведения МТА стандартам, которая является лишь косвенным признаком спамно-сти/неспамности, происходит переход непосредственно к использованию пользовательского мнения.

Наличие р^ позволяет от ручного указания серверов - рекомендателей перейти к их автоматическому подбору на основе их репутации. Например, начинать использовать белые списки тех МТА, которые уже известны, как хорошие отправители. Или же наоборот, отказываться от списков, благодаря которым на сервер был передан спам.

Для вычисления цепочки рекомендателей, что, заметим, является родом задачи о маршрутизации, применим степенной разлом. А именно, МТА-отправитель (SMTP-клиент) может представить получателю список своих рекомендателей, так что получателю необходимо найти цепочку поручителей лишь до любого из них. Таким образом, многоуровневый список рекомендателей представляет из себя топоним, как описано в Разд. 2.2.1.

Многоуровневые белые списки другого МТА, например peer.dom, доступны, как http://peer.dom:24024/whitelist. Списки рекомендателей этого же сервера доступны, как http://sender.dom:24024/recommenders.

Рассмотрим, как в таком случае будет выглядеть процесс передачи письма.

1. МТА-отправитель, sender.dom, связывается с МТА-получателем, recipient.dom, по протоколу SMTP.

2. Если отправитель находится в черных списках - почта отклоняется.

3. Если отправитель был известен ранее (не раз передавал письма), почта принимается.

4. Если отправитель был известен одному из доверенных МТА МТА-получателя, от которых МТА-получатель принимает их белые списки, то почта также принимается.

5. Затем получатель устанавливает, поддерживает ли отправитель репута-ционный механизм - а именно, пытается получить список рекомендателей http://sender.dom:24024/recommenders. В случае, если среди рекомендателей есть некто, чьим советам получатель доверяет, то получатель проверяет ту часть цепочки, которая не хранится локально и, в случае положительного результата, принимает письмо.

6. В остальных случаях почта подвергается задержке (4хх - временная ошибка) на значительный период времени.

5.3 Вычислительная сложность

Возникает вопрос об ориентировочной величине списков рекомендованных и рекомендателей, необходимых для полного счастья, а именно - для установления цепочек доверия для большинства пар "правильных" МТА. Предполагая power-law топологию контактов МТА и исходя из прежних результатов автора ([38], Разд. 2.2) можно определить величину таких списков, как сублинейную относительно общего количества МТА. (Принимая топологию, как случайную, получим также сублинейный порядок обоих списков, однако следующее допущение в таком случае будет некорректно.) Из соображений минимизации издержек и увеличения времени отклика логично иметь большие списки рекомендованных и маленькие - рекомендателей. Следуя соображениям Гл. 2 можно ожидать, что достаточные списки рекомендателей, за счет определяющей роли хабов, будут относительно малы (напр., 0(№"2), а не 0(№ 5)). В таком случае, списки рекомендателей можно интерпретировать, как "имена" в терминах Разд. 2.2. Принимая во внимание, что количество МТА в мире невелико (вероятно, миллионы) относительно количества пользователей и сайтов, размер списков рекомендованных МТА, оцениваемый грубо, как 0{\/N), будет иметь порядок десятков тысяч записей (сотен килобайт), что абсолютно необременительно с точки зрения объема хранения, потребляемой пропускной способности и т.д. Скажем прямо, необходимая здесь к использованию операция поиска в отсортированном списке имеет логарифмическую сложность, а потому, список даже из миллиона серверов не представил бы чрезмерных затруднений в плане вычислительной сложности и эксплуатации. Другой вопрос, что составление и поддержание такого списка - принципиально более сложная задача, с которой, в теории, и должна справиться репутационная модель и социальные сети.

Глава 6

Результаты и выводы

Разработана репутационная аксиоматика, обладающая рядом достоинств. Цель репутационного механизма - решить Дилемму Узника, поощрять долговременные взаимовыгодные отношения и предотвращать Трагедию Общин. На базе аксиоматики, состоящей из определения и простой гипотезы, построены две модели информационных пространств со встроенными метриками репутаг ции - "горизонтальная" (тапу2шапу) и "диагональная" (опе2опе).

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

Разработан протокол ос-со для социальной одноранговой сети обработки произвольного XML, реализующей горизонтальную модель. Разработано ПО, использующее протокол ос-со для поддержки однорангового (Р2Р) распределенного wiki - система Бульон.

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

На сегодняшний день (сентябрь 2006) ситуация с этими двумя проектами такова. Бульон существует в виде работающего прототипа (Глава 4 была первоначально набрана в нем), однако пользователей в этой сети пока нет. Идет поиск приложений, в которых данная технология давала бы наибольшие выгоды - т.е., рыночной ниши. Учитывая, что распространение новых технологий подобного рода обычно занимает около 10 лет (как, например, wiki и блоги), в исключительных случаях - около 5 лет (как WWW), можно предположить, что впереди масса работы.

P2PWL реализовано в объеме этапа 1 и может быть полезно, в основном, в двух случаях: для сбоеустойчивого обмена белыми списками между основным

MX и дублером (локальный вариант), а также для обмена белыми списками внутри локальных клик SMTP-серверов ("локальных" в глобальном масштабе). На сегодня в Екатеринбурге такая клика включает 4 сервера: два сервера провайдеров (УралРелком и СЦК) и два корпоративных.

Резюмируя, обе представленные технологии работают, но насколько они окажутся популярны и полезны - покажет время.

1. Abdul-Rahman A., Hailes S. Using recommendations for managing trust in distributed systems // Proceedings of the IEEE Intl. Conference on Communication, Malaysia. — 1997.

2. Aberer K., Despotovic Z. Managing trust in a peer-2-peer information system // Proceedings of the 10th Intl. Conference on Information and Knowledge Management. — Atlanta, Georgia, USA: 2001.

3. Adar E., Huberman B. A. Free riding on gnutella. — http://www.firstmonday.org/issues/issue510/adax/.

4. Akerlof G. A. The market for "lemons": Quality uncertainty and the market mechanism // The Quarterly Journal of Economics. — 1970.— Vol. 84, no. 3. P. 488-500.

5. Albert R., Jeong #., Barabasi A.-L. Error and attack tolerance of complex networks // Nature. 2000. - no. 406. - P. 378-382.

6. Amaral L. A. N., et al. The web of human sexual contacts // Nature.— 2001,-no. 411.

7. Anderson C. The long tail // Wired. 2006. — May.

8. Avesani P., Massa P., Tiella R. Moleskiing.it: a trust-aware recommender system for ski mountaineering // Journal of Infonomics, Special Issue: Selected papers of the ACM SAC 2005 TRECK. 2005.

9. Barabasi A.-L., Albert R. Emergence of scaling in random networks // Science.- 1999. October. - Vol. 286, no. 5439.- P. 509-512. http://www.sciencemag.org/cgi/content/full/286/5439/509.

10. Berners-Lee T. Realising the full potential of the web.— http://www.w3.org/1998/02/Potential.html.

11. Berners-Lee Т. Transcript of the talk to the lcs 35th anniversary celebrations.- http://www.w3.org/1999/04/13-tbl.html.- 1999.

12. Blaze M., Feigenbaum J., Lacy J. Decentralized trust management // Proc. of IEEE Symposium on Security and Privacy, Oakland, CA. — 1996. — May.

13. Boguna M., Pastor-Satorras R., Vespignani A. Absence of epidemic threshold in scale-free networks with connectivity correlations. — http://www.citebase.org/abstract?id=oai:arXiv.org:cond-mat/0208163. — 2002.

14. Buchegger S., Boudec J.-Y. L. A robust reputation system for p2p and mobile ad-hoc networks // Proceedings of 2nd Workshop on Economics of Peer-to-Peer Systems. — 2004.

15. Buchegger S., Boudec J.-Y. L. A robust reputation system for p2p and mobile ad-hoc networks // Proceedings of the Second Workshop on the Economics of Peer-to-Peer Systems. — 2004. citeseer.ifi.unizh.ch/buchegger04robust.html.

16. Burke P. A Social History of Knowledge: Prom Gutenberg to Diderot.— Polity Press, 2000.

17. Chord: a scalable peer-to-peer lookup protocol for internet applications / I. Stoica, R. Morris, D. Liben-Nowell et al. // IEEE/ACM Trans. Netw.-2003.-Vol. 11, no. l.-P. 17-32.

18. Christianson В., Harbison W. S. Why isn't trust transitive? // Proceedings of the International Workshop on Security Protocols.- London, UK: Springer-Verlag, 1997.- P. 171-176. http://portal.acm.org/citation.cfm?id=647214.720377.

19. Cohen B. Incentives build robustness in bittorrent.— http://www.bittorrent.org/bittorrentecon.pdf.

20. Cohen R., Havlin S. Scale-free networks are ultrasmall // Phys. Rev. Lett. — 2003.-Vol. 90.-P. 058701.

21. Cohen R., Havlin S. Scale-free networks are ultrasmall // Physical Review Letters. 2003. - Vol. 90. - P. 058701.

22. Compact name-independent routing with minimum stretch / I. Abraham, C. Gavoille, D. Malkhi et al. // 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM Press, 2004. - July. - P. 2024.

23. Crespo A., Garcia-Molina H. Semantic overlay networks for p2p systems.— http://www-db.stanford.edu/ crespo/publications/op2p.pdf.

24. Cunningham W. Folk memory: A minimalist architecture for adaptive federation of object servers. — http://c2.com/doc/FolkMemory.pdf.— 1997.

25. Decker S., Frank M. The social semantic desktop: Tech. rep.: DERI, 2004.

26. Document object model (dom).— http://www.w3.org/D0M/.

27. Douceur J. R. The sybil attack // Proc. of the IPTPS02 Workshop, Cambridge, MA (USA).- 2002.

28. Ebel H., Mielsch L.-I., Bornholdt S. Scale-free topology of e-mail networks // Physical Review E. 2002.- Vol. 66, no. 035103(R).

29. Evaluating collaborative filtering recommender systems / J. L. Herlocker, J. A. Konstan, L. G. Terveen, J. T. Riedl // ACM Trans. Inf. Syst. 2004. -Vol. 22, no. l.-P. 5-53.

30. Faloutsos M., Faloutsos P., Faloutsos C. On power-law relationships of the internet topology // SIGCOMM. 1999. - P. 251-262.

31. The free network project. — http://freenetproject.org/.

32. Giles J. Internet encyclopaedias go head to head // Nature. — 2005. — Dec 15.-Vol. 438.-P. 900-901.

33. Golbeck J. Personalizing applications through integration of inferred trust values in semantic web-based social networks // Semantic Network Analysis Workshop at the 4th International Semantic Web Conference.— Galway, Ireland: 2005.

34. Golbeck J., Hendler J. Filmtrust: Movie recommendations using trust in web-based social networks // Proceedings of the IEEE Consumer Communications and Networking Conference. — Las Vegas, Nevada, USA: 2006.— January.

35. Grishchenko V. Computational complexity of one reputation metric // Proceedings of IEEE/Create-Net SecureComm 2005 workshops, Athens, Greece. — (Электронное издание, ISBN 0-7803-9469-0.), 2005.

36. Grishchenko V. Distance-based reputation metrics are practical in p2p environments // International Journal of Metadata, Semantics and Ontologies (IJMSO). 2006. - Vol. 1. - P. 133-140.

37. Harris E. The next step in the spam control war: Greylisting. — http://projects.puremagic.com/greylisting/whitepaper.html. — 2003.

38. Huberman B. A., Adamic L. A. Growth dynamics of the world-wide web // Nature. 1999. - Sep 9. - Vol. 401.

39. Jabber.org load stats. — http://status.jabber.org/.43. JEP-0166: Jingle, 2006.44. john Markoff, Hansell S. Hiding in plain sight, google seeks more power // The New York Times.- 2006.-June 14.

40. Josang A., Keser C., Dimitrakos T. Can we manage trust? // Proceedings of the Third International Conference on Trust Management (iTrust).— Roc-quencourt, France: 2005.

41. Josang A., Pope S. Semantic constraints for trust transitivity // APCCM '05: Proceedings of the 2nd Asia-Pacific conference on Conceptual modelling. — Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2005. P. 59-68.

42. Josang A., Presti S. L. Analysing the relationship between risk and trust // Proceedings of the Second International Conference on Trust Management / Ed. by T. Dimitrakos. Oxford, UK: 2004. —April.

43. Kamvar S. D., Schlosser M., Garcia-Molina H. Incentives for combatting freeriders on p2p networks // Proceedings of Euro-PAR European Conference' on Parallel Computing in Klagenfurt, Austria. — 2003. — August.

44. Kim D.-H., Noh J. D., Jeong H. Scale-free trees: The skeletons of complex networks // Phys. Rev. E. 2004. - Vol. 70.

45. Krioukov D., Fall K., Yang X. Compact routing on internet-like graphs.— 2003.

46. Levien R. Advogato's trust metric.— http://www.advogato.org/trust-metric.html.

47. Marsh S. P. Formalising Trust as a Computational Concept: Ph.D. thesis / Department of Computing Science and Mathematics, University of Stirling. — 1994.

48. Marti S., Garcia-Molina H. Taxonomy of trust: Categorizing p2p reputation systems // Computer Networks. — 2006. — March. — Vol. 50, no. 4. — P. 472484.

49. Massa P. Trust metrics evaluation project.— http://moloko.itc.it/trustmetricswiki/moin.cgi/TrustMetricsEvaluationProject.

50. McAnally D., Josang A. Addition and subtraction of beliefs // Proceedings of the conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU2004), Perugia, Italy. 2004.

51. Modelling wikipedia's growth.— http://en.wikipedia.org/wiki/Wikipedia:-ModellingWikipedia'sgrowth.

52. Netcraft web server survey. — http://www.netcraft.com.

53. Newman M. E. J. Scientific collaboration networks. I. network construction and fundamental results // Phys. Rev. E. — 2001. — Vol. 64, no. 1.

54. Newman M. E. J. Scientific collaboration networks. II. clustering and preferential attachment in growing networks // Phys. Rev. E. — 2001. — Vol. 64, no. 2.

55. Odlyzko A. Tragic loss or good riddance? the impending demise of traditional scholarly journals // Intern. J. Human-Computer Studies. — 1995.— P. 71122.

56. Odlyzko A. M. Internet traffic growth: Sources and implications // Optical Transmission Systems and Equipment for WDM Networking II, Proc. SPIE. 2003. - Vol. 5247. - P. 1-15.

57. Ontology-based search and broadcast in hypercup / M. Schlosser, M. Sintek, S. Decker, W. Nejdl // International Semantic Web Conference, Sardinia, Italy. 2002.

58. The pagerank citation ranking: Bringing order to the web: Tech. rep. / L. Page, S. Brin, R. Motwani, T. Winograd: Stanford Digital Library Technologies Project, 1998.

59. Postgrey postfix greylisting policy server, домашняя страница проекта postgrey (серые списки для postfix).— http://isg.ee.ethz.ch/tools/postgrey/.

60. Price D. J. The exponential curve of science // Discovery. — 1956. — P. 240 -243.

61. Guha R., Kumar R., Raghavan P., Tomkins A. Propagation of trust and distrust. — 2004. http://citeseer.ist.psu.edu/703938.html.

62. Rahman A. A. The pgp trust model // EDI-Forum: The Journal of Electronic Commerce. — 1997. — April.

63. Ramasco J. J., Dorogovtsev S. N., Pastor-Satorras R. Self-organization of collaboration networks // Physical Review E. 2004. - Vol. 70. - P. 036106.

64. Reputation systems / P. Resnick, K. Kuwabara, R. Zeckhauser, E. Friedman // Commun. ACM. 2000. - December. - Vol. 43, no. 12. - P. 45-48. http://dx.doi.org/l0.1145/355112.355122.74. RFC 3920 XMPP Core, 2004.75. RFC 3921 XMPP IM, 2004.

65. RFC2821 Simple Mail Transfer Protocol, 2001.

66. Richardson M., Agrawal R., Domingos P. Trust management for the semantic web // Lecture Notes in Computer Science.— 2003.— January. — Vol. 2870. P. 351-368.

67. Ritter J. Why gnutella can't scale. no, really.— http://www.darkridge.com/ jpr5/doc/gnutella.html.

68. Rowstron A., Druschel P. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems // Lecture Notes in Computer Science.- 2001.- Vol. 2218.- P. 329-?? http://citeseer.ist.psu.edu/620683.html.

69. Selcuk A. A., Uzun E., Pariente M. R. A reputation-based trust management system for p2p networks // 4th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2004), Chicago, USA. 2004.-April.

70. Shirky C. A group is its own worst enemy, http://www.shirky.com/writings/groupenemy.html.

71. Shirky C. Power laws, weblogs, and inequality.— http: / / www.shirky.com / writings/power lawweblog.html.

72. Simulating the Evolution of Language / Ed. by A. Cangelosi, D. Parisi. — Springer Verlag, London, 2001.

73. Skeleton and fractal scaling in complex networks / K.-I. Goh, G. Salvi, B. Kahng, D. Kim // Phys. Rev. Lett.- 2006.- Vol. 96.- P. 018701.

74. Slashdot moderation. — http://slashdot.org/moderation.shtml.

75. The spread of the sapphire/slammer worm.— http: //www.caida.org/publications / papers /2003/ sapphire / sapphire.html. — 2003.

76. Staniford S., Paxson V., Weaver N. How to Own the internet in your spare time // Proceedings of the 11th USENIX Security Symposium (Security '02).-2002.

77. Super-peer-based routing and clustering strategies for rdf-based p2p networks / W. Nejdl, M. Wolpers, W. Siberski et al. // Proceedings of World Wide Web Conference 2003 in Budapest, Hungary. — 2003.-May.

78. Suryanarayana G., Taylor R. N. A survey of trust management and resource discovery technologies in peer-to-peer applications: Tech. rep.: ISR Technical Report UCI-ISR-04-6, 2004.

79. Tapestry: a resilient global-scale overlay for service deployment /

80. B. Y. Zhao, L. Huang, J. Stribling et al. // Selected Areas in Communications, IEEE Journal on.— 2004.— Vol. 22, no. 1,— P. 41-53. http://ieeexplore.ieee.org/xpls/absall.jsp?arnumber=1258114.

81. Thorup M., Zwick U. Compact routing schemes // SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM Press, 2001. - P. 1-10.

82. Trust propagation in small worlds / E. Gray, J.-M. Seigneur, Y. Chen,

83. C. Jensen // Proceedings of the First International Conference on Trust Management (iTrust2003) / Ed. by P. Nixon, S. Terzis.- 2003. http://citeseer.ist.psu.edu/gray03trust.html.

84. Taring test, статья в wikipedia. — http://en.wikipedia.org/wiki/Turingtest.

85. Vigas F. В., Wattenberg M., Dave K. Studying cooperation and conflict between authors with history flow visualizations // Proceedings of СНГ2004, Conference on Human Factors in Computer Systems, Vienna, Austria.— 2004.

86. Wang Y., Vassileva J. Trust and reputation model in peer-to-peer networks // Proc. of The Third IEEE International Conference on Peer-to-Peer Computing, Linkopings, Sweden. — 2003.

87. Wang Y., Vassileva J. Trust-based community formation in peer-to-peer file sharing networks // Proc. of IEEE/WIC/ACM International Conference on Web Intelligence, Beijing, China. — 2004.

88. Welcome to bambi's epinions house of trustitution.— http://www0.epinions.com/content4054884484. — 2004. —Aug 17.

89. Wikipedia: Resolving disputes. — http://en.wikipedia.org/wiki/Wikipedia:-Disputeresolution. — 2006.

90. Wikipedia: Size comparisons.— http://en.wikipedia.org/wiki/Wikipedia:-Sizecomparisons. — 2006.

91. Wikipedia:five pillars (основные политики и руководства по публикации материала в Вивкипедии).— http://en.wikipedia.org/wiki/Wikipedia:-Five pillars. 2006.

92. Wittgenstein L. Tractatus Logico-Philosophicus. — Routledge & Kegan Paul, 1922.

93. Wittgenstein L. Philosophical Investigations. — Blackwell Publishing, 2001.

94. Xiong L., Liu L. A reputation-based trust model for peer-to-peer ecommerce communities // Proc. of IEEE International Conference on E-Commerce Technology (CEC'03), Newport Beach, California, USA. 2003.

95. Xiong L., Liu L. Reputation ' and trust.— cite-seer.ist.psu.edu/xiong05reputation.html. — 2005.

96. Y. W., J. V. Bayesian network-based trust model // Proc. of IEEE/WIC International Conference on Web Intelligence, Halifax, Canada. — 2003.

97. Вадимович С. Б. Правда о Великой Отечественной войне. — СПб.: Але-тейя, 1989.

98. Грищенко В. С. Черви Уорхола и модульные черви: перспективы эпидемий в Интернет // Труды XXIV конференции молодых ученых механико-математического факультета МГУ им. М.В.Ломоносова / Изд-во МГУ: Москва. Vol. I. - 2002. - Р. 62-64.

99. Грищенко В. С. Исчисление мнений // Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. — 2006. — № 43. — С. 139-153.

100. Грищенко В. С. Метрики репутации и борьба за релевантность // Материалы Международной научно-практической конференции студентов, аспирантов и молодых ученых "Безопасность информационного пространства".— Изд-во УрГУПС: Екатеринбург, 2006.-Р. 89.

101. Грищенко В. С. Некоторые новые подходы к маршрутизации в Интернете // Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. — 2006. — по. 43. Р. 198.

102. Нехамкин С., Архангельский Т. Когда считать мы стали раны // Известия. — 2005. — 6 мая.

103. Поликарпов М. Неизвестная цена Победы // Независимое военное обозрение. — 2004. —18 июня.

104. Россия и СССР в войнах XX века: Потери вооруженных сил / Под ред. Г. Ф. Кривошеее. — OJIMA-ПРЕСС, 2001.

105. Сервис организации библиографии citeulike. — http://citeulike.com.

106. Сервис организации закладок del.icio.us.— http://del.icio.us.

107. Сталин И. интервью // Правда. — 1946. —14 марта.

108. Фронтин С. Ю. СТРАТЕГЕМЫ (sextvs ivlivs frontinvs. strategemata).— http://www.xlegio.ru/sources/frontin/. — 84-88 г.н.э.