Содержание к диссертации
Введение
1 Обзор существующих подходов 17
1.1 Открытость и контроль: примеры из истории 17
1.1.1 Пример: потери в ВОВ 18
1.1.2 Пример: Википедия и Британника 20
1.1.3 Пример: история WWW 21
1.1.4 Пример: WWW и поисковые машины 24
1.2 О современной технологии доверия 25
1.2.1 Проблема: сигнал/шум 26
1.2.2 Проблема: дублирование усилий 26
1.2.3 Проблема: фрагментация
1.3 Ранее предложенные решения 27
1.4 Модели доверия/репутации
1.4.1 Действующие модели 28
1.4.2 Теоретические модели
1.5 Рекомендующие системы 31
1.6 Социальные сети 32
1.7 Р2Р 34
1.8 Репутационные механизмы в Р2Р сетях 36
1.9 Топология социальных сетей 37
1.9.1 Безмасштабный (scale-free) граф 38
1.9.2 Мир тесен 39
1.9.3 Уязвимость безмасштабных сетей 39
1.9.4 Маршрутизация в безмасштабных сетях, скелет сети 41
1.9.5 Распространение информации в безмасштабных сетях 42
1.10 Степенные распределения (power-law) 43
2 Топологические вопросы 45
2.1 Степенной разлом 46
2.1.1 Степенной разлом и поиск путей в графе 46
2.1.2 Теорема о достижимости 47
2.1.3 Степенной разлом и IPv4 48
2.1.4 Форсирование экспоненциального роста 49
2.2 Маршрутизация 51
2.2.1 Имена как инструмент разлома 54
2.2.2 Алгоритм 55
2.2.3 Результаты 2.3 Модель издержек коммуникации 58
2.4 Необходимое (глобальное) покрытие 60
2.5 Сравнение: PageRank и "просачивание" 60
3 Репутационная модель 63
3.1 Репутация 63
3.1.1 Простая репутационная аксиоматика 63
3.1.2 Почему не вероятности? 64
3.2 Обобщенная (рефлексивная) аксиоматика мнений 65
3.2.1 Формальное и нечеткое 65
3.2.2 Мера схожести 65
3.3 Рефлексивные множества 66
3.3.1 Мера схожести в рефлексивных множествах 67
3.3.2 Геометрическая интерпретация 68
3.4 Многоуровневая модель 68
3.4.1 Уровни 70
3.4.2 Ожидание 71
3.5 Приложения многоуровневой модели 72
3.5.1 Персональные коммуникации 72
3.5.2 Групповые коммуникации 73
3.6 Выводы 74
4 Групповые коммуникации 75
4.1 Что такое Бульон? 76
4.1.1 Принципы работы 77
4.1.2 Основные примитивы 77
4.2 Кусочки 78
4.2.1 Тела (тексты) и мнения 79
4.2.2 Идентификаторы POV 79
4.2.3 Порядок кусочков 80
4.3 Протокол ос-со 80
4.3.1 Жизненный цикл токенов 81
4.3.2 Востребование 82
4.3.3 Особые возможности движка ос-со 84
4.4 Топологические и сложностные аспекты 84
4.4.1 Вопрос о сложении запросов 85
4.4.2 За и против сложения запросов 86
4.4.3 Издержки сложения запросов 87
4.5 Приложение: Bouillon v2 89
4.5.1 Клиент-серверный вариант 89
4.5.2 Р2Р-вариант 90
4.6 Расчет нагрузки 90
4.6.1 Расчет нагрузки: взбирание 93
4.6.2 Итого: вычислительная нагрузка 95
4.7 Выводы 97
5 Персональные коммуникации . 99
5.1 Черные, белые и серые списки 99
5.2 Общие белые списки 1 5.2.1 Этап I: плоские списки 101
5.2.2 Этап II: транзитивные списки 101
5.2.3 Этап III: диагональная модель 102
5.3 Вычислительная сложность 103
6 Результаты и выводы 105
А Вычислительный эксперимент - маршрутизация 107
В Глоссарий
- Проблема: дублирование усилий
- Теорема о достижимости
- Обобщенная (рефлексивная) аксиоматика мнений
- Особые возможности движка ос-со
Введение к работе
Актуальность темы Ситуация, сложившаяся в наши дни в области производства и обработки информации, часто характеризуется как "информационный взрыв" Такие наблюдаемые параметры, как количество научных публикаций и изданий, количество страниц во Всемирной Сети, трафик в ишерпеїр, растут экспоненциально [12, 14] В подобных условиях становятся все более важными средства автоматического упорядочения и обработки информации - такие, как поисковые машины, рекомендующие системы и т п
Тенденция последних лет заключается в том, что широкое распространение уже собранной информации (публикация) более не представляет проблемы Всемирная паутина дня іексіа, однорашовые (peer-to-peer, Г2Р) сети для мультимедийного содержимого приблизили издержки распространения к нулю На первый план поэтому выходят проблемы сбора рассеянной информации и распросіранения немассовой (г е интересной относительно узкому кругу лиц) информации При этом становится популярной так называемая концепция "Длинного хвоста" Под этим названием подразумеваются наблюдаемые в самых различных сферах степенные распределения популярности [3], когда многочисленные источники пемассовой информации в совокупности представляют не меньший интерес, чем относительно малочисленные источники - "звезды" В ответ на указанные запросы возникли сначала форумы и блоги (веб-дневники) с комментариями-репликами, а затем вики с совместной правкой содержимого
Сбор мнений от неопределенно широкого круга лиц требует значительной открытости среды, те возможности леї ко вносить свои мнения При этом неизбежно столкновение с принципиальной проблемой, чрезвычайно актуальной для Сені последние десять лег, - засорением информационных сред, действующих по принципу push (проталкивание содержимого к потрєбиіелю) Для злонамеренного проталкивания нерелевантных материалов в рекламных или мошеннических целях принят термин "снам" Спам существует в почте, интернет-пейджерах, блогах, вики, поисковых машинах — везде, где есть элемент push В средах, действующих но принципу pull (вытягивание информации пользователем), например, в FTP (протокол передачи файлов) или в "чистом" WWW, спама пет Но в них и сбор рассеянной информации непрост
Итак, фокус инноваций переместился на сбор, фильтрацию и адресное распросіранение информации, чаще локального либо узкоспециального значения, и основное препятствие на этом пути - это засорение, ограничивающее открытость информационных сред
Один из подходов к борьбе с засорением - метрики репутации, отслеживание прошлого поведения участников Для борьбы со спамом в электронной почте, например, широко применяются репутационные инструменты - іак называемые белые и черные списки (і е списки добросовестных и недобросовестных почтовых серверов соответственно) В том или ином виде метрики репутации также используются в поисковых машинах, онлайновых аукционах, на "социальных" сайтах и т д
С изменением задач изменилась и топология информационных взаимодействий от централизованного распространения центр тяжести смещается к социальным сетям, сообществам и группам В плане осуществления контроля как замена централизованным механизмам, имеющим свой потолок масштабирования, активно опробуется общий подход "сети доверия" (Web-of-Trust) или социальных сетей, заключающийся в использовании транзитивных свойств устоявшихся социальных связей (1, 8, 15, 17] Подход базируется на механизмах, доказавших свою работоспособность в реальном мире именно для решения проблем интересующего нас типа Тем не менее, его использование в онлайновых сервисах пока имеет имеет частный, ограниченный характер
Диссертация затрагивает такие темы, как совместное фильтрование, социальные сети, системы доверия и репутации, одноранговые сети Все эти направления активно исследуются в последние 8-10 лет [2, 4-7, 9-11, 13, 16] По каждому из них существуют уже вполне удавшиеся продукты и проекты, іакие, как рекомендующие системы Amazon и Epimons, онлайновая социальная сеть Lmkedln, алгоритм PageRank, одноранговая сеть BitTorrent, открытая онлайновая энциклопедия Wikipedia
Цель работы Используя математическую модель распространения информации в среде с социальной топологией, разработать алгоритмы функционирования распределенной вики-сети, использующей явную работу с мнениями читателей и репутационные механизмы для массивной распределенной обработки и фильтрации материала Оценить вычислительную сложность разработанных алгоритмов Реализовать алгоритмы в программе-прототипе
Задачи
Разработать адекватную формальную модель мнений, репутации и рекомендаций, образующих сеть доверия
На основе построенной формальной модели социальной сети создать алгоритмы для сбора, распространения, фильтрации и обработки информации в максимально открытой среде
Даіь теоретические оценки вычислительной сложности разработанных алгоритмов
Реализовать алюритмы в виде работающих программных комплексов или их прототипов
Реализоваїь сеіь доверия для персональных коммуникаций (в первую очередь, e-mail) как репутационпый механизм для борьбы со спамом
Направления исследования
Репутационная аксиоматика, основанная на теории нечетких множеств, отражающая все требуемые явления ответственность, репутацию, рекомендации, и определяющая математическую модель - основу дальнейшей работы
Маршрутизация в безмасгатабных сетях как метод построения ре-комендациопных цепочек на социальном графе
Топологические аспекты распространения общего знания в социальных сетях в предположении безмасштабной топологии
А Создание алгоритмов среды обработки информации, действующих поверх социальной сети и использующих эту сеть для распространения, фильтрации и хранения произвольной информации
Этапы работы На теоретическом этапе исследования была разработана полностью персонализоваиная репутационная аксиоматика Затем на основе теории сложное і и вычислений и анализа топологических особенности целевою семейства графов были разработаны полностью де-цешралиюванные алюритмы, реализующие принципы репутационных вычислений применительно к информационным средам С использованием модели социальной сети па основе ірафов Эрдсша-Репьи и безмас-шгабных графов была получена оценка вычислительной сложности разработанных алгоритмов, оказавшейся приемлемой с точки зрения возможностей практической реализации На закчючигельном этапе исследования разрабоїашше алгоритмы составили ядро программных комплексов, имеющих практическую ценное ть
Методы исследования В работе используются методы теории графов и нечеткой логики, а также методы дискретной оптимизации, оценки вычисли іельной сложности алгоритмов и экспериментальные данные по функционированию соїевьіх протоколов интернета
Основные результаты, выносимые на защиту
Репутационная аксиоматика
Теорема о достижимости информации в сеги с социальной топологией
Социальная вики-сеть Бульон - модель, алгоритмы и программное обеспечение
Маршругизационная схема с топонимами для безмасшл абиых сетей решение задачи о кратчайших путях на безмасштабном графе с сублинейной вычислительной нагрузкой на узел
Репутационная система P2PWL (общие белые списки для почтовых серверов) - модель, алгоритмы и программное обеспечение
Достоверность и обоснованность Работоспособиость алгоритмов проверяется как аналитически, так и через создание реально работающих программ Значительная часть работы посвящена вопросам вычислительной сложности алгоритмов Эффективность маршрутизаци-онных алгоритмов проверяется через вычислительные эксперименты на реальных и синтетических топологиях и сверку результатов с классическими алгоритмами Ключевые аспекты работоспособности сети Бульон рассматриваются на аналитических моделях, общая рабогоспособность проверяется через создание работающего прогоиша Теоретическая работоспособное і ь репутациошюй сети обмена белыми списками P2PWL вытекает из работоспособности вышеупомянутых маршрутизационлых алгоритмов Базовый прототип P2PWL запущен в промышленную эксплуатацию на клике почтовых серверов г Екатеринбурга
Научная новизна Предлагаемая в данной работе модель метрики доверия и репуіации отличается от моделей, ранее встречавшихся в литературе, тем, что опирается на интуитивно понятые аксиомы, сформулированные в терминах теории нечеіких множеств
В тополоіичєской и сложностной части работы автором предложено понятие степенного разлома, а также получены некоторые новые результаты по теории безмасштабных сегей В частности, усіановлено, что функции коммуникационного ядра безмасштабной сети обеспечивает геометрическая пропорция числа вершин наибольшей степени (так называемых "хабов"), что важно как для вопроса о маршрутизации, так и для задачи о распространения информации в безмасштабной сети
Разработанный автором оригинальный алгоритм маршрутизации с именами малого сублинейною размера (топонимами) впервые решает
задачу о кратчайших путях для безмасшгабных графов с сублинейной сложногтыо п расчете на узел (Задача о всех кратчайших путях для произвольных графов имеет линейную сложность па узел, и известно, что этот результат в общем случае неулучтасм ) Наблюдения за реальными сетями и аналитические результаты показывают, что сети безмасгатаб-ной топологии распространены весьма широко, в силу чего предлагаемый алюритм маршрутизации имеет большое практическое значение
Предложена модель издержек коммуникации, иллюстрирующая фундаментальную важность безмасштабпой гополоіии дня информационных сетей различного рода
Разработанная автором среда Бульон, а также лежащий в ее основе протокол, впервые реализуют совместную работу с редактируемым гипертекстом в одноранговой сети (внесение, правку, фильтрацию, распространение гипертекста) Ранее известные среды (например, Ггеепег.) позволяли чишь хранить документы в однорапювой сети
Разработанное автором программное обеспечение P2PWL является, по-видимому, первой попьикой расширить возможности "белых списков", основанной на открытом решении в одноранговой архитектуре
Практическая значимость и внедрение результатов Разработанный автором программный комплекс Бульон, а также лежащий в его основе протокол, характеризуются следующими особенностями
это шпертсксговая среда, где документы связаны гиперссылками,
это редактируемая среда с возможностями совместной обработки документов (wiki),
это открытая однорашовая есть с тциалыюй топологией (такой тип сети также называется Г2Р, fnend-lo-fnenu),
в этой среде репутации и мнения пользователей (рекомендации) используются для совместного фильтрования материала
По набору возможностей среда Бульон является уникальной, по-видимому, нет онлайновой среды, имеющей более двух из перечисленных характеристик По полезному функцнонату Бульон сочетает возможности Р2Р сети, рекомендующей системы, онлайновой социальной сети, браузера и текстового процессора В отношении базовых принципов распространения информации среда Бульон использует как pull ("вытягивание" информации пользователем), так и push ("проталкивание" информации к пользователю) Характерная проблема push-сред, а именно засорение, решается фундаментальным образом, через отсутствие полной связности участников Участник имеет возможность протолкнуть информацию
лишь в нскоюрую свою социальную окрестность Зюі подход, имитирующий социальные процессы реальною мира, является принципиально новым для сетевых сред
Если опьп эксплуатации среды Бульон большим количеством пользователей подтвердит теоретические оценки, данная техіюлої ия можег стать основой хранилища знаний, значительно превосходящего существующие образцы по охвату и глубине представленных знаний и удоб-ст ву использования Такая среда може г бы гь более полным воплощением метафор "социальною вики", "Редактируемой Паутины", а іакже "Социальной Паутины", чем все теперешние модели социальных сетей
Использование P2PWL в объеме самого базового функционала уже сегодня позволяет преодолеть основной недостаток "серых списков" - задержку писем от ранее неизвестных отправителей (что также означает и задержку практически всех писем первое время после установки) Так, белый список почтового сервера plotmka ru, сформированный с помощью P2PWL, на сегодня включает порядка 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 наименований
Проблема: дублирование усилий
В отдельные периоды (перестроечных разоблачений) назывались и 40 и 80 миллионов (43,3 млн общих потерь - число названо Б.Соколовым).
Сталинскую цифру можно считать эталоном полного контроля, особенно если вспомнить историю с переписью 1937 года [114]. Напомню, что результаты переписи показали убыль населения СССР и не совпали с прогнозами И.В.Сталина (162 против 180 миллионов). Эти результаты были засекречены, а руководители Центрального управления народнохозяйственного учета - расстреляны. Кажется парадоксальным, что полный контроль приводит к ухудшению качества информации. Впрочем, большого противоречия тут нет. Будем понимать качество, как показатель относительный, определяемый теми, кто осуществляет контроль. С этой точки зрения, Сталинская цифра -непревзойденный эталон качества.
"Разоблаченческие" цифры, в свою очередь, демонстрируют недостатки полной бесконтрольности. Как правило, такие цифры заявлялись без сколько-нибудь серьезного обоснования. Комментарии тут излишни. На настоящее время "разоблаченческую" традицию продолжает Б. Соколов [109]. Актуальная версия в 26-27 миллионов в части военных потерь (8,6 миллиона) опирается на результаты, опубликованные в 1993 под руководством Таким образом, при Горбачеве мы потеряли в войне столько же, сколько при Сталине и Хрущеве вместе взятых. ген. Г.Ф. Кривошеева [116]. Сами результаты Кривошеева получены еще в советское время и, возможно, не свободны от недостатков советской отчетности. Однозначно можно сказать лишь то, что таблицы Кривошеева, по-видимому, в принципе не поддаются выборочной проверке базовыми фактами, доступными человеческому восприятию (например, воспоминаниями участников ВОВ), являясь предметом "высокой статистики". Например, в исключительных случаях мы можем узнать с достаточной степенью точности и достоверности потери такого крупного соединения, как дивизия. Скажем, из мемуаров известно, что 365-я Уральская стрелковая дивизия вступила в войну 6 декабря 1941 под Москвой, а в январе 1942 ее остатки погибли в окружении в Мончаловских лесах, со всем командным составом, документами и прочим. Таким образом, общие потери должны быть примерно равны либо превосходить списочный состав дивизии. Увы, это нам никак не поможет, поскольку в таблицах Кривошеева дивизии даже не перечислены, дано лишь их общее количество в той или иной операции. Непонятно даже, входит ли 365-я в список. По большому счету, принятие либо непринятие результатов Кривошеева является вопросом веры.
Иллюстративным является пример Курской оборонительной операции, на который обратил внимание Михаил Поликарпов [115]: данные о потерях, указанные в боевом донесении штаба Воронежского фронта, хорошо согласуются с данными немецкой стороны: 46,500 и 51,000 безвозвратных (т.е. убитые плюс пленные) потерь соответственно, причем советская сторона указывает 26 тыс. пропавших без вести, а немецкая - 24 тыс. пленных. В то же время, по версии Кривошеева, безвозвратные потери советской стороны - 27,542, т.е. почти в два раза меньше. Поэтому, одно расхожее мнение заключается в том, что Кривошеевские цифры можно принимать лишь как нижнюю границу.
Странно закончился проект Центрального Банка Данных, куда к 50-летию победы должны были быть поименно внесены все погибшие и пропавшие без вести воины. Сама выбранная методика скорее тяготела к завышению за счет дублей (когда на одного человека заводилось несколько дел, например). Была предана гласности промежуточная информация [115], что в ЦБД уже внесено 19 млн записей и осталось еще около полумиллиона, после чего работа, по-видимому, была прекращена - во всяком случае, ни подтверждений, ни опровержений цифры обнародовано не было.
Итак, на протяжении полувека некоторая информационная среда эволюционировала от максимального контроля к некоторой открытости, затем - к бесконтрольной открытости и затем - к открытости контролируемой. Соответственно и ответ на один вполне конкретный вопрос изменялся вместе со средой. По-видимому, тот ответ, который мы имеем сегодня, несколько ближе к истине чем тот, что был дан 60 лет назад. Что же касается действительной цифры потерь, то академик РАН Ю.А. Поляков, председатель научного совета РАН по исторической демографии и исторической географии, занимавшийся вопросом довольно много лет, резюмировал следующим образом:
Надо остановиться на нынешней цифре и прекратить дискуссию -просто понимая, что фактически число потерь гораздо выше. [114]
Британника - энциклопедия, основанная в 1768 году и пополняемая с помощью труда оплачиваемых авторов. К созданию современной версии Британни-ки было привлечено более 4,000 человек. Изначально (XVIII век), Британника ориентировалась на научную информацию и издавалась в Эдинбурге. Содержимое было весьма свежим, энциклопедия включала последние научные результаты. Начиная с третьей редакции (1788-1797), многие статьи писались ведущими экспертами по тому или иному вопросу. В начале XX века Британника уже не могла поспевать за периодикой и специализированными изданиями, и начался процесс популяризации - энциклопедия стала издаваться в расчете на широкую аудиторию читателей и содержала более общую, справочную информацию. Описанный эффект весьма важен в контексте данной работы: возможности масштабирования среды уперлись в некоторый потолок, что привело к сокращению ее функционала и значения. Другие варианты исхода в подобной ситуации включают фактическую смерть среды (Usenet) и фрагментацию, т.е. появление большого числа слабо связанных (loosely coupled) ее экземпляров.
Википедия - основанная в 2001 году онлайновая энциклопедия на основе технологии Wiki, свободной правки содержимого посетителями. Политика наполнения: никаких оригинальных мнений составителя, нейтральная точка зрения, каждое мнение должно подаваться в контексте (как минимум, со ссылкой на заслуживающий доверия источник) [102]. Википедия может редактироваться любым посетителем, налицо практически идеальная открытость. Гарантия качества содержимого - контроль со стороны других посетителей (концепция soft security). Порой, такая степень открытости приводит к редакторским войнам, когда один и тот же кусок текста переписывается/восстанавливается по многу раз. В Википедии используется ряд приемов и политик, чтобы успокаивать подобные конфликты. В частности, редактор, в течение 24 часов сделавший в одной статье три отката (т.е. удаливший чужие правки), автоматически лишается доступа на протяженный период времени. Существует также многоступенчатая процедура разрешения споров, делающая акцент на примирении противоборствующих сторон [100]. Что примечательно, процедуры не преду 21 сматривают участия администраторов. Редакторы могут привлечь третьего участника для разрешения спора, в случае крайней необходимости привлекается кто-то из добровольных "адвокатов" (Members Advocates), в еще более сложных случаях - арбитр из Arbitration Committee (на май 2006 это около 10 добровольцев). Вовлечение штатного персонала Википедии, а это 2 человека (и еще двое на пол-ставки) штатными процедурами не предусмотрено.
Как показало исследование журнала Nature [33], точность Википедии и Британники сравнима: выборочная проверка 42 статей экспертами выявила 8 серьезных ошибок, поровну в обеих энциклопедиях; средняя статья Википедии содержала четыре неточности, средняя статья Британники - три. Учитывая, что сейчас Британника также поддерживается с помощью компьютерных технологий, можно заключить, что преимущество Википедии - в использовании лучших социальных механизмов, большей открытости при сравнимом уровне контроля.
Теорема о достижимости
При изучении социальных сетей важно иметь ввиду особенности их топологии. Что мы знаем о социальных сетях из повседневного опыта? Они обладают высоким коэффициентом кластеризации, то есть высока вероятность того, что два ваших друга знакомы и между собой. Также, "мир тесен" - очень часто мы встречаем знакомых нам людей в совершенно незнакомом контексте, находим самых неожиданных общих знакомых и так далее. Рассмотрим это в более формальном аспекте.
Социальные сети, которые будут рассмотрены в последующих главах, как предполагается, будут иметь безмасштабную (scale-free) топологию. Сети такого типа также называют степенными (power-law).
Для такой гипотезы есть достаточные основания. Как показали исследования последних лет, к данному классу принадлежат сети контактов e-mail [29], интернет на уровне IP [31], интернет на уровне автономных систем [31], граф ссылок во Всемирной Сети [9], сети половых контактов [6], граф сотрудничества звезд кинематографа (co-starring, [71]) и многие другие.
Основное свойство такого устройства - степенное (power law) распределение степеней вершин, Р(к) Аг7, где /с-степень вершины, а Р-вероятность того, что произвольная вершина имеет такую степень. Параметр 7 предполагается в интервале (2;3). также предполагается высокий коэффициент кластеризации и, как минимум, некоррелированность степеней соседних вершин. Коэффициентом кластеризации называется вероятность того, что два соседа одной вершины также являются соседями. Что касается корреляции степеней соседей, то, по-видиму, достаточно требование некоррелированности, наличие корреляции даже излишне. В случае же обратной корреляции, когда хабы окружены исключительно узлами малой степени, свойства графа могут быть иными, т.е. это уже не scale-free. Общепринятой точки зрения по этому вопросу нет.
Такие графы названы безмасштабными, поскольку средняя степень вершины в них не является характерной, т.е. отсутствует характерный масштаб. Возможно также, что это намек на свойства самоподобия подобных графов и сетей. 5 Для такой топологии характерно определяющее значение хабов - малого количества вершин наибольшей степени. Общепризнано, что для безмасштаб-ньгх графов ключевым является процесс роста. Наиболее распространенной моделью появления таких структур является принцип preferential attachment ("rich gets richer", "деньги к деньгам"), когда в растущем графе вероятность появления новых связей у вершины пропорциональна ее степени, т.е. количеству уже имеющихся связей. Есть и другие взгляды на этот вопрос.
Впервые гипотезу о логарифмическом диаметре человечества выдвинул венгерский писатель Frigyes Karinthy, отталкиваясь от экспоненциального роста количества людей по мере продвижения по графу знакомств. Первое широко известное научное исследование вопроса тесноты мира - знаменитый эксперимент Милгрэма. Американский социолог отправлял письма некоторому удаленному лицу "по цепочке". Каждый промежуточный участник должен был передать письмо человеку, которого он достаточно хорошо знал, и который имел лучшие шансы достичь адресата. Серия экспериментов показала, что средняя длина такой цепочки - пять-шесть шагов, в тех случаях, когда письмо все-таки доходило. Так родилась гипотеза six degrees of separation.
Простейшая модель тесного мира - случайный граф Эрдоша, где связаны случайные вершины, случайным образом. Другие ранние модели малого мира использовали решетку (буквально) или иной граф с пространственной локальностью, например - кольцо (буквально), к которому затем случайно добавлялись "shortcuts" - связи между случайными вершинами, не зависящие от их расположения. Эти модели имели логарифмический диаметр и вышли из употребления, по мере появления новых знаний о сложных самоорганизующихся сетях и теории безмасштабных графов, в частности.
Относительно диаметра scale-free сетей, интересную теорию выдвинули Ко-эн и Хавлин [20]. Они заметили, что специально построенный граф со степенным распределением степеней вершин вида а;7,2 j 3, где узлы высокой степени в первую очередь соединены с другими узлами высокой степени, имеет диаметр O(loglogiV), где N - количество вершин, Далее, опираясь на вероятностные рассуждения, авторы показали, что случайный (некоррелированный) power-law граф имеет диаметр того же порядка. Таким образом, в большом количестве случаев диаметр безмасштабных графов можно принимать за константу, не зависящую от размера графа.
Характерной особенностью является эффект funneling, когда большая часть кратчайших путей от заданной вершины до всех остальных вершин проходит через одного, наиболее значимого, соседа этой вершины. Эффект был отмечен еще Милгрэмом и более детально исследован Марком Ньюманом [60, 61] для случая графа академических соавторств уже в наши дни.
Безмасштабные графы весьма устойчивы к случайному удалению узлов (т.е. к сбоям). Для того, чтобы разрушить гигантский кластер безмасштабного графа случайным удалением узлов, необходимо удалить их значительную часть - 20..30% [б]. Это объясняется тем фактом, что, в отличие, например, от дере 40
ва, безмасштабный граф содержит альтернативные пути. Но, как уже сказано, хабы играют ключевую роль в безмасштабных графах. При удалении нескольких процентов вершин наибольшей степени безмасштабный граф распадается. Удаление геометрической пропорции вершин наибольшей связности (скажем, О (у/її) приводит к многократному увеличению диаметра графа - "клубочек" превращается в "серпантин" [38, 5], этот эффект более подробно рассмотрен в Гл. 2. То есть, безмасштабные графы устойчивы к сбоям и уязвимы перед целенаправленной атакой.
Подобное свойство безмасштабных графов имеет разнообразные практические последствия. Например, для предотвращения эпидемий венерических заболеваний необходимо сосредоточиться на вакцинации хабов, т.е. наиболее активных лиц. Для искоренения политической оппозиции также необходимо сосредоточиться на ключевых персонах. Что, в общем-то, не является новым знанием.
Тарквиний Гордый отец, решив убить главарей габинов, но не желая никому доверить свое намерение, ничего не ответил вестнику, которого по этому поводу прислал к нему сын; только, гуляя по саду, он прутиком отсекал головки наиболее возвышающихся маков. Вестник, вернувшись без ответа, рассказал молодому Тарквинию, что у него на глазах проделал отец. Тот понял, что так надо поступить с выдающимися габинами. [120]
Для установления диктаторского контроля и сегодня используются такие меры, как взятие под контроль независимой прессы, разрушение политических партий и прочие подобные механизмы политической дезорганизации общества. При работе с менее развитыми обществами используются более брутальные практики. Поскольку политические институты и газеты в таких регионах не играют роли основной политической площадки (институциональных "хабов"), работа фокусируется на уничтожении персоналий. Например, для подавления т.н. "бандитизма" в мусульманских регионах СССР/России неоднократно и достаточно успешно использовалась охота на лидеров подполья ("басмачей", "ваххабитов" и т.д.). Это несомненно более дешевое средство, нежели геноцид или массовая депортация.
В случае, когда уничтожаемая сеть является скрытой, применяется следующий весьма эффективный метод. Для каждого случайного выявленного узла отслеживают его связи. Поскольку значительная доля всех связей принадлежит именно хабам, вероятность обнаружить таким порядком хаб весьма высока. Применив такую, достаточно простую, методику, можно через уничтожение всего нескольких процентов узлов (хабов и "побочных" жертв) разрушить скрытую безмасштабную сеть. Например, таким образом можно уничто ГОБ/БЬІСТЕКА. І жить действующую и потенциальную политическую оппозицию и превратить общество в "мелкую крошку" атомарных сообществ.
Задача о маршрутизации (или кратчайших путях на графе) - важная и популярная алгоритмическая задача, имеющая применение во многих областях компьютерных наук и приложениях. Как уже было замечено, для некоторых задач, связанных с метриками доверия, а именно для задачи о персональных коммуникациях (см. Гл. 5), нам необходимо будет решение задачи о маршрутизации на безмасштабном графе для того, чтобы найти кратчайшую рекомен-дационную цепочку. Поэтому я рассмотрю некоторые ключевые результаты, связанные со структурой кратчайших путей в безмасштабных графах.
Обобщенная (рефлексивная) аксиоматика мнений
Основная проблема, для которой была предназначена [37] простая репутационная аксиоматика - спам. Это относительно простая задача: каждое сообщение может быть признано либо спамом, либо не спамом (ham). Соответствующие мнения получателей становятся публично доступны, благодаря чему отправители имеют хорошую либо плохую репутацию.
Основная абстракция простой репутационной аксиоматики: некий участник (участники) инициирует некоторое сообщение. Другой участник, выступающий в роли получателя, может это сообщение принять или не принять. Основной критерий принятия - хорошая репутация инициатора.
Определение 2 Репутация - это средняя мера соответствия прежних сообщений, за которые были ответственны те оке участники.
Гипотеза 1 (Репутационная гипотеза) Мы ожидаем, что прошлое поведение (т.е. репутация) в некоторой степени предсказывает будущее поведение. Также в ПРА рассматривается возможность рекомендовать то или иное сообщение. Достигается это просто: рекомендатель принимает на себя ответственность за сообщение - и, согласно определению 2, в расчете ожидаемой меры соответствия рекомендованного сообщения принимается в расчет и репутация рекомендателя.
Для того, чтобы выразить "осторожную" рекомендацию используется нечеткая логика (т.е. если рекомендатель е поручился лишь "в некоторой степени" с, тогда рекомендованные сообщения принадлежат к его множеству ответственности лишь этой самой степени, є Єс Ее). В таком случае репутация рассчитывается, как взвешенная сумма (центроид):
Таким образом, была получена довольно простая и естественная аксиоматика. Очевидным пробелом [37] является отсутствие обсуждения механизмов распространения/востребования репутациошюй информации по заданному отправителю. Отчасти эта проблема обсуждается в Разд. 3.5, однако и в этой статье данный вопрос подробно не рассматривается.
Отдельно следует остановиться на том, почему не используются средства теории вероятностей. Во-первых, нечеткая логика описывает совсем другой род неопределенности - не вероятность некоторого исхода, а неопределенность имеющегося результата, как правило - при работе с расплывчатыми понятиями, наподобие "хорошо-плохо" или "тепло-холодно". Опыт исследовательской работы по проблематике спама убедил меня, что это понятие вполне расплывчато и субъективно; при работе с более общим понятием "уместность" ("релевантность") это еще более очевидно. Таким образом, использование вероятности имело бы смысл наряду с использованием нечеткой логики.
Однако есть одно соображение, которое ставит применимость теории вероятностей под большое сомнение. Вероятностная модель (Бернулли) подразумевает наблюдение за некоторым случайным процессом (монеты, кости). Эта модель не содержит возможности наличия обратной связи, а именно, что результат эксперимента может зависеть от того, что мы о нем думаем. Если мы наблюдаем за действиями кого-то разумного, кто в это же время наблюдает за нами, этим моментом пренебрегать никак нельзя.
Назовем это "Проблемой зеркального коридора". Никоим образом не утверждается, что не-применение теории вероятностей позволяет эту проблему решить. Столь плотное вовлечение человеческого фактора, по-видимому, вообще выводит данную проблему за границы точных наук. И хотя Репутационная гипотеза, субъективно, имеет статистический характер, формально теория вероятностей в данной модели задействована не будет.
Также не утверждается, что конкретные численные значения соответствуют каким-либо явлениям физического мира (например, не утверждается выполнение Закона Больших Чисел). То, что нам требуется в конечном счете -это некоторое практически эффективное ранжирование матеприалов по "релевантности".
Интересно было бы перейти к более широкому классу проблем. Вместо отправителя сообщения и получателя, определяющего степень "спайности" сообщения, будем рассматривать двух субъектов а и ft1, множество элементарных сообщений и некоторый класс С, к которому данные сообщения могут быть отнесены либо не отнесены.
Для понимания вопроса ключевым является различение между формализмом и мнением. Формальными и точными подразумеваются идентификаторы классов (напр.: слово "спам") и идентификаторы сущностей (отправителей, сообщений); вопрос же отнесения сущности к классу является уже мнением. В общем-то, это мнение и представляет из себя смысловое наполнение класса. В том случае, если мнения различных субъектов относительно наполнения данного класса близки - мы можем говорить об общепринятом термине (обозначении).
Обобщим понятие репутации/оценки (pv(s), Разд. 3.1.1) до понятия меры схожести мнений. Рассмотрим, каким образом могут соотноситься мнения двух субъектов по некоторому фиксированному вопросу (Рис. 3.1). В качестве меры согласия естественно определить отношение мощности множества "согласия" (т.е. Са П Съ) к совокупной мощности множества заявленных соответствий по данному вопросу (т.е. CaUCj) - все в пределах обоюдной компетенции
Более подробно следует остановиться на "рамках обоюдной компетенции". В предыдущем разделе уже рассматривались "осторожные" рекомендации - имеет смысл реализовать похожий механизм и здесь. Мы понимаем степень принадлежности х кСа, как мнение а. Насколько а уверен в этом мнении? (Как
2Конечно, если бы целью данной работы являлось написание рекомендующей системы для веб-магазина, где все данные лежат в одной БД, мы могли бы оперировать с оригинальным, полным Сь. Однако же, в распределенном случае полная сверка всех мнений просто невозможна. выразить: "сам не видел, но говорят, что... 7) В то же время, понятно, что, если речь идет о мнениях, один участник может знать о нескольких различных мнениях по вопросу. Если, например, наивно сформулировать наличие двух мнений, как х Є0.і С YL х Єо.з О, то в результате получим х Єо.д О, что есть совсем не то. Именно поэтому будем работать с утверждениями, как с некоторыми элементами: Of = (Са) = {(х Єр, Са)} - рефлексивное множество мнений участника а относительно класса С. ("Рефлексивное" в смысле "отражения", "самоосмысления", "способности человека познавать свою умственную деятельность так, как мы познаем внешние предметы"). Поскольку мы работаем с нечеткими множествами, вполне логично, что мнение, принадлежащее к Of в некоторой степени - это мнение, в котором а не вполен уверен (будем соответствующую степень принадлежности называть мера уверенности).
Особые возможности движка ос-со
Рассмотрим пространство, в котором распространяются запросы и мнения. Метрикой расстояния в нем является репутационное расстояние. Будем считать, что в этом пространстве, с увеличением радиуса шара его масса нарастает не менее, чем экспоненциально. Это первое упрощающее предположение. Из-за высокой кластеризации социальных сетей можно было бы подумать, что масса будет нарастать каким-либо образом медленнее. Но эксперименты и теория показывают, что в безмасштабных графах, к которым относятся социальные, масса нарастает с радиусом быстрее, нежели экспоненциально, см. Гл. 2. Второе упрощающее предположение заключается в том, что в данном рассуждении мы будем измерять расстояние в шагах, а не в репутационном расстоянии. Третье упрощающее предположение - мы предполагаем, что между прямым и обратным расстоянием (систематической) разницы нет, или даже, для простоты, рл{В) = Рв{А).
От участника А во все стороны распространяются корневые запросы - на некоторое предельное расстояние, которое никак не может быть больше четырех шагов, но почти наверняка достигнет двух ("два - можно, четыре - может быть, возможно"). Траектории тех запросов, чьи копии пришли в точку 5, описывают эллипс с большой осью, равной радиусу распространения корневого запроса. Действительно, длина каждой траектории не должна превысить радиуса распространения запроса, см. Рисунок 4.2. Соответственно, траектория мнения в обратном направлении представляет из себя траекторию запроса наоборот. Итого, копии одного ответа, которые вынужден рассылать В, описывают эллипс. Рассмотрим, как масса этого эллипса Е соотносится с массой большого шара О, т.е. количеством всех узлов, покрытых корневым запросом.
Даже в пространстве с описанными мной свойствами, эллипс накрывается двумя шарами Hi и Hi радиусом в половину большой оси и центрами в фокусах. Т.о. радиус Я; равен половине радиуса О, а значит, масса Я равна квадратному корню массы О. Следовательно, количество узлов, покрытых копиями каждого из оригинальных мнений, являющихся ответом на некоторый корневой запрос, не превосходит двух квадратных корней от количества узлов, покрытых копиями самого корневого запроса. Или же,
Замечание 3 Затраты на один (корневой) ответ имеют вдвое меньший порядок, чем затраты на соответствующий корневой запрос.
Таким образом, если имеющих свое мнение мало, то затраты на возврат ответов не превосходят затрат на распространение запросов. Если же мнений по странице много, то политика передачи не более к мнений об одном кусочке ограничивает совокупные затраты на доставку мнений к\0\, А;-кратными затратами на распространение запроса.
Клиентская часть На настоящий момент единственный существующий клиент реализован в технологии AJAX: загруженная в браузер пользователя стра 90 ница содержит Javascript, который опрашивает сервер, получает оттуда кусочки, затем средствами DOM собирает из них документ. Веб-сервер Веб-сервер является одновременно внешним компонентом некоторого jabber-сервера. По http происходит общение с клиентом, по jabber/XMPP - общение с другими серверами Бульон. Внутри сервера есть четыре основных блока:
Бульон потребляет достаточно разнообразные системные ресурсы. Это пропускная способность сети, ресурсы Jabber-сервера, место на диске, ресурсы встроенной Berkeley DB. Рассмотрим предполагаемую нагрузку, производимую одним пользователем. Во-первых, следует заметить, что эта нагрузка - постоянная. Пользовательский движок работает 24x7; даже когда пользователь не в сети - движок получает запросы от других пользователей. Активные запросы и запрошенные мнения подлежат обновлению - и если страница открыта в браузере пользователя, соответствующие запросы вещаются каждые 50 секунд. Процент пользователей, находящихся в сети одновременно - важный показатель. Появление всех пользователей в сети одновременно будем рассматривать, как редкое явление, наподобие того, что те же сети GSM испытывают лишь пару часов в году, как раз в районе Нового Года. ПО Бульон обладает свойством graceful degradation - большая или меньшая загрузка сервера ведет к изменению порога репутационного расстояния, выше которого токены обрабатываются, ниже - обрабатываются частично (напр: не пересылаются) либо не обрабатываются вообще. Т.е. перегрузка сети уменьшает ее прозрачность , достижимость мнений. Нормальной ситуацией будем считать ту, когда запросы могут распространяться на два шага от инициатора (до друзей друзей).
При оценке потребляемой пропускной способности будем исходить из того, что один токен-мнение либо запрос мнения в форме XML имеет размер около 300 байт. Также, для такого XML можно ожидать коэффициента компрессии 10:1 (проверено). Все технические проблемы, связанные с ХМРР, поддержанием соединений TCP и маршрутизацией XML (stanzas), перекладываются на Jabber-сервер. Принимая во внимание ограниченность функций Jabber-сервера и достоинства современных реализаций (напр, ejabberd) можно сказать, что Jabber-сервер вряд ли будет узким местом.
При оценке производительности Berkeley DB можно считать, что на среднем сервере, по-видимому, возможна обработка до 10,000 токенов в секунду реализацией на Java и до 100,000 токенов на С. (Но на С реализации Бульона пока нет, поэтому будем рассматривать это, как теоретический потолок.) Подробнее об этом - ниже. Разгрузить сервер от операций с БД можно было бы, реализовав Бульон в схеме полного Р2Р, с ос-со движком на пользовательском компьютере. Такое архитектурное решение оставим на самый крайний случай, поскольку хотелось бы, чтобы пользователи были всегда в сети, чего в случае с пользовательскими компьютерами гарантировать нельзя.
Вопрос: сколько запросов в секунду придется обрабатывать движку среднего пользователя и каков будет объем траффика, если: у него есть 100 друзей и у каждого друга есть 100 друзей, а запросы распространяются на два шага. Рис. 4.4: Прикидки вычислительной нагрузки - предполагается распространение запроса на два шага. Верхний рисунок ситуация для конечного (второго шага), нижний рисунок - для промежуточного (первого шага). Не все участники сидят в Сети одновременно, а также некоторые участники смотрят одни и те же страницы и их запросы суммируются. Поэтому примем следующую гипотезу: участник, имеющий 100 друзей, вынужден в среднем поддерживать одновременно запросы по 10 разным страницам в качестве промежуточного узла. То есть, этот участник должен пересылать запросы своим друзьям (это случается каждые 50 секунд). Также, он должен пересылать обратно ответы, от друзей полученные.
Итак, примем, что со стороны каждого друга поддерживается 10 корневых запросов одновременно. Наш участник является "конечным получателем" - он .не должен пересылать эти запросы, а только отвечать на них. Тогда количество принимаемых запросов в 50 секунд (период обновления) равно: 100 10, т.е. 20 запросов в секунду.
Нагрузка: коренные мнения
Как и в предыдущем пункте, у нашего участника 100 друзей. Рассмотрим количество пересылаемых им корневых мнений в тех же условиях. Корневых запросов, подлежащих пересылке, мы получаем 10, поскольку только запросы, инициированные друзьями, подлежат пересылке, а также по-прежнему в силе предположение из предыдущего пункта о том, что не все друзья в сети одновременно и некоторые запросы суммируются. Даже если все друзья отвечают на каждый из пересланных им корневых запросов, мы получаем 10 100 корневых мнений. Для статического случая с обновлением мнений раз в 50 минут получается 0.27 мнения в секунду. Даже если кто-то из друзей каждую секунду кликает в новую, ранее никем не востребованную, ссылку, что есть довольно смелое предположение, имеем 100 корневых мнений в секунду.
