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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Кафедра информатики и вычислительной математики Специальность прикладная математика Моделирование Web-графа.Курсовая работа Выполнил студент 4 курса группы 1241 Труфанов Александр Николаевич Научный руководитель Борисова С. П. Работа защищена 2006г. Оценка Зав. кафедрой д.ф м.н профессор Степанов А.Н. Самара 2006 Оглавление. Введение. 3 Web-граф. Применение и ценность исследования. 3 Этапы изучения web-графа и его моделирование. 4 Цели и задачи этой работы. 7 Модели Web-графа. 8 Модель ACL. 8 Модель Развивающейся сети. 10 Копирующая модель сети. 12 Модель Растущей сети. 13 Многослойная модель. 14 Заключение. 16 Библиография. 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 узлы. Весом дуги Ex, y между вершинами x и y является число страниц ссылающихся и на страницу x и на страницу y. Пиринговый граф Gnutella graph.

Орграф, вершинами которого являются хосты пиринговых программ, таких как Gnutella, Napster, Morpheus и т.п. А дугами соединения между ними. Интернет-граф Internet graph. Неориентированный граф, представляющий физическое соединение компьютеров в Интернет. Коммуникационный граф Communication graph. Взвешенный неориентированный граф, вершинами которого являются хосты, а дугами соединения между ними. Весом дуги является количество информации проходящей по соответствующей линии связи.

Роутинг граф Routing graph. Представляет движение пакетов в сети Интернет. Удивительно, но web-граф имеет во многом схожие свойства со многими вышеперечисленными структурами. Одним из направлений в исследовании web-графа является его моделирование. Получить Web-граф всей сети невозможно размеры ее огромны. Каждая ИПС имеет сеть роботов-пауков, производящих индексирование ресурсов сети и накапливающих информацию о них в специальных хранилищах данных.

Со временем появляются новые ресурсы, исчезают, либо перемещаются уже проиндексированные поэтому, процесс исследования сети пауками непрерывен. Периодически происходит обновление рабочей базы данных ИПС раз в 1-2 недели, для крупных ИПС раз в месяц. В настоящий момент наибольшим числом проиндексированных сайтов может похвастаться компания Google - Непроиндексированными же остаются многочисленные форумы, блоги, файлы неподдерживаемых форматов, динамически создаваемые и просто труднодоступные для пауков страницы.

Эту часть сети принято называть невидимой Invisible Web. По различным оценкам, она превосходит видимую часть от 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-графа и его моделирование

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

Цели и задачи этой работы

Эти данные делают доступными эксперименты с алгоритмами и симуляциями,... В среде Delphi 7 мною была реализована Многослойная модель, использующ... Если это не так, то можно добавить к графу вершину степени 1, но далее... 5. Выбрать случайное соответствие элементов в L.

Копирующая модель сети

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

Заключение

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

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

Также активно изучаются фрактальные свойства web-графа, его структурную эволюцию и влияние на нее большого числа появившихся за последние годы сервисов напр. живые журналы, блоги, реферальные услуги и on-line игры. Возможно, глубокий анализ web-графа уже сейчас позволит нам заглянуть в будущее и узнать, на что будет похожа web через 3, 5, 10 лет, какие проблемы и перспективы нас ждут. Растет и число программных продуктов, позволяющих генерировать качественные наборы данных.

Особенно хочется отметить пакет WebGraph Framework II 17. Он разработан группой ученых на платформе Java и содержит в себе не только механизмы генерации web-графов, но и различные инструменты и алгоритмы для работы с ними. Для хранения данных используется специально разработанное кодирование, позволяющее экономить внешнюю память, а также механизм, на лету определяющий необходимость извлечения данных из архива и их объем. 18

Библиография

Библиография . 1. S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engines.

In Proceedings of the 7th WWW Conference, 1998. 2. S. D. Kamvar, T. H. Haveliwala, C. D. Manning, G. H. Golub. Exploiting the Block Structure of theWeb for Computing PageRank. Stanford University. 3. P. Erdцs, Renyi R. Publ. Math. Inst. Hung. Acad. Sci, 5, 1960. 4. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the web for emerging cyber communities. In Proc. of the 8th WWW Conference, pages 403-416, 1999. 5. A.L. Barabasi and A. Albert.

Emergence of scaling in random networks. Science, 286509, 1999. 6. G. Caldarelli, P. De Los Rios, L. Laura, S. Leonardi, S.Millozzi. A study of stochastic models for the Web Graph. 2003 7. W Aiello, F Chung, and L Lu. A random graph model for massive graphs. In Proc. ACM Symp. on Theory of computing, pages 171180, 2000. 8. R. Albert, H. Jeong, and A.L. Barabasi. Nature, 401130, 1999. 9. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, S. Stata, A. Tomkins, and J. Wiener.

Graph structure in the web. In Proceedings of the 9th WWW conference, 2000. 10. D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature, 393440, 1998. 11. J. Kleinberg. The small world phenomenon an algorithmic perspective. 12. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Proc. of 41st FOCS, 2000. 13. G. Pandurangan, P. Raghavan, and E. Upfal. Using pagerank to characterize web structure. 14. D.M. Pennock, G.W. Flake, S. Lawrence, E.J. Glover, and C.L. Giles. Winners dont take all Characterizing the competition for links on the web. Proc. of the National Academy of Sciences, April 2002. 15. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, and A. Tomkins.

Self-similarity in the web. In Proceedings of the 27th VLDB Conference, 2001. 16. L. Laura, S. Leonardi, G. Caldarelli, and P. De Los Rios. A multi-layer model for the webgraph.

In On-line proceedings of the 2nd International Workshop on Web Dynamics 2002. 17. Paolo Boldi, Sebastiano Vigna. The Web Graph Framework III. Technical Reports 293-03294-03, Universitа di Milano, Dipartimento di Scienze dell Informazione, 2003. Available at httpwebgraph.dsi.unimi.it. 18. Paolo Boldi, Sebastiano Vigna. The Web Graph Framework II Codes For The World Wide Web.