Дипломная работа Исследование модулярности веб-графа сайта



страница1/29
Дата24.07.2017
Размер7.58 Mb.
ТипДиплом
  1   2   3   4   5   6   7   8   9   ...   29
Санкт-Петербургский государственный университет

Факультет прикладной математики – процессов управления

Кафедра технологии программирования
Ланкин Александр Валерьевич
Дипломная работа

Исследование модулярности веб-графа сайта

Заведующий кафедрой,


кандидат физ.-мат. наук,
доцент Сергеев С. Л.
Доктор технических наук, профессор Печников А. А.
Старший программист

ООО "Искусство Управления Данными" Чернобровкин Д.И.


Санкт-Петербург

2016

Содержание


Содержание 2

Введение 3

Постановка задачи 5

Обзор литературы 7

Глава 1. Разработка программы сканирования сайта для построения его веб-графа 9

1.1. Требования к разрабатываемому приложению 9

1.2. Нормализация URL 11

1.3. Общая архитектура RCCrawler 13

1.4. Конфигурация RCCrawler для решения поставленной задачи 16

Глава 2. Исследования модулярности веб-графов сайтов 19

2.1. Основные определения 19

2.2. Построение вектора модулярности веб-графа сайта 21

2.3. Кластерный анализ на множестве векторов модулярности 21

Глава 3. Экспериментальная часть 23

3.1. Список исследуемых сайтов факультетов и институтов СПбГУ 23

3.2. Ход исследования 24

3.4. Анализ значений модулярности 38

3.5. Кластеризация веб-сайтов 39

3.6. Кластеризация веб-сайтов на расширенном множестве 47

Выводы и заключение 49

Список литературы 51

Приложение 53





Введение


Вебометрика - раздел информатики, посвященный изучению количественных аспектов конструирования и использования информационных ресурсов, структур и технологий применительно к Всемирной паутине [1]. Основными структурами изучения вебометрики являются веб-сайты, рассматриваемые как атомарные неделимые единицы. К нашему времени структура веб-сайтов стала достаточной сложной сама по себе, и может быть сравнима с отдельными фрагментами Веба. Для описания такой структуры можно использовать веб-граф сайта - ориентированный граф, вершинами которого являются документы, а дугами гиперссылки между ними. Такой граф можно разбить на сообщества (кластеры, модули) - группы таких вершин, что количество ребер, связывающих вершины внутри сообщества намного больше, чем количество ребер связывающих сообщества.

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

В качестве объекта исследования выбрано множество сайтов факультетов и институтов Санкт-Петербургского государственного университета.

Для построения веб-графов сайтов была разработан специальный краулер (англ. crawler) - программа занимающаяся процессом следования по страницам сайта через гиперссылки, полученные с других страниц и внесенные пользователям вручную, с целью сбора определенной информации, статистики или сохранения ресурсов сайта. Далее такой процесс будет называться краулингом (англ. crawling).

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

Постановка задачи


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

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

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

Основная гипотеза, проверяемая в работе, заключается в том, что тематически близкие веб-сайты должны иметь близкие (в заданном смысле) вектора модулярности.

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

Для решения основной задачи требуется решить следующие подзадачи:



  1. Разработать программу-краулер, сканирующую заданный сайт и выдающую данные для построения его веб графа.

  2. Отсканировать и построить веб-графы заданного множества сайтов (в данной работе - сайтов факультетов и институтов Санкт-Петербургского государственного университета (СПбГУ)).

  3. Вычислить меры модулярности и построить вектора модулярности для построенных веб-графов.

  4. Реализовать процедуру разбиения построенного множества векторов на сравнительно однородные группы методами кластерного анализа.

  5. Провести анализ полученных результатов и сформулировать основные выводы результатов исследования.

Обзор литературы


В научной литературе, изученной в процессе работы, можно выделить 5 основных блоков, связанных с темой исследования: веб-графы, краулеры, модулярность графа, укладки графов и программный продукт Gephi.

Веб-графам сайтов посвящена статья [2], в которой выделяются три свойства веб-графа сайта:

  1. Веб-граф сайта имеет выделенную начальную вершину представленную главной страницей.

  2. В веб-графе сайта можно выделить уровневую структуру через удаленность любой веб-страницы от главной.

  3. Веб-граф сайта почти всегда сильно-связный, в отличие от веб-графа фрагмента Веба.

Далее в статье описываются результаты исследования сайта Института прикладных математических исследований КарНЦ РАН (http://mathem.krc.karelia.ru), для которого было проведено построение веб-графа, и для страниц которого был рассчитан PageRank. В частности, рассмотрен и проанализирован топ 10 страниц с самым высоким PageRank. В заключении предварительно дана положительная оценка перспективности таких исследований.

Общим принципам разработки краулеров посвящена работа [3], в которой авторы рассмотрели архитектуры простейших моделей однопоточного краулера, многопоточного краулера, а также алгоритмы краулинга: Naive Best-First Crawler, SharkSearch, Focused Crawler, Context Focused Crawler, Info Spiders.

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

В статье [4] обсуждаются случаи, когда различные URL отсылают к одинаковому текстовому содержимому. Такие повторяющиеся URL-адреса широко распространены на веб-сайтах, так как программное обеспечение веб-сервера часто использует псевдонимы и перенаправления (редиректы), приводя URL-адреса к некоторой канонической форме, и динамически генерирует ту же самую страницу по различным URL. В нашем случае этот вопрос решается посредством составления набора правил запрета URL с помощью анализа гиперссылок, по которым выявлено повторение содержимого (контента) ранее встречавшихся страниц. Нормализации URL посвящен отдельный пункт первой главы.

Понятие модулярности графа было описано в работах [5,6]. В них описаны алгоритмы разбиения графа на сообщества, в том числе и в плане производительности. Модулярность используется как качественный критерий меры разбиения графа на сообщества. Целью таких алгоритмов является максимизация значения модулярности.

Укладка графа – это графическое представление (визуализация) графа на плоскости, ориентированное как правило на удобное для пользователя отображение требуемых свойств графа. Укладки графа описаны в работе [7], где говорится о методах и средствах визуализации структурированных данных, формализованных в виде графов. Перечислены такие алгоритмы укладки как Eades, Kamada-Kawaii, Fructerman-Reingold, Yifan Hu, Force Atlas 2, Open Ord.

Gephi – графическая оболочка для представления и изучения графов [8]. Разработана на языке программирования Java на платформе Netbeans.

Предоставляет возможности визуализации графа, укладки графа, сбора статистик по графу, таких как средняя степень, средняя взвешенная степень, диаметр графа, плотность графа, модулярность, PageRank, связные компоненты и др..






Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   29


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал