Моделирование Web-графа

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

[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-х и более моделей, рассмотренных ранее, и подробно освещается в данной работе.

[4], где xи yудовлетворяют следующему равенству:

Таким образом, мы имеем:

,

По сути, - это логарифм числа вершин степени 1, а - двойная логарифмическая оценка убывания числа вершин заданной степени. Из формулы видно, что y – действительное число. На практике используют :

·

·

где

·

Для создания графа необходимо поступить следующим образом:

1.и рекомендуется брать близким к 1.

2.

3.

4.L, состоящий из deg(v_i) копий вершин v_i, i= 1..n.

5.L.

6.u и vграфа, число дуг соединяющих эти вершины будет равно числу соответствий всех копий вершины uкопиям вершины vнабора L.

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

http://webgraph.dsi.unimi.it/.

Paolo Boldi, Sebastiano Vigna. The Web Graph Framework II: Codes For The World–Wide Web

[1] Граф, при таком подходе, является неориентированным.

[2] Дуги web-графа должны быть неориентированными.

[3] Наряду с неявными, различают также явные кибер-сообщества: кольца (webrings), службы новостей и группы, образованные клиентами пиринговых сетей.

[4] Вершины степени 0 являются изолированными и обычно не рассматриваются, т.к. на практике они не встречаются.