рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Этапы изучения web-графа и его моделирование

Работа сделанна в 2006 году

Этапы изучения web-графа и его моделирование - Курсовая Работа, раздел Связь, - 2006 год - Моделирование Web-графа. Этапы Изучения Web-Графа И Его Моделирование. Первой Моделью Web-Графа Являла...

Этапы изучения web-графа и его моделирование. Первой моделью web-графа являлась модель Erdцs-Renyi 3. Конечные вершины для исходящих дуг в этой модели выбираются случайным образом из всех вершин графа. В частности, для моделирования web-графа применялась модель с среднем числом исходящих из каждой вершины дуг равным 7. Более глубокий анализ полученных на практике данных показал неадекватность модели Erdцs-Renyi настоящим web-графам.

В 1999г. R. Kumar 4 и независимо A.L. Barabasi и A. Albert 5 обнаружили, что число входящих в вершину дуг имеет экспоненциально распределение с коэффициентом 2.1. Также ими было выдвинуто предположение о том что и число исходящих дуг имеет экспоненциальное распределение с коэффициентом 2.7. Следует отметить, что последнее утверждение не является бесспорным 6. Первой моделью, реализовавшая это свойство считается модель Aiello, Chung и Lu 7, хотя она и предназначена для отображения трафика телефонных звонков.

Граф, при таком подходе, является неориентированным. Немного позднее Albert, Barabasi and Jeong 8 предложили модель Развивающейся сети, в которой на каждой итерации к графу добавляется новая вершина и соединяется с некоторым числом вершин графа.

Если выбрать эту константу равной 7-и, то коэффициент распределения будет около 2. В том же году A. Border 9 обнаружил удивительное свойство web-графа. На макроскопическом уровне он имеет структуру бабочки. Ее центром является группа страниц, образующих компонент сильной связности SCC. Также имеются страницы, ссылающиеся на центральную группу IN, страницы на которые ссылается центральная группа OUT и группа несвязных с ними страниц.

Существуют также трубы ссылки между крыльями бабочки. В web-графе размером 200 млн. страниц, предоставленным компанией Alexa в 1997г. было обнаружено свыше 10 подобных сообществ. рис 1. Структура бабочки. Также A. Border показал, что вероятность существования пути между двумя случайно выбранными вершинами web-графа равна 24, а средняя длина такого пути равна 16. В работах J. Kleinberg 10 и D. Watts 11 был обнаружен свойственный web-графу феномен Малого мира Small world phenomen, типичный для динамических социальных сетей.

Дуги web-графа должны быть неориентированными. За исключением небольшого процента дуг, почти все страницы достижимы из любой другой через огромный центральный компонент связности, объединяющий около 90 вершин web-графа. В структуре web-графа также было выделено удивительно большое число специфических топологических структур, таких как двудольные клики небольшого размера 3-10 страниц. Это связывают с наличием неявных кибер-сообществ групп ресурсов сходной тематики, имеющих общие авторитетные страницы.

Двудольные клики интерпретируются как ядро подобных сообществ они состоят из множества фанатских и авторитетных страниц, причем все страницы из первого множества ссылаются на страницы второго. Наряду с неявными, различают также явные кибер-сообщества кольца webrings, службы новостей и группы, образованные клиентами пиринговых сетей. Для реализации вышеназванных свойств, в частности существования кибер-сообществ 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-графом понимается орграф, вершинами которого являются документы в основном статические html страницы сети Интернет, а дугами гипертекстовые… Подавляющее большинство запросов пользователей содержат не более 3-5 слов, и… Естественно, пользователю предоставляются ссылки на первые 10-15 самых лучших страниц.Ранжирование результатов поиска…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Этапы изучения web-графа и его моделирование

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Цели и задачи этой работы
Цели и задачи этой работы. В данной работе описаны наиболее актуальные модели web-графа, позволяющие получить компактные наборы данных, максимально полно отражающие структуру и особенности w

Копирующая модель сети
Копирующая модель сети. На каждой итерации алгоритма к web-графу добавляется по одной вершине. Для каждой новой вершины v выбирается вершина-прототип p. Для всех исходящих из v дуг, с вероятностью

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги