WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

М. В. Баклановский, В. Ю. Попов) в Уральском государственном университете.

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

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

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

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

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

В главе 2 дается анализ общих вопросов, связанных с распространением информации в социальных сетях, репутационными метриками и пр. Выделяется типовой подход к решению некоторых задач на графах, названный “степенной разлом”. Степенной разлом – это разделение задачи сложности O(N) на две задачи сложностей O(P ) и O(Q) – так, что N P Q, а сложность “разложенной” задачи имеет порядок O(P + Q), т. е. сублинейный. Приводятся различные примеры применения разломов на практике, в основном – в задачах о маршрутизации. Исследуются подходы к решению задач сложностного и топологического характера, связанных с реализацией метрик репутации на безмасштабных графах; в основном, это задачи о маршрутизации и распространении информации.

На основе известных свойств безмасштабной топологии делается вывод о том, что принцип подтверждения сообщения промежуточным узлом, лежащий в основе Бульон, позволит передавать сообщение из одной произвольной точки сети в другую произвольную, в идеале, за два промежуточных прочтения и подтверждения – независимо от размера сети. Затем из моделей распространения информации на основе графов Эрдеша-Реньи и безмасштабных графов, а также других соображений выводится основная теорема о достижимости: материал в сети вида Бульон доступен большинству участников, если он распространился на сублинейную долю узлов Na, а каждый участник может запрашивать свою соответствующую сублинейную окрестность Nb (здесь N - число узлов сети, а a + b 1).

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

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

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

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

мнения о качестве рекомендаций рекомендателей. Затем рассматриваются случаи групповой и персональной коммуникации и многоуровневая модель применяется к этим случаям. В результате возникают две модели работы с сообщениями: модель групповых коммуникаций (“горизонтальная”, соответствует таким средам, как Usenet, списки рассылок, форумы) и модель персональных коммуникаций (“диагональная”, соответствует e-mail).

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

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

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

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

На настоящий момент созданная автором система P2PWL действует на нескольких серверах и доступна по адресу http://oc-co.org/p2pwl.

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

3

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ Разработана репутационная аксиоматика на основе нечетких множеств. На базе аксиоматики построены горизонтальная и диагональная модели информационных пространств со встроенными метриками репутации. Полученные и привлеченные результаты по сложности маршрутизации, распространения и поиска информации в безмасштабных графах убедительно свидетельствуют в пользу вывода о практической применимости горизонтальной и диагональной моделей в сетях с произвольно большим количеством участников.

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

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

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

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

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

С. 198.

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

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

Изд-во МГУ: Москва, 2002. С. 62–64.

5. V. S. Grishchenko. Redefining web-of-trust: reputation, recommendations, responsibility and trust among peers // Proceedings of the First Workshop on Friend of a Friend, Social Networking and the Semantic Web.

National University of Ireland, Galway. 2004. Р. 75–84.

6. V. S. Grishchenko. A fuzzy model for context-dependent reputation // Proceedings of the International Semantic Web Conference 2004 Workshop on Trust, Security, and Reputation on the Semantic Web. Hiroshima, 2004.

(Электронное издание CEUR Workshop Proceedings, ISSN 1613-0073, Vol 127) 7. V. S. Grishchenko. Computational complexity of one reputation metric // Proceedings of IEEE/Create-Net SecureComm 2005 Workshops.

SECOVAL Workshop. Athens, 2005. (Электронное издание, ISBN 0-78039469-0.) 8. V. S. Grishchenko. Distance-based reputation metrics are practical in p2p environments // International Journal of Metadata, Semantics and Ontologies. 2006. Vol. 1, № 2. P. 133–140.

Список литературы [1] Abdul-Rahman A., Hailes S. A distributed trust model // NSPW ’97:

Proceedings of the 1997 workshop on New security paradigms. New York, NY, USA: ACM Press, 1997. P. 48–60.

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

[3] Anderson C. The Long Tail. Random House Business Books, 2006.

July.

[4] Chord: a scalable peer-to-peer lookup protocol for internet applications / I. Stoica, R. Morris, D. Liben-Nowell et al. // IEEE/ACM Trans.

Netw. 2003. Vol. 11, no. 1. P. 17–32.

[5] Cohen B. Incentives build robustness in bittorrent.

http://www.bittorrent.org/bittorrentecon.pdf.

[6] Despotovic Z., Aberer K. P2p reputation management: Probabilistic estimation vs. social networks // Computer Networks. 2006.

March. Vol. 50, no. 4. P. 485–500.

[7] Evaluating collaborative filtering recommender systems / J. L. Herlocker, J. A. Konstan, L. G. Terveen, J. T. Riedl // ACM Trans. Inf. Syst. 2004. Vol. 22, no. 1. P. 5–53.

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

[9] Kamvar S. D., Schlosser M. T., Garcia-Molina H. The eigentrust algorithm for reputation management in p2p networks // WWW ’03: Proceedings of the 12th international conference on World Wide Web. New York, NY, USA: ACM Press, 2003. P. 640–651.

http://portal.acm.org/citation.cfmid=775242.

[10] Marti S., Garcia-Molina H. Taxonomy of trust: Categorizing p2p reputation systems // Computer Networks. 2006. March. Vol. 50, no. 4. P. 472–484.

[11] Massa P., Avesani P. Controversial users demand local trust metrics:

An experimental study on epinions.com community. // Proc. of Twentieth National Conference on Artificial Intelligence (AAAI-05), Pittsburgh, Pennsylvania. 2005. P. 121–126. http://dblp.unitrier.de/db/conf/aaai/aaai2005.html#MassaA05.

[12] Odlyzko A. Tragic loss or good riddance the impending demise of traditional scholarly journals // Intern. J. Human-Computer Studies.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»