Моделирование Web-графаОценка________________________ Зав. кафедрой д.ф.-м.н., профессор Степанов А.Н. ______________________________ Самара 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 . · Пиринговый граф ( 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 -графа и его моделирование. · 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 , Barabasi and Jeong [8] предложили модель “Развивающейся сети”, в которой на каждой итерации к графу добавляется новая вершина и соединяется с некоторым числом вершин графа. Если выбрать эту константу равной 7-и, то коэффициент распределения будет около 2. · A . Border [9] обнаружил удивительное свойство web -графа. На макроскопическом уровне он имеет структуру “бабочки”. Ее центром является группа страниц, образующих компонент сильной связности ( SCC ). Также имеются страницы, ссылающиеся на центральную группу ( IN ), страницы на которые ссылается центральная группа ( OUT ) и группа несвязных с ними страниц. Существуют также “трубы” – ссылки между “крыльями” бабочки. В web -графе размером 200 млн. страниц, предоставленным компанией Alexa в 1997г. было обнаружено свыше 100000 подобных сообществ. Двудольные клики интерпретируются как ядро подобных сообществ – они состоят из множества “фанатских” и “авторитетных” страниц, причем все страницы из первого множества ссылаются на страницы второго. [3] · Для реализации вышеназванных свойств, в частности существования кибер-сообществ R . Kumar [12] в 2000г. предложил “Копирующую модель”. Она похожа на модель развивающейся сети, но новые вершины соединяется с некоторым постоянным числом уже имеющихся вершин с некоторой вероятностью. (т.н. фактор копирования) Автор предложил 2 модификации алгоритма: в первой на каждой итерации добавляется постоянное (обычно 1) число вершин (линейная модель), во второй – это число является функцией от текущего размера сети (экспоненциальная модель). Изучая различные cohesive группы страниц (напр. страницы, принадлежащие одному сайту, или страницы общей тематики), было обнаружено подобие их структуры структуре всего графа (структура “бабочки”, экспоненциальный закон распределения числа ссылающихся страниц). Центральная часть структуры этих коллекций была названа “Тематически Объединенным Кластером” ( Thematically Uni fi ed Cluster' (TUC) ). Модели Web -графа. Модель ACL . Модель ACL зависит от 2-х параметров: Прообразом для модели служил т.н. call -граф – граф междугородних телефонных звонков, произведенных за некоторый длительный промежуток времени (например, сутки). Для генерации web -графа эта модель не используется, но оказала большую помощь в его изучении этой проблемы. Модель “Развивающейся” сети. Модель представляет собой итерационный процесс, в котором на каждой итерации к web -графу добавляется по одной вершине. Пусть функция indegree ( v ) возвращает число входящих в вершину v дуг. Тогда новая вершина w соединяется с вершинами v k графа с вероятностью пропорциональной indegree ( v k ) (преференциальное добавление). Для реализации модели, используется массив I [ k ] хранящий значения indegree ( v k ) + 1. Обозначим число уже добавленных к web -графу вершин g . Пусть I – сумма значений indegree всех вершин + количество вершин. Поэтому к I и было добавлено g . Добавим к web -графу вершину w . Выберем случайное число r от 1 до I . Затем найдем вершину v k с наименьшим k , для которого выполняется следующее: Каждый элемент массива S хранит сумму значений indegree для Множество из Алгоритм генерации web -графа принимает следующий вид: Фаза 1. В оперативной памяти хранятся картежи t k , описывающие дуги, для которых известна начальная вершина, но не найдена конечная. Каждый картеж хранит номер блока, в котором находится конечная вершина дуги. Пусть с – добавляемая вершина, она и будет являться начальной для новой дуги. Выберем случайное число r от 1 до I , где Добавление вершин и генерация картежей продолжается до заполнения заданного объема памяти. Фаза 2. Создание дуг и запись их во внешнюю память. Для каждого блока ищутся все картежи, которые ссылаются на один блок. Затем этот блок загружается в оперативную память и в нем ищется конечные вершины описанных картежами дуг. Полученные дуги пишутся в буфер, выгружаемый во внешнюю память по мере заполнения, а значение indegree их конечных вершин увеличивается. Фаза завершает работу, когда для всех картежей будут сгенерированны дуги. На практике часто используют многоуровневую систему блоков и специальные структуры, ускоряющие поиск вершины внутри них. Копирующая модель сети. На каждой итерации алгоритма к web -графу добавляется по одной вершине. Для каждой новой вершины v выбирается вершина-прототип p . Для всех исходящих из v дуг, с вероятностью Сгенерируем для каждой вершины 1+2* L случайных чисел. Одно – для выбора вершины-прототипа, L – для конечных вершин, выбираемых “единообразно” и L значений Результаты работы алгоритма записываются в буфер. При заполнении буфера, его содержимое переносится во внешнюю память, а сам буфер очищается. Описанная выше модель является линейной. Существует ее т.н. “экспоненциальная” модификация, при которой на каждой итерации к web -графу добавляется не одна, а k вершин. Где k – функция, зависящая от размера графа. Модель “Растущей сети”. Модель была предложена в 2002г. D.M. Pennock и G.W. Flake. В своей работе они исследовали структуры web -графа, образованные тематическими наборами страниц. Их исследования показали, что распределение значений indegree в этих множествах сильно отличаются от экспоненциального. Распределение числа ссылающихся страниц в подобных группах более всего походит на “унимодальное с экспоненциальным хвостом”. Авторы выдвинули гипотезу, что экспоненциальный закон распределения является скорее исключением, чем правилом. Для реализации web -графа на уровне групп страниц с подобным распределением и была разработана модель “Растущей сети”. Пусть мы имеем некий начальный граф, содержащий m 0 вершин. На каждой итерации t к нему будет добавляться по одной вершине и m дуг. В модели развивающейся сети все m дуг соединяют новую вершину со старыми преференциально: Вероятность П( k i ) того, что дуга соединит вершину i пропорциональна k i , где k i – текущее число дуг, инцидентных i . В этой модели у всех вершин есть некая базовая вероятность быть соединенной с новой вершиной (единообразное добавление). Поэтому, вероятность соединения i -той вершины с новой, можно выразить следующей формулой: Баланс между этими принципами дает более адекватную модель графа, т.к. web -дизайнеры при создании ссылок руководствуются 2 принципами: · · При устремлении параметра a к 1 или m к 1 закон распределения числа входящих ссылок вновь станет близок к экспоненциальному. Многослойная модель. Как и все вышеописанные модели, многослойная модель является итерационной. В этой модели web -граф рассматривается как объединение нескольких регионов, называемых слоями. На каждой итерации t к графу добавляется вершина x , и ей присваиваются фиксированное число l регионов и d дуг, соединяющих x с вершинами графа. Многослойная модель графа. Пусть X i ( t ) – число вершин принадлежащих i -му слою на t -ой итерации. L ( x ) – набор слоев, связанных с вершиной x . Для связывания вершины x со слоями, в цикле l раз необходимо выполнить следующую операцию: Обозначим за Выберем из Заключение. Моделирование web -графа уже долгое время является самостоятельным и очень динамично развивающимся направлением исследований. Публикации, посвященные данной теме, появляются с завидной регулярностью. Также не может не радовать их доступность – подавляющее большинство из них можно найти в сети. В последнее время активно обсуждается возможность модификации вышеописанных моделей: разрабатываются механизмы корректного изменения и удаления дуг и вершин, не ухудшающие свойства web -графа. Возможность подобных операций сделает модель более гибкой и позволит симулировать не только рост сети, но и ее распад. В свою очередь, это обеспечит изучение различных деструктивных процессов, таких как вирусная атака, отказ оборудования или просто резкое уменьшение числа пользователей некоторого сегмента web (например, в связи с прекращением работы какого-либо пирингового сервиса). Также активно изучаются фрактальные свойства web -графа, его структурную эволюцию и влияние на нее большого числа появившихся за последние годы сервисов (напр. “живые журналы”, блоги, реферальные услуги и on - line игры). Возможно, глубокий анализ web -графа уже сейчас позволит нам “заглянуть в будущее” и узнать, на что будет похожа web через 3, 5, 10 лет, какие проблемы и перспективы нас ждут. |
оценка ущерба экспертиза в Брянске
оценка недвижимости для наследства в Смоленске
Педагогика
Литература, Лингвистика
Технология
Микроэкономика, экономика предприятия, предпринимательство
Конституционное (государственное) право России
Гражданская оборона
География, Экономическая география
Теория государства и права
Социология
Гражданское право
История политических и правовых учений
Бухгалтерский учет
Маркетинг, товароведение, реклама
Биология
Техника
Политология, Политистория
Психология, Общение, Человек
Государственное регулирование, Таможня, Налоги
Экскурсии и туризм
Химия
Архитектура
Охрана природы, Экология, Природопользование
Теория систем управления
Компьютеры и периферийные устройства
Искусство
Экономическая теория, политэкономия, макроэкономика
Философия
Культурология
Транспорт
Ветеринария
Медицина
Астрономия, Авиация, Космонавтика
Сельское хозяйство
Менеджмент (Теория управления и организации)
Криминалистика и криминология
Уголовное право
Трудовое право
Радиоэлектроника
Международные экономические и валютно-кредитные отношения
Банковское дело и кредитование
Религия
Программное обеспечение
История
Материаловедение
Административное право
Военное дело
Физика
Физкультура и Спорт
Здоровье
Музыка
История отечественного государства и права
Конституционное (государственное) право зарубежных стран
История экономических учений
Право
Биржевое дело
История государства и права зарубежных стран
Историческая личность
Компьютерные сети
Программирование, Базы данных
Страховое право
Геодезия, геология
Пищевые продукты
Таможенное право
Металлургия
Ценные бумаги
Юридическая психология
Международное частное право
Международное право
Жилищное право
Экологическое право
Математика
Налоговое право
Правоохранительные органы
Экономика и Финансы
Семейное право
Компьютеры, Программирование
Разное
Гражданское процессуальное право
Астрономия
Российское предпринимательское право
Земельное право
Иностранные языки
Уголовное и уголовно-исполнительное право
Подобные работы
Структурированная кабельная система на оборудовании Nexans
echo "Кабельные системы являются той “базой” на котором строятся все основные компоненты информационно-вычислительных комплексов предприятий и организаций. Грамотная организация кабельной системы зда
Моделирование Web-графа
echo "Оценка________________________ Зав. кафедрой д.ф.-м.н., профессор Степанов А.Н. ______________________________ Самара 2006 Оглавление. TOC o '1-5' h z u Введение. PAGEREF _Toc105251122 h 3 Web -
Н.323 протокол IP-телефонии
echo "Стремление использовать сложившуюся структуру IP сетей привело к появлению в 1996 году стандарта H.323 (Visual Telephone Systems and Terminal Equipment for Local Area Networks which Provide a No
Особенности самоопределения и формирования идентичности молодых людей, увлекающихся интернетом
echo "Исходя из этого, будем рассматривать влияние на психику молодого человека в комплексе всеми новыми ИТ и в частности связанных с пользователем посредством глобальной вычислительной системы (Интер
Классификация меток и смарт-карт, работающих по радиоканалу
echo "Данная курсовая работа просвещена одному из самых перспективных и бурно развивающейся виду пластиковых карт – бесконтактным пластиковым смарт-картам и радиометкам . 1. Общая характеристика беско
Технология EDGE
echo "Впервые EDGE была представлена ESTI (Европейский институт стандартизации электросвязи) в начале 1997 года в качестве эволюции существующего стандарта GSM. Основное эволюционное изменение при пер