Метрики репутации: модели и алгоритмы построения открытых информационных сред тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Грищенко, Виктор Сергеевич

• Грищенко, Виктор Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Грищенко, Виктор Сергеевич

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 сервера: два сервера провайдеров (УралРелком и СЦК) и два корпоративных.

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

Список литературы диссертационного исследования кандидат физико-математических наук Грищенко, Виктор Сергеевич, 2007 год

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 г.н.э.