ФЕДЕРАЛЬНОЕ АГЕНСТВО ПООБРАЗОВАНИЮ
Государственноеобразовательное учреждение
высшего профессиональногообразования
“САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
Механико-математическийфакультет
Кафедра информатики и вычислительной математики
Специальность “прикладнаяматематика”
МоделированиеWeb-графа.
Курсовая работа
Выполнил студент
4 курса группы 1241
Труфанов АлександрНиколаевич
_____________________________
Научный руководитель
Борисова С. П.
_____________________________
Работа защищена
“______”_________________2006г.
Оценка________________________
Зав. кафедрой
д.ф.-м.н., профессор
Степанов А.Н.
______________________________
Самара 2006
Оглавление.
TOC o «1-5» h z u Введение.PAGEREF _Toc105251122 h 3
Web-граф. Применение и ценность исследования.PAGEREF _Toc105251123 h 3
Этапыизучения web-графа иего моделирование.PAGEREF _Toc105251124 h 4
Целии задачи этой работы.PAGEREF _Toc105251125 h 7
МоделиWeb-графа.PAGEREF _Toc105251126 h 8
МодельACL.PAGEREF _Toc105251127 h 8
Модель“Развивающейся” сети.PAGEREF _Toc105251128 h 10
Копирующаямодель сети.PAGEREF _Toc105251129 h 12
Модель“Растущей сети”.PAGEREF _Toc105251130 h 13
Многослойнаямодель.PAGEREF _Toc105251131 h 14
Заключение.PAGEREF _Toc105251132 h 16
Библиография.PAGEREF _Toc105251133 h 17Введение.
Web-граф. Применение и ценность исследования.
Под Web-графом понимается орграф,вершинами которого являются документы (в основном статические html страницы) сети Интернет, а дугами –гипертекстовые ссылки между ними. Изучение его свойств представляет большойнаучный интерес и имеет огромную практическую ценность. Основная областьприменения накопленных о Web-графеданных – информационно поисковые системы (ИПС), такие как Google, MSN, Altavista.
Подавляющеебольшинство запросов пользователей содержат не более 3-5 слов, и числорелевантных им документов измеряется десятками тысяч. Естественно, пользователюпредоставляются ссылки на первые 10-15 самых “лучших” страниц. Ранжированиерезультатов поиска производится по присвоенным им рейтингам. Существуетогромное число алгоритмов, для определения “важности” ресурса сети. Прорывом вметодах ранжирования стал алгоритм PageRank [1] компании Google: превосходя конкурентов более качественным поиском, онабыстро стала лидером рынка. На данный момент ни одна крупная ИПС не можетобойтись без подобного алгоритма. PageRank в качестве рейтинга страницы использует взвешенноеотношение суммы рейтингов ссылающихся на страницу ресурсов к количествуисходящих из них ссылок. Реализация подобного подхода невозможна безиспользования web-графа.
Наряду с web-графом исследуются такжетакие структуры как:
· Хост-граф(Host graph).Орграфвершинами которого являются webузлы. Дуга между вершинами Aи B существует, еслисуществует хоть одна webстраница узла A имеющая гипертекстовую ссылку на одну из web страниц узла B.
· Cosine-граф(Cosine graph).Неориентированныйграф, вершинами которого являются web узлы. А дуги имеют вес равный cosine дистанции между векторамитерминов соответствующих страниц
· Графцитирования(Co-citation graph).Неориентированный граф вершинами которого являются web узлы. Весом дуги E(x,y) между вершинами x и yявляется число страниц ссылающихся и на страницу x и на страницу y.
· Пиринговый граф (Gnutellagraph). Орграф, вершинамикоторого являются хосты пиринговых программ, таких как Gnutella, Napster, Morpheus и т.п. А дугами – соединениямежду ними.
· Интернет-граф(Internet graph). Неориентированныйграф, представляющий физическое соединение компьютеров в Интернет.
· Коммуникационный граф (Communicationgraph).Взвешенный неориентированный граф, вершинами которого являются хосты, а дугами– соединения между ними. Весом дуги является количество информации проходящейпо соответствующей линии связи.
· Роутингграф(Routing graph).Представляетдвижение пакетов в сети Интернет.
Удивительно, но web-граф имеет во многомсхожие свойства со многими вышеперечисленными структурами.
Одним изнаправлений в исследовании web-графаявляется его моделирование. Получить Web-граф всей сети невозможно – размеры ее огромны. Каждая ИПСимеет сеть роботов-пауков, производящих индексирование ресурсов сети инакапливающих информацию о них в специальных хранилищах данных. Со временемпоявляются новые ресурсы, исчезают, либо перемещаются уже проиндексированные –поэтому, процесс исследования сети пауками непрерывен. Периодически происходитобновление рабочей базы данных ИПС (раз в 1-2 недели, для крупных ИПС – раз вмесяц). В настоящий момент наибольшим числом проиндексированных сайтов можетпохвастаться компания Google — .... Непроиндексированными же остаютсямногочисленные форумы, блоги, файлы неподдерживаемых форматов, динамическисоздаваемые и просто труднодоступные для пауков страницы. Эту часть сетипринято называть невидимой (“InvisibleWeb”).По различным оценкам, она превосходит видимую часть от 10 до 500 раз.
Многие ИПС, заинтересованные в более качественномранжировании результатов поиска, предоставляют данные, собранные пауками, дляизучения. Но размеры этих данных делают эксперименты над ними чрезвычайнотрудоемкими, что затрудняет созданиеэффективных алгоритмов. Работа с полноценным web-графом может вестись только на высокопроизводительныхсерверах. Для примера, приведем сведения о экспериментальных данных,использованных при создании алгоритма BlockRank [2]. Работа алгоритма на web-графе, созданном в рамках проекта “Stanford WebBase” в январе 2001г., размером в290 млн. вершин и чуть более миллиарда дуг, на AMD Athlon 1533MHz с дисковыммассивом RAID-5 и3.5Гб оперативной памяти, требовала около 100 итераций по 7минут каждая. Представление web-графана внешних носителях потребовало 6Гб памяти, и это – очень небольшой web-граф.
На практикеиспользуют “мини” web-графы,сгенерированные на основе некоторой модели. Основная задача моделирования web-графа – охватить все егоособенности, в связи с этим, создание новой модели обычно являлось ответом наобнаружение неизвестных свойств web-графа.Рассмотрим основные, известные на данный момент, свойства web-графа и модели, их отражающие:
Этапыизучения web-графа и егомоделирование.
· web-графа являлась модель Erdös-Renyi [3]. Конечные вершины для исходящих дуг в этой моделивыбираются случайным образом из всех вершин графа. В частности, длямоделирования web-графаприменялась модель с среднем числом исходящих из каждой вершины дуг равным 7.Более глубокий анализ полученных на практике данных показал неадекватностьмодели Erdös-Renyi настоящим web-графам.
· R. Kumar[4] и независимо A.L. Barabasi и A. Albert [5] обнаружили, что число входящих в вершину дуг имеет экспоненциально распределение скоэффициентом 2.1. Также ими было выдвинуто предположение о том что и числоисходящих дуг имеет экспоненциальное распределение с коэффициентом 2.7. Следуетотметить, что последнее утверждение не является бесспорным [6].
· Aiello, Chung и Lu[7], хотя она и предназначена для отображения трафика телефонных звонков.[1]Немного позднее Albert,BarabasiandJeong[8] предложили модель “Развивающейся сети”,в которой на каждой итерации к графу добавляется новая вершина и соединяется снекоторым числом вершин графа. Если выбрать эту константу равной 7-и, токоэффициент распределения будет около 2.
· A. Border[9] обнаружил удивительное свойство web-графа. На макроскопическом уровне он имеет структуру“бабочки”. Ее центром является группа страниц, образующих компонент сильнойсвязности (SCC). Такжеимеются страницы, ссылающиеся на центральную группу (IN), страницы на которые ссылается центральнаягруппа (OUT) и группанесвязных с ними страниц. Существуют также “трубы” – ссылки между “крыльями”бабочки. В web-граферазмером 200 млн. страниц, предоставленным компанией Alexa в 1997г. было обнаружено свыше100000 подобных сообществ.
рис1. Структура “бабочки”.
· A. Borderпоказал, что вероятность существования пути между двумя случайно выбраннымивершинами web-графаравна 24%, а средняя длина такого пути равна 16.
· J.Kleinberg [10]и D. Watts [11] был обнаружен свойственный web-графу феномен “Малого мира” (Smallworldphenomen), типичный для динамических социальныхсетей.[2]За исключением небольшого процента дуг, почти все страницы достижимы из любойдругой через огромный центральный компонент связности, объединяющий около 90%вершин web-графа.
· Вструктуре web-графа также быловыделено удивительно большое число специфических топологических структур, такихкак двудольные клики небольшого размера (3-10 страниц). Это связывают сналичием неявных кибер-сообществ: групп ресурсов сходной тематики, имеющихобщие “авторитетные” страницы. Двудольные клики интерпретируются как ядроподобных сообществ – они состоят из множества “фанатских” и “авторитетных”страниц, причем все страницы из первого множества ссылаются на страницывторого.[3]
· Дляреализации вышеназванных свойств, в частности существования кибер-сообществ R. Kumar[12] в 2000г. предложил “Копирующую модель”. Она похожа на модельразвивающейся сети, но новые вершины соединяется с некоторым постоянным числомуже имеющихся вершин с некоторой вероятностью. (т.н. фактор копирования) Авторпредложил 2 модификации алгоритма: в первой на каждой итерации добавляетсяпостоянное (обычно 1) число вершин (линейная модель), во второй – это числоявляется функцией от текущего размера сети (экспоненциальная модель).
рис2. Двудольная клика.
· В видуособой практической важности PageRankи ему подобных алгоритмов G.Pandurangan, P. Raghavan, и E. Upfalизучили распределение рейтинга PageRank(PR) в web-графе. Их исследование показало, что распределениеPR, также как и числоссылающихся страниц, подчиняется экспоненциальному закону с коэффициентом 2.1,но корреляция между этими параметрами очень невелика, а значит, страница сбольшим количеством входящих ссылок может получить очень низкий PR. Подобный результат очень обрадовал ИПС, вчастности Google, ведущуюпостоянную борьбу с компаниями-оптимизаторами сайтов (SEO).
· Основываясьна данных о распределении PageRankи числа ссылающихся страниц, G.Pandurangan, P. Raghavanи E.Upfal[13] предложили т.н. PageRankмодель, являющуюся обобщением моделиразвивающейся сети. В ней вводятся 2 параметра и i-й дуги, соединяющая ее с новой добавляемой вершиной, свероятностью будет выбираться свероятностью, пропорциональной числу входящих в нее дуг (преференциальноедобавление); с вероятностью она выбирается свероятностью пропорциональной ее PageRank; и с вероятностью случайным образом(единообразное добавление). С помощью компьютерной симуляции авторам удалосьпоказать, что при правильно подобранных коэффициентах генерируемый данноймоделью граф обладает свойствами распределения и числа входящих дуг и PageRank.
· 2002г. D.M. Pennock,G.W. Flake идр. [14] установили, что законраспределения числа входящих дуг для таких групп страниц, как домашние сайтыстудентов университета, или все страницы сайтов новостей, испытывают значительныеотклонения от экспоненциального закона в различной для каждой группы степени. Вэтой же работе, они предложили модель “Растущей сети”, являющуюся комбинациейединообразных и преференциальныхдобавлений вершин с коэффициентом вероятности меняя
· S.Dill в своей работе[15] исследовал различные фрактальные свойства web-графа. Граф может быть рассмотренкак производная нескольких независимых стохастических процессов. Изучая различныеcohesive группы страниц(напр. страницы, принадлежащие одному сайту, или страницы общей тематики), былообнаружено подобие их структуры структуре всего графа (структура “бабочки”,экспоненциальный закон распределения числа ссылающихся страниц). Центральнаячасть структуры этих коллекций была названа “Тематически ОбъединеннымКластером” (Thematically Unified Cluster" (TUC)).
рис3. Самоподобие web-графа.
· Дляреализации фрактальных свойств web-графа,L. Laura, S.Leonardiи др. [16] в2002г. предложили “Многослойная модель”. Она позволяет одновременноеиспользование 2-х и более моделей, рассмотренных ранее, и подробно освещается вданной работе.
Цели и задачи этой работы.
В данной работе описаны наиболее актуальные модели web-графа, позволяющие получитькомпактные наборы данных, максимально полно отражающие структуру и особенности web. Эти данные делаютдоступными эксперименты с алгоритмами исимуляциями, использующими в своей работе ссылочную структуру сети (от PageRank и выделениякибер-собществ до моделирования распространения вирусов в реальных сетях).
Наиболее удачные модели были реализованы в среде Delphi в видебыстродействующих консольных утилит.
Модели Web-графа.Модель ACL.
Модель ACLзависит от2-х параметров: и положим, что мы имеем в графе yвершинстепени x > 0[4], где xи yудовлетворяютследующему равенству:
Таким образом, мы имеем:
,
По сути, — это логарифм числавершин степени 1, а — двойнаялогарифмическая оценка убывания числа вершин заданной степени. Из формулывидно, что y – действительноечисло. На практике используют :
·
·
где
·
Для создания графа необходимопоступить следующим образом:
1. и рекомендуется братьблизким к 1.
2.
3.
4. L, состоящий из deg(vi) копий вершин vi, i=1..n.
5. L.
6. u и vграфа,число дуг соединяющих эти вершины будет равно числу соответствий всех копийвершины uкопиям вершины vнабора L.
Результатом модели будетмультиграф, который может содержать петли. Прообразом для модели служил т.н. call-граф – графмеждугородних телефонных звонков, произведенных за некоторый длительныйпромежуток времени (например, сутки). Для генерации web-графа эта модель не используется, нооказала большую помощь в его изучении этой проблемы.Модель“Развивающейся” сети.
Модель представляет собойитерационный процесс, в котором на каждой итерации к web-графу добавляется по одной вершине.Пусть функция indegree(v) возвращает число входящихв вершину v дуг. Тогдановая вершина wсоединяется с вершинами vkграфа с вероятностью пропорциональной indegree(vk) (преференциальноедобавление).
Для реализации модели,используется массив I[k] хранящий значения indegree(vk) + 1. Обозначим число ужедобавленных к web-графувершин g. Пусть I – сумма значений indegree всех вершин +количество вершин.
Все добавляемые вершины получаютфиктивное значение indegreeравное 1, что позволяет им быть выбранным в качестве конечной вершины дуги.Поэтому к I и былодобавлено g.
Добавим к web-графу вершину w. Выберем случайное число r от 1 до I. Затем найдем вершину vk с наименьшим k, для которого выполняетсяследующее:
Вершина vk выбирается конечнойвершиной новой дуги, а значение I[k] увеличивается на 1.Начальной вершиной дуги является добавленная вершина w.
При генерации массивных web-графов возникают дветрудности:
· I[j], что затруднительно при большом числевершин.
· vk существеннозамедляется.
Для решения вышеописанных проблемиспользуется следующее усовершенствование алгоритма:
В оперативной памяти хранитсявспомогательный массив Sиз элементов. Каждыйэлемент массива Sхранит сумму значений indegreeдля вершин. Т.о. , и т.д.Множество из вершин назовем блоком.Алгоритм генерации web-графапринимает следующий вид:
Фаза 1.
В оперативной памяти хранятся картежи tk, описывающиедуги, для которых известна начальная вершина, но не найдена конечная. Каждыйкартеж хранит номер блока, в котором находится конечная вершина дуги.
Пусть с – добавляемая вершина,она и будет являться начальной для новой дуги. Выберем случайное число r от 1 до I, где g = с – 1. Затем необходимоопределить блок, в котором находится конечная вершина. Для этого найдемнаименьшее k’, длякоторого выполняется следующее:
В память записывается картеж t , где за относительную позициювнутри блока принимается разность числа r и суммы значений indegree всех блоков, предшествующих найденному. Добавлениевершин и генерация картежей продолжается до заполнения заданного объема памяти.
Фаза 2.
Создание дуг и запись их во внешнюю память.Для каждого блока ищутся все картежи, которые ссылаются на один блок. Затемэтот блок загружается в оперативную память и в нем ищется конечные вершиныописанных картежами дуг. Полученные дуги пишутся в буфер, выгружаемый вовнешнюю память по мере заполнения, а значение indegree их конечных вершинувеличивается. Фаза завершает работу, когда для всех картежей будутсгенерированны дуги.
На практике часто используютмногоуровневую систему блоков и специальные структуры, ускоряющие поиск вершинывнутри них.Копирующаямодель сети.
На каждой итерации алгоритма к web-графу добавляется поодной вершине. Для каждой новой вершины v выбирается вершина-прототип p. Для всех исходящих из v дуг, с вероятностью конечная вершинавыбирается среди всех вершин графа (“единообразный” выбор), а, с вероятностью p (“копирование” дуги).
Отличительной особенностью этоймодели является необходимость в большом числе операций чтения/записи из внешнейпамяти:
1.
2.
Для сокращения числа обращений квнешней памяти применяют модификацию модели, не требующей считывания копируемыхдуг.
Пусть L – некоторое фиксированное числоисходящих дуг. Сгенерируем для каждой вершины 1+2*L случайных чисел. Одно – для выбора вершины-прототипа, L – для конечных вершин,выбираемых “единообразно” и Lзначений p, можно “вернуться” к моментудобавления p к графу и“пересчитать” исходящие из него дуги. Это может привести к цепи вычислений, новсе они достаточно просты и проводятся в оперативной памяти, что заметноускоряет работу алгоритма.
Результаты работы алгоритмазаписываются в буфер. При заполнении буфера, его содержимое переносится вовнешнюю память, а сам буфер очищается.
Описанная выше модель являетсялинейной. Существует ее т.н. “экспоненциальная” модификация, при которой накаждой итерации к web-графудобавляется не одна, а kвершин. Где k – функция,зависящая от размера графа.Модель “Растущейсети”.
Модель была предложена в 2002г. D.M. Pennock иG.W. Flake. В своей работеони исследовали структуры web-графа, образованные тематическими наборами страниц. Ихисследования показали, что распределение значений indegree в этих множествахсильно отличаются от экспоненциального. Распределение числа ссылающихся страницв подобных группах более всего походит на “унимодальное с экспоненциальнымхвостом”. Авторы выдвинули гипотезу, что экспоненциальный закон распределенияявляется скорее исключением, чем правилом. Для реализации web-графа на уровне группстраниц с подобным распределением и была разработана модель “Растущей сети”.
Пусть мы имеем некий начальный граф,содержащий m0вершин. На каждой итерации t к нему будет добавляться поодной вершине и m дуг. В модели развивающейся сети все m дуг соединяют новую вершинусо старыми преференциально: Вероятность П(ki) того, что дуга соединитвершину i пропорциональна ki, где ki – текущее число дуг, инцидентных i.
В этой модели у всех вершин есть некаябазовая вероятность быть соединенной с новой вершиной (единообразноедобавление). Поэтому, вероятность соединения i-той вершины с новой, можновыразить следующей формулой:
где m0 + t – число вершин, а 2mt – число дуг графа на t-й итерации.
При преференциальном добавлении, страницы накоторые указывают множество ссылок имеют большее предпочтение при добавлениидуги. При единообразном – все страницы равноценны. Баланс между этимипринципами дает более адекватную модель графа, т.к. web-дизайнеры при созданииссылок руководствуются 2 принципами:
·
·
При устремлении параметра a к 1 или m к 1 закон распределениячисла входящих ссылок вновь станет близок к экспоненциальному. Многослойная модель.
Как и все вышеописанные модели,многослойная модель является итерационной. В этой модели web-граф рассматривается как объединениенескольких регионов, называемых слоями. На каждой итерации t к графу добавляется вершина x, и ей присваиваютсяфиксированное число lрегионов и d дуг,соединяющих x свершинами графа.
рис.Многослойная модель графа.
Пусть Xi(t) – число вершин принадлежащих i-му слою на t-ой итерации.
L(x) – набор слоев, связанных с вершиной x.
Для связывания вершины x со слоями, в цикле l раз необходимо выполнитьследующую операцию:
, где i– слой, выбираемый из множества L/L(x) с вероятностью, пропорциональной Xi(t) с некоторым нормализующимфактором.
При генерации дуг припреференциальном добавлении рассматриваются только вершины одного слоя. Этопозволяет генерировать слои “независимо” друг от друга. В связи с этим вмногослойной модели выделяют 2 процесса: “поведение вне слоя” (extra-layerbehavior) и “поведение внутрислоя” (intra-layerbehavior).
Подобная независимость позволяетиспользовать для формирования слоев различные модели (Развивающейся сети,Копирующую модель, модель Роста сети и т.д.). При этом часть слоев можетгенерироваться одной моделью, а часть – другой.
В данной работе мы рассмотримт.н. “гибридную” модель формирования слоев. Она была предложена авторамимногослойной модели [16] и обладает большой устойчивостью при вариациипараметров. “Гибридная” модель является сочетанием “Развивающейся” и “Линейнойкопирующей” моделей.
Между l слоями равномерно распределяются d дуг. Пусть с = [d/x] и — параметр копирования.В каждом слое i, скоторым связана вершина x,она будет иметь с или с + 1 исходящую дугу, к которой необходимо подобратьконечную вершину. Обозначим за множество из Xi(t) вершин слоя i. Т.о. слой i будет состоять из вершинмножества и дуг между ними,созданных за t-1итерацию. Выберем из прототип p. Соединим x с помощью с дуг с вершинами множества следующим образом:
Для l-я дуга соединяется с конечной вершинойl-й дуги прототипа p. Иначе, концом l-й дуги выбирается одна изеще на связанных с xвершин множестваindegree + 1.Если прототип имеет лишь с исходящих дуг, а необходимо создать c+1, то она берется вторымспособом.Заключение.
Моделирование web-графа уже долгое время являетсясамостоятельным и очень динамично развивающимся направлением исследований.Публикации, посвященные данной теме, появляются с завидной регулярностью. Такжене может не радовать их доступность – подавляющее большинство из них можнонайти в сети.
В последнее время активно обсуждаетсявозможность модификации вышеописанных моделей: разрабатываются мех