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

Ланкин Александр Валерьевич

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

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

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36345f1be77c40d58945

UUID: 65f9ebf0-04c8-42ed-b2a9-297dc45cf128

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 159

Ланкин Александр Валерьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 2907024 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ – ПРОЦЕССОВ УПРАВЛЕНИЯ КАФЕДРА ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ Ланкин Александр Валерьевич Дипломная работа Исследование модулярности веб-графа сайта Заведующий кафедрой, кандидат физ.-мат. наук, доцент Сергеев С. Л. Доктор технических наук, профессор Печников А. А. Старший программист ООО "Искусство Управления Данными" Санкт-Петербург 2016 Чернобровкин Д.И.

2 Содержание Содержание.................................................................................................... 2 Введение.........................................................................................................3 Постановка задачи.........................................................................................5 Обзор литературы..........................................................................................7 Глава 1. Разработка программы сканирования сайта для построения его веб-графа.................................................................................................................. 9 1.1. Требования к разрабатываемому приложению........................................................................... 9 1.2. Нормализация URL........................................................................................................................11 1.3. Общая архитектура RCCrawler...................................................................................................... 13 1.4. Конфигурация RCCrawler для решения поставленной задачи................................................... 16 Глава 2. Исследования модулярности веб-графов сайтов.......................20 2.1. Основные определения................................................................................................................20 2.2. Построение вектора модулярности веб-графа сайта................................................................. 22 2.3. Кластерный анализ на множестве векторов модулярности...................................................... 22 Глава 3. Экспериментальная часть............................................................24 3.1. Список исследуемых сайтов факультетов и институтов СПбГУ.................................................. 24 3.2. Ход исследования......................................................................................................................... 25 3.3. Сводные данные по результатам сканирования сайтов............................................................ 26 3.4. Анализ значений модулярности.................................................................................................. 39 3.5. Кластеризация веб-сайтов............................................................................................................41 3.6. Кластеризация веб-сайтов на расширенном множестве........................................................... 48 Выводы и заключение................................................................................. 50 Список литературы..................................................................................... 52 Приложение................................................................................................. 54

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

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

5 Постановка задачи Основная задача данной работы заключается в применении вебометрических методов к заданному множеству веб-сайтов с целью проверки гипотезы о том, что тематически близкие сайты обладают сходными (в некотором смысле) структурными характеристиками. В каче стве теоретиче ской модели веб-сайта принимается соответствующий веб-граф, где вершинами являются html-страницы (документы - в более общем случае), а дугами – связывающие их гиперссылки. В качестве оценки структурной характеристики сайта в работе принимается модулярность его веб-графа. Модулярность - это свойство графа и некоторого разбиения его на подграфы (так называемые модули). Мера модулярности показывает, насколько данное разбиение качественно в том смысле, что существует много ребер, лежащих внутри подграфов, и мало ребер, лежащих вне подграфов (соединяющих подграфы между собой). В работе вводится понятие вектора модулярности, а именно, вектора, значения элементов которого равны количеству модулей заданной размерности, начиная от 2 и заканчивая размерностью наибольшего модуля. Основная гипотеза, проверяемая в работе, заключается в том, что тематически близкие веб-сайты должны иметь близкие (в заданном смысле) вектора модулярности. Таким образом, более точно основная задача заключается в разработке математических методов и программ для проверки сформулированной выше гипотезы. Для решения основной задачи требуется решить следующие подзадачи: 1. Разработать программу-краулер, сканирующую заданный сайт и выдающую данные для построения его веб графа. 2. Отсканировать и построить веб-графы заданного множества сайтов (в данной работе - сайтов факультетов и институтов СанктПетербургского государственного университета (СПбГУ)).

6 3. Вычислить меры модулярно сти и по строить вектора модулярности для построенных веб-графов. 4. Реализовать процедуру разбиения построенного множества векторов на сравнительно однородные группы методами кластерного анализа. 5. Провести анализ полученных результатов и сформулировать основные выводы результатов исследования.

7 Обзор литературы В научной литературе, изученной в процессе работы, можно выделить 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 отсылают к

8 одинаковому текстовому содержимому. Такие повторяющиеся 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, связные компоненты и др..

9 Глава 1. Разработка программы сканирования сайта для построения его веб-графа 1.1. Требования к разрабатываемому приложению Основная задача разрабатываемого приложения заключается в сканировании заданного веб-сайта с целью сбора данных о его внутренней структуре, используемых далее для построения веб-графа сайта как модели структуры сайта. Предполагается, что имеется некоторое множество исследуемых сайтов, поэтому должна быть предусмотрена возможность сканирования нескольких сайтов. Основные требования к приложению: 1. Получать в качестве исходных данных список доменных имен сайтов, предназначенных для сканирования. 2. Обходить каждый сайт начиная с главной (индексной) страницы, перемещаясь по внутренним гиперссылкам в заданном порядке обхода «вначале вширь» [9]. 3. Выдавать в качестве результата данные для построения веб-графов сайтов, полученных на входе, например, в виде файлов, имена которых ассоциируемы с доменными именами сайтов. 4. Иметь возможность обхода несколько сайтов одновременно. 5. Иметь расширяемую архитектуру для последующего развития функциональности. 6. Иметь механизмы внешней остановки работы приложения с сохранением состояния для продолжения работы с точки останова. 7. Иметь механизмы внутренней остановки работы приложения в специально перечисленных случаях типа: не осталось не обойденных внутренних гиперссылок, по истечению времени ожидания доступа к вебресурсу, по достижению заданной глубины сканирования.

10 8. Следовать правилам из файла robots.txt сайта (если не указано иное). Это помогает избегать ненужных ссылок вроде страниц поиска, авторизации, сортировки по заданным параметрам, приводящих в некоторых случаях к бесконечному процессу сканирования. Дополнительные требования, уточнения и допущения: 1. Гиперссылки могут извлекаться из html полученной страницы из тегов <a> без предварительного выполнения сценариев и имитации действий пользователя. Такое допущение подходит для большинства сайтов, упрощает разработку и позволяет меньше нагружать ресурсы компьютера. 2. Для гиперссылки соответствующей узлу веб-графа сервер должен выдавать ответ с кодом состояния HTTP [11], равным 200 (OK — успешный запрос). 3. В случае если код ответа 301 [12] (Moved Permanently), 302 (Moved Temporarily) или 303 (See Other), необходимо осуществлять редирект по указанному в ответе URL и заменять адрес обрабатываемой страницы новым. Такое допущение связано с тем, что пользователь в окне браузера получает страницу по конечной ссылке и «не замечает» промежуточных страниц с редиректом. 4. Следует игнорировать внешние гиперссылки, включая случаи, когда они являются ссылками на поддомен текущего домена. В рамках данной работы поддомен считается отдельным сайтом в соответствии со следующим определением сайта: веб-сайт – совокупность html-страниц и вебдокументов, связанных внутренними гиперссылками и обладающих единством содержания, идентифицируемый в Вебе по уникальному доменному имени. 5. Можно игнорировать ссылки с протоколом передачи данных, отличным от заданного. 6. Игнорируются результаты запросов по гиперсылкам в тех случаях, когда ответ сервера в http-заголовках не указывает Content-type [13] text/html или не указывает Content-type вовсе. То есть объектами сканирования

11 являются только html-страницы, а гиперссылки, указывающие на файлы с расширениями rar, docx, js и прочими, не рассматриваются. 7. Ссылки должны проходить некоторую нормализацию [14] (процесс, при котором URL приводится к единообразному виду) для исключения случаев скачивания страницы по одной и той же ссылки с разным написанием. 8. Страницы с одинаковым содержимым (дубли) считаются одной и той же страницей. Под указанные требования было разработано приложение RCCrawler. 1.2. Нормализация URL Нормализации по видам разбивают на три типа [15]: 1. Сохраняющие исходную семантику URL. 2. Частично изменяющие семантику. 3. Полностью изменяющие семантику. К первому типу относят: 1. Конвертация протокола и хоста в нижний регистр. Пример: htTp://eXamplE.com → http://example.com 2. Удаление порта по умолчанию. По умолчанию для доступа к сайту по протоколу http используется 80 порт. В случае протокола https по умолчанию используется 443 порт. Пример: https://example.com:443/q.html → https://example.com/q.html 3. Перевод закодированных знаком процента последовательностей (пример: %3A) в верхний регистр. Пример: http://example.com/%3a%2B%3e → http://example.com/%3A%2B%3E Ко второму типу относят: 1. Добавление завершающего слеша. Пример: http://example.com/folder → http://example.com/folder/

12 На практике данная процедура не всегда дает эквивалентный URL. 2. Нормализация пути. Символы перехода на уровень выше ("..") или текущего каталога (".") можно разрешить до отправки http запроса. Пример http://example.com/f1/./f2/../f3 → http://example.com/f1/f3 К третьему типу относят: 1. Отбрасывание фрагмента. Фрагмент имеет значение только на клиенте. Пример: http://example.com/folder#fragment → http://example.com/folder 2. Замена двойных слешей на одинарный. Пример: http://example.com/f1//f2 → http://example.com/f1/f2 3. Замена IP адреса именем домена. Если мы знаем, что в данный IP резолвится определенный домен, мы можем сделать замену IP на домен. Пример: https://23.23.23.23 → https://example.com 4. Сортировка параметров GET запроса. Пример: http://example.com/?b=1&c=2&a=3 → http://example.com/?a=3&b=1&c=2 5. Удаление «?» при пустом списке параметров GET запроса. Пример: http://example.com/? → http://example.com/ 6. Удаление пустых параметров GET запроса. Пример: http://example.com/?a&b=1&c=2→ http://example.com/?b=1&c=2

13 1.3. Общая архитектура RCCrawler RCCrawler является многопоточным мультиплатформенным краулером Написан на языке C++ стандарта С++11 с использованием фреймворка Qt 1 версии 5.5. Обладает некой общей архитектурой, которая может конкретизироваться определенными классами и, таким образом, возможно реализовывать разные задачи, связанные с crawling. На рисунке 1 представлено визуальное представление архитектуры. Главный поток ApplicationManager DownloadingThread Скачивание страниц ParsingThread x N Р а з б о р Р а з б о р Р а з б о р с т р а н и ц с т р а н и ц с т р а н и ц RoutineThread Логирование Выгрузка кэша в БД Анализ списка URL Прочее DataManager Рис. 1. Архитектура RCCrawler. При запуске в главном потоке происходит чтение settings.ini и выбирается реализация интерфейса ApplicationManager. Данный объект осуществляет управление приложением и инициализирует все другие потоки и ключевые объекты, завершает приложение. Например потомок ApplicationManager может считывать при запуске необходимые данные из текстовых файлов или слушать какой-либо порт и выполнять поступающие команды. DownloadingThread 1 http://www.qt.io представляет собой базовый класс для потока,

14 занимающегося загрузкой страниц. ParsingThread - базовый класс, потомки которого занимаются разбором скачанных страниц. Тут может быть любой разбор, не только извлечение ссылок, как в данной работе. Одновременно может быть несколько таких потоков, так как разбор страниц в данном случае – основная нагрузка. RoutineThread - потомки этого класса должны заниматься логированием, переносом части данных в СУБД для уменьшения потребляемой оперативной памяти и пр.. В многопоточном приложении необходимо согласовывать доступ к общим данным и минимизировать общение потоков. DataManager представляет интерфейс для получения потоками необходимых для работы данных. Потомки должны реализовывать блокировки для исключения так называемых гонок за данными. DataManager делает общение потоков не столь необходимым. Например, есть метод забирающих данные для парсинга или для скачивания, и тд.. Так же этот интерфейс дает инкапсуляцию хранения данных: полностью в оперативной памяти, во внешних источниках, частично в оперативной памяти - аспект, касающийся только реализации DataManager и не влияющий на другие компоненты RCCrawler. За страницы и связи между ними отвечают структуры HostData, PageData и PageArc. Рассмотрим их предназначение и поля. HostData отвечает за сайт. Поля: QString host; QString protocol; QString str; uint crawlDelay; uint maxDownloadsAtTime; int maxCrawlLevel; RTRContainer rules; host - строка с именем хоста (пример "example.com"). protocol - протокол (пример "https"). str - строка для быстрой подстановки (пример "https://example.com").

15 crawlDelay - задержка по скачиванию в миллисекундах. Диапо maxDownloadsAtTime - количество одновременных загрузок с сайта. maxCrawlLevel - максимальный уровень crawling'а включительно. rules - правила из robots.txt сайта. PageData отвечает за страницу. Поля: ulong id; HostData* phD; QString url; QString normalizedUrl; ulong idFrom; uint level; uint outDegree; bool blocked; bool downloaded; bool parsed; QString content; uint contentHash; uint errorCode; ulong replaceId; uint downloadAttempts; bool remove; id - уникальный идентификатор, не должен быть равен нулю. phD - указатель на соответствующую HostData. url - исходная ссылка. normalizedUrl - нормализованная ссылка. idFrom - id страницы, откуда получена ссылка на данную страницу. level - уровень страницы. outDegree - количество внешних исходящих ссылок. blocked - этот параметр должен выставляться в true в случае если данная страница отправлена на скачивание и возвращаться в false при обновлении. downloaded - была ли страница скачана. parsed - был ли совершен разбор html страницы. content - содержимое страницы. contentHash - хэш содержимого страницы. Если страница была разобрана, то ее содержимое не нужно, а по сравнению хэша можно выявить то, является ли страница дублем. errorCode - код ошибки. 0, если ошибки нет. replaceId - id страницы, дублем которой является текущая. downloadAttempts - количество попыток скачать страницу. Ограничение на этот параметр помогает избежать циклических редиректов. remove - при обновлении PageData в хранилище DataManager сигнализирует о необходимости удаления и совершения сопутствующих действий.

16 PageArc отображает связь между двумя страницами. Поля: ulong id; ulong from; ulong to; id - уникальный идентификатор, не должен быть равен нулю. from - id PageData на которой находится ссылка. to - id PageData на которую указывает ссылка. Рассмотренные выше структуры являются основным набором данных, которые хранит DataManager, и которыми оперирует все приложение. Их достаточно для построения веб-графа сайта. Также важными вспомогательными базовыми классами являются RobotsTxt, ApplicationFinisher, ResultUnloader. RobotsTxt реализует получение файла robots.txt и проверку ссылок на следование правилам этого файла. ApplicationFinisher своим методом needToFinishApplication отвечает, нужно ли завершить приложение. Возможные варианты: вся работа выполнена, истек таймаут. ResultUnloader осуществляет выгрузку результата в нужную форму. Для возможности специализировать объекты на этапе работы приложения используется две абстрактные фабрики: O b j e c t C r e a t o r - создание базовых объектов (потомки ApplicationManager, DataManager ParsingThread, DownloadingThread, RoutineThread). HelperCreator - абстрактная фабрика по созданию вспомогательных объектов. 1.4. Конфигурация RCCrawler для решения поставленной задачи В качестве ApplicationManager используется TextFileAM. Алгоритм его работы: 1. Создать и настроить реализации DataManager, DownloadingThread,

17 заданное количество ParsingThread, RoutineThread, несколько реализаций ApplicationFinisher согласно файлу settings.ini. 2. Прочитать файл hosts.txt в качестве источника сайтов для сканирования. 3. Для каждого сайта получить правила из robots.txt и поместить стартовую страницу в DataManager. 4. Запустить потоки, определенные в пункте 1. 5. Проверять в цикле с помощью реализаций ApplicationFinisher необходимость завершить приложение. 6. В случае положительного ответа от одного из ApplicationFinisher'ов произвести выгрузку результата с помощью реализаций ResultUnloader, указанных в settings.ini. 7. Завершить приложение. DownloadingThread в используемой конфигурации представлен классом DT0, к о т о р ы й а с и н х р о н н о з а г р у ж а е т с т р а н и ц ы и с п о л ь з у я QNetworkAccessManager и сигнально-слотовую систему Qt. Упрощенный цикл работы: 1. Обработать события. То есть принять сигналы и вызвать связанные слоты. 2. Запросить у DataManager коллекцию PageData для скачивания по каждому сайту. 3. По каждому сайту поставить данные на загрузку, если свободные соединения. 4. При определенных условиях отправить данные по которым произведена загрузка на обновление в DataManager. ParsingThread представлен классом PT0. Упрощенный цикл работы: 1. Получить коллекцию PageData для разбора у DataManager. 2. Для каждой PageData: 3. Поставить поле parsed в true. 4. Разобрать content на ссылки. 5. По каждой ссылке: 6. Проверить является ли она внутренней. 7. Если нет, то повысить outDegree. Если да, то нормализовать с с ы л к у и д о б а в и т ь в в ы ход н у ю ко л л е к ц и ю PDAndPACreateData

18 (вспомогательная структура для обработки внутри DataManager и создания соответствующих данных). 8. Отправить выходную коллекции PDAndPACreateData на вставку в DataManager. 9. Отправить входную коллекцию PageData в DataManager на обновление. RoutineThread представлен классом RT0. Его единственной функцией является логирование. Доступны три реализации ApplicationFinisher: WorkIsDoneAF, T i m e o u t A F и StopFileAF. П е р в ы й в о з в р а щ а е т true в м е т о д е needToFinishApplication если у DataManager нет PageData для скачивания и обработки, второй по истечению таймаута. Так как прием пользовательского ввода во время работы невозможен по причине активного вывода информации по скачанным страницам и ошибкам, в качестве средства внешнего завершения приложения был разработан StopFileAF, который проверяет появление файла с заданным именем в каталоге приложения и сигнализирует о необходимости остановки в случае наличия. GephiSiteGraphRU я в л я е т с я и с п о л ь зу е м о й р е а л и з а ц и е й ResultUnloader. Выгружает данные в формате для построения графа в Gephi. В качестве DataManager используется BMICDM (Boost Multi-Index Container Data Manager). Для хранения структур PageData и PageArc используется Boost Multi-index Container Library2. Multi-index сontainer представляет из себя нечто вроде таблицы базы данных в памяти, доступ в которой осуществляется по индексам по полю или набору полей, и эти индексы задаются на этапе компиляции. Таким образом, доступ и поиск данных в такой коллекции обладает высокой производительностью. Также, индекс может быть уникальным и вставка с нарушением уникальности не будет происходить. Все эти качества multi-index container позволяют потокам находиться в ожидании разблокировки ресурса меньшее время. 2 http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/

19 Глава 2. Исследования модулярности веб-графов сайтов 2.1. Основные определения Веб-сайт (сайт) – совокупность html-страниц и веб-документов, связанных внутренними гиперссылками и обладающих единством содержания, идентифицируемая в Вебе по уникальному доменному имени. Ориентированный граф — это упорядоченная пара G = (V, E), где V — непустое множество вершин, и E — множество (упорядоченных) пар различных вершин, называемых дугами (ориентированными рёбрами). Дуга — это упорядоченная пара вершин (vi, vj), где вершину vi называют началом, а vj — концом дуги. Матрица смежности - матрица A = [Aij] размерности nxn, где n количество вершин графа, элементы которой определяются следующим образом: Aij = 1, если (vi, vj) Є E, Aij = 0 в противном случае Инцидентность — понятие, используемое дуги и вершины: если v 1, v2 — вершины, а e=(v1, v2) — соединяющее их ребро, тогда вершина v 1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности. Петля - дуга инцидентная одной и той же вершине. Степень вершины - количество дуг, инцидентных вершине. Притом, петля учитывается дважды. Модулярность - это метрика, разработанная с целью измерения силы разбиения графа на сообщества. Пусть произведено разбиение графа на сообщества или по-другому классы. Пусть ci - метка класса для vi. Мера модулярности Q описывается следующей формулой:

20 где m - количество дуг, Aij - элемент матрицы смежности, ki, kj - степени соответствующих вершин, δ(ci, cj) - символ Кронекера, вычисляемый по формуле: где ci, cj - метки класса соответствующих вершин. Рассмотрим ki k j 1 δ (c i , c j ) . Если мы выберем i ∑ 2 i, j 2 m и j такие, что вершины будут принадлежать одному классу, то, очевидно, получим ожидаемое число ребер для данного класса. Таким образом, для выделенного сообщества мера модулярности отражает разницу между реальным количеством ребер внутри сообщества и ожидаемым. Веб-граф сайта – ориентированный граф, в качестве вершин которого принимаются документы, а дуг – гипертекстовые ссылки между ними. В нашем случае в качестве вершин принимаются в основном htmlстраницы. В качестве оценки структурной характеристики сайта в работе принимается модулярность его веб-графа. Поскольку реальные веб-сайты могут иметь очень большую размерность, соответствующие им веб-графы также могут содержать большое количество вершин и дуг. Понятно, что количество классов в веб-графе может быть достаточно велико и классы могут иметь большие размерности. Пусть множество вершин веб-графа сайта V разбито на s классов W1, W2, …,Wk, таких, что W1UW2U…UWk=V и Wi∩Wj для любых i,j (i≠j). Причем классы упорядочены по убыванию мощности, то есть W1≥W2≥…≥Wk.

21 Вектором модулярности для заданного разбиения V на классы W1, W2, …,Wk будем называть вектор M=(W1, W2,…,Wk). 2.2. Построение вектора модулярности веб-графа сайта Для заданного сайта с доменным именем краулер RCCrawler в качестве выходных данных генерирует два файла: первый содержит узлы веб-графа с url и другой информацией, второй содержит дуги. Эти два файла могут быть использованы в качестве исходных данных в программном комплексе Gephi для построения и исследования веб-графа сайта. Gephi решает задачу разбиения на сообщества (модули) и вычисления значения модулярности графа. Поэтому применение краулера RCCrawler и пакета Gephi позволяет построить вектор модулярности для заданного сайта. Таким образом, если нам задано множество, состоящее из n сайтов s1, s2, …, sn, то с использованием RCCrawler и пакета Gephi мы можем получить множество векторов модулярности M1=(W11, W21,…,Wk11) , M2=(W12, W22, …,Wk22), …, Mn=(W1n, W2n,…,Wknn) для их дальнейшего анализа. 2.3. Кластерный анализ на множестве векторов модулярности Теперь, считая заданным множество векторов модулярности M1, M2, …, Mn, методами кластерного анализа решается задача разбиения множества сайтов на однородные в некотором понимании группы. Цитируя [10], «...задача кластерного анализа заключается в том, чтобы на основании данных (об объектах), ... разбить множество объектов на m (m – целое) кластеров (подмножеств) ... так, чтобы каждый объект принадлежал одному и только одному подмножеству разбиения. А объекты, принадлежащие одному и тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам, были разнородными. Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности». Для решения задачи кластерного анализа на множестве сайтов в работе

22 используется пробная версия пакета STATISTICA3, предоставляющая возможности, достаточные для нашего исследования. В нашем случае был применен метод кластерного анализа Joining (tree clustering) (Объединение (двевовидная кластеризация)) с настройками пакета STATISTICA: - для определения близости между объектами выбрано Euclidean distances (Евклидово расстояние), то есть геометрическое расстояние в многомерном пространстве; - для определения расстояния между кластерами выбрано Single Linkage (Метод одиночной связи “принцип ближайшего соседа”), расстояние между ближайшими представителями классов. Поскольку в нашем случае вектора модулярности могут иметь различную размерность, используется следующий метод: в качестве единой размерности выбирается максимальное значение K=max{k1 , k2, …, kn}. Далее, все вектора, имеющие размерность меньше K, дополняются справа нулевыми элементами до требуемой единой размерности. Вектора модулярности задаются в соответствующей табличной форме пакета, затем запускается процедура кластерного анализа с указанными настройками, по сле выполнения которой выдаются результаты классификации. Затем используется ряд опций, позволяющих проводить требуемый анализ результатов. Конкретные результаты по кластеризации вебсайтов будут приведены в следующих главах. 3 Триал-версии STATISTICA. http://www.statsoft.ru/products/trial.

23 Глава 3. Экспериментальная часть 3.1. Список исследуемых сайтов факультетов и институтов СПбГУ Название факультета/института Биологический факультет Восточный факультет Факультет искусств Математико-механический факультет Факультет международных отношений Факультет политологии Факультет прикладной математики - процессов управления Факультет психологии Факультет свободных искусств и наук Факультет социологии Факультет стоматологии и медицинских технологий Физический факультет Филологический факультет Экономический факультет Юридический факультет Факультет Военного обучения Институт "Высшая школа менеджмента" Институт наук о Земле Институт "Высшая школа журналистики и массовых коммуникаций" Институт истории Институт философии Институт химии URL сайта http://bio.spbu.ru http://orient.spbu.ru http://arts.spbu.ru http://math.spbu.ru http://sir.spbu.ru http://politology.spbu.ru http://apmath.spbu.ru http://www.psy.spbu.ru http://artesliberales.spbu.ru http://soc.spbu.ru http://dent.spbu.ru http://phys.spbu.ru http://phil.spbu.ru http://econ.spbu.ru http://law.spbu.ru http://fvo.spbu.ru http://gsom.spbu.ru http://earth.spbu.ru http://jf.spbu.ru https://history.spbu.ru http://philosophy.spbu.ru http://chem.spbu.ru

24 3.2. Ход исследования С помощью RCCrawler были просканированы все сайты из списка в п. 3.1. Использованные файлы settings.ini и hosts.txt находятся в приложении. Все сайты были просканированы до конца, кроме сайта биологического факультета, для которого было применено ограничение по 4-й уровень включительно. Для каждого отсканированного сайта был получен файл, содержащий перечень страниц (соответствующих вершинам веб-графа) и перечень внутренних гиперссылок (соответствующих дугам веб-графа). Для каждого отсканированного сайта по полученным файлам с использованием программного пакета Gephi был построен соответствующий веб-граф, реализована их визуализация, сделан расчёт значения модулярности и построены все сообщества (модули), на которые разбивается веб-граф. Визуализация полученных веб-графов произведена в укладке Yifan Hu [7]. Для наглядности вершина, соответствующая начальной странице сайта, имеет больший размер и отличный от других вершин цвет. Также, в некоторых случаях относительно небольшие вершины сильно отдаленные от основной части графа находятся за гранями изображения. Также, из-за размера изображений некоторые дуги могут стать незаметными. Но, стоит заметить, что изолированных вершин в графах нет. Параметры укладки и рендеринга описаны в приложении. Далее был произведен кластерный анализ полученного множества векторов модулярности в пакете STATISTICA.

25 3.3. Сводные данные по результатам сканирования сайтов Биологический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://bio.spbu.ru 7259 Вектор модулярности: [2572,2286,1259,1063,79 ] 238952 0,344 5 Рис. 2. Веб-граф сайта биологического факультета Восточный факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://orient.spbu.ru 1042 Вектор модулярности: [625,267,64,33,26] 16054 0,380 5 Рис. 3. Веб-граф сайта восточного факультета

26 Факультет искусств URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://arts.spbu.ru 1146 Вектор модулярности: [501,453,72,54,35,22,1 5,12] 26494 0,129 8 Рис. 3. Веб-граф сайта факультета искусств Математико-механический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://math.spbu.ru 2816 Вектор модулярности: [793,447,447,328,248,16 6,62,62,57,45,45,21,21,1 7,11,10,8,6,4,4,3,3,2,2,2, 2] 51234 0,449 25 Рис. 4. Веб-граф сайта математико-механического факультета

27 Факультет международных отношений URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://sir.spbu.ru 14231 Вектор модулярности: [1784,1784,1696,1692,16 89,1676,1675,209,132,12 6,66,58,55,50,44,44,44,4 4,44,44,44,44,44,44,44,4 4,44,44,44,44,44,44,44,4 4,44,44,44,44,44,44,44,4 4,44,44,44,44,44,44,43] 238952 0,065 49 Рис. 5. Веб-граф сайта факультета международных отношений Факультет политологии URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://politology.spbu.ru 996 38921 0,009 3 Вектор [482,452,62] Рис. 6. Веб-граф сайта факультета политологии модулярности: Факультет прикладной математики - процессов управления URL: Количество http://www.apmath.spbu. ru 4385

28 вершин: Количество дуг: Мера модулярности: Количество сообществ: Вектор модулярности: 271261 0,465 37 [1690,792,687,223,102,9 5,79,72,66,46,41, 41,40,38,36,35,31,29,25, 25,21,21,20,19,17,15,14, 13,12,8,8,7,5,3,3,3,3] Рис. 7. Веб-граф сайта факультета прикладной математики - процессов управления Рис. 8. Веб-граф сайта факультета прикладной математики - процессов управления. Основная часть.

29 Факультет психологии URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://www.psy.spbu.ru 1025 Вектор модулярности: [553,323,44,38,36,31] 31156 0,199 6 Рис. 9. Веб-граф сайта факультета психологии Факультет свободных искусств и наук URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: Вектор модулярности: http://artesliberales.spbu. ru 6232 468764 0,394 2 [4125,2107] Рис. 10. Веб-граф сайта факультета свободных искусств и наук

30 Факультет социологии URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://soc.spbu.ru 17867 Вектор модулярности: [5142,288,284,277,277,260,2 60,259,258,258,258,257,257, 257,255,253,253,253,253,252 ,252,252,251,251,251,251,25 0,250,250,249,249,249,248,2 48,248,247,247,247,246,246, 246,246,245,245,245,245,245 ,245,245,245,38,37,37,36,36, 35,34,33,33,3] 1256179 0,013 60 Рис. 11. Веб-граф сайта факультета социологии Факультет стоматологии и медицинских технологий URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://dent.spbu.ru 795 Вектор модулярности: [484,226,76,9] 13928 0,373 4 Рис. 12. Веб-граф сайта факультета стоматологии и медицинских технологий

31 Физический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://phys.spbu.ru 7118 Вектор модулярности: [1423,580,569,452,449,4 49,372,358,291,238,232, 180,151,145,130,129,127 ,113,96,85,76,73,72,64,6 2,61,61,50,30] 1172839 0,015 29 Рис. 13. Веб-граф сайта физического факультета Филологический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://phil.spbu.ru 6266 Вектор модулярности: [2492,2093,533,457,398, 150,143] 283266 0,285 7 Рис. 14. Веб-граф сайта филологического факультета

32 Экономический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://econ.spbu.ru 4189 Вектор модулярности: [2034,530,260,260,260,2 42,210,102,92,89,73,37] 506382 0,062 12 Рис. 15. Веб-граф сайта экономического факультета

33 Юридический факультет URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://law.spbu.ru 5483 Вектор модулярности: [2045,1656,1348,224,210 ] 1573891 0,287 5 Рис. 16. Веб-граф сайта юридического факультета

34 Факультет Военного обучения URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://fvo.spbu.ru 392 Вектор модулярности: [104,70,40,37,31,31,31,3 0,18] 45384 0,007 9 Рис. 17. Веб-граф сайта факультета военного обучения Институт "Высшая школа менеджмента" URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://gsom.spbu.ru 1868 Вектор модулярности: [1127,738,3] 250440 0,449 3 Рис. 18. Веб-граф сайта института "Высшая школа менеджмента"

35 Институт наук о Земле URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://earth.spbu.ru 2022 Вектор модулярности: [1275,421,37,37,35,29,28 ,28,27,26,26,22,21,10] 2022 0,234 14 Рис. 19. Веб-граф сайта факультета наук о Земле И н с т и ту т " В ы с ш а я ш кол а ж у рн а л и с т и к и и ма с с ов ы х коммуникаций" URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://jf.spbu.ru 29808 1227226 0,293 29 Вектор модулярности: [16908,4736,2218,1378,1 262,667,548,341,252,197 ,136,121,118,118,105,95, 89,88,82,76,62,43,31,29, 26,25,23,19,15] Институт истории URL: https://history.spbu.ru Рис. 20. Веб-граф сайта института "Высшая школа журналистики и массовых коммуникаций"

36 Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: 1574 Вектор модулярности: [302,286,221,150,115,10 1,78,76,66,64,45,37,33] 82219 0,065 13 Рис. 21. Веб-граф сайта института истории Институт философии URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://philosophy.spbu.ru 6508 Вектор модулярности: [2698,1899,676,325,241, 208,164,153,144] 189734 0,292 9 Рис. 22. Веб-граф сайта института философии

37 Институт химии URL: Количество вершин: Количество дуг: Мера модулярности: Количество сообществ: http://chem.spbu.ru 6983 Вектор модулярности: [2336,1952,1527,621,264 ,259,24] 203351 0,198 7 Рис. 23. Веб-граф сайта института химии

38 3.4. Анализ значений модулярности Далее будем использовать краткие обозначения для сайтов факультетов и институтов: Название факультета/института Биологический факультет Восточный факультет Факультет искусств Математико-механический факультет Факультет международных отношений Факультет политологии Факультет прикладной математики - процессов управления Факультет психологии Факультет свободных искусств и наук Факультет социологии Факультет стоматологии и медицинских технологий Физический факультет Филологический факультет Экономический факультет Юридический факультет Факультет Военного обучения Институт "Высшая школа менеджмента" Институт наук о Земле Институт "Высшая школа журналистики и массовых коммуникаций" Институт истории Институт философии Институт химии Краткое имя сайта bio orient arts math sir politology apmath psy artes-liberales soc dent phys phil econ law fvo gsom earth jf history philosophy chem Р а с с м о т р и м с в од н у ю т а б л и ц у з н ач е н и й м од ул я р н о с т и , отсортированную по убыванию: Сайт apmath math gsom artes-liberales orient dent Мера модулярности 0,465 0,449 0,449 0,394 0,380 0,373

39 bio jf philosophy law phil earth psy chem arts sir history econ phys soc politology fvo 0,344 0,293 0,292 0,287 0,285 0,234 0,199 0,198 0,129 0,065 0,065 0,062 0,015 0,013 0,009 0,007 Как видно из таблицы, разброс довольно большой. Нельзя сказать, что по этому параметру сайты находятся в одной группе. Несмотря на то, что понятие модулярности напрямую не связано с укладкой графов, и в частности с примененной укладкой Yifan Hu, достаточно сравнить визуализированные графы первых пяти и последних пяти графов и найти связь между значением модулярности и результатом укладки. 3.5. Кластеризация веб-сайтов Вектора модулярности для исследуемых факультетов и институтов ниже сведены в единую таблицу с добавлением нулей справа (как это было описано в главе 2). Количество элементов в самом длинном векторе равно 60. Был применен метод кластерного анализа Joining (tree clustering) (Объединение (древовидная кластеризация)) с настройками Euclidean distances (Евклидово расстояние) и Single Linkage (Метод одиночной связи “принцип ближайшего соседа”).

40 apmath artesliberales arts bio chem dent earth econ fvo gsom history 1 1690 2 792 3 687 4 223 5 102 6 95 7 79 8 72 9 66 10 46 11 41 12 41 13 40 14 38 15 36 16 35 17 31 18 29 19 25 20 25 21 21 22 21 23 20 24 19 25 17 26 15 27 14 28 13 29 12 30 8 4125 2107 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 501 453 72 54 35 22 15 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2572 2286 1259 1063 79 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2336 1952 1527 621 264 259 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 484 226 76 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1275 421 37 37 35 29 28 28 27 26 26 22 21 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2034 530 260 260 260 242 210 102 92 89 73 37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 104 70 40 37 31 31 31 30 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1127 738 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 302 286 221 150 115 101 78 76 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2218 1378 1262 667 548 341 121 118 118 105 95 89 88 82 76 62 43 31 29 26 25 23 19 15 0 law math orient phil philosoph y 2045 1656 1348 224 210 0 0 0 45 13 6 0 33 4736 64 19 7 0 37 16908 66 25 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 793 447 447 328 248 166 62 62 57 45 45 21 21 17 11 10 8 6 4 4 3 3 2 2 2 2 0 0 0 0 2698 1899 676 325 241 208 phys 1423 580 569 452 449 482 452 62 0 553 323 44 38 sir 1784 1784 1696 1692 soc 5142 288 284 277 jf politology psy 652 267 64 33 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2492 2093 533 457 398 150 143 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 164 153 14 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 449 372 358 12 7 0 72 64 62 61 61 50 30 0 0 12 9 0 73 0 14 5 0 76 0 15 1 0 85 0 23 2 0 96 0 23 8 0 113 0 29 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 36 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1676 1675 209 66 58 55 50 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 277 260 260 259 0 12 6 25 8 0 1689 0 13 2 25 8 25 8 257 25 7 25 7 255 25 3 25 3 25 3 253 25 2 25 2 252 25 1 25 1 25 1 251 25 0 25 0 250 249 180 130

41 продолжение таблицы apmath artesliberale s arts bio chem dent earth econ fvo gsom history jf law math orient phil philoso phy phys politolo gy psy sir soc 3 1 8 3 2 7 3 3 5 3 4 3 3 5 3 3 6 3 3 7 3 3 8 0 3 9 0 4 0 0 4 1 0 4 2 0 4 3 0 4 4 0 4 5 0 4 6 0 4 7 0 4 8 0 4 9 0 5 0 0 5 1 0 5 2 0 5 3 0 5 4 0 5 5 0 5 6 0 5 7 0 5 8 0 5 9 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 2 4 9 0 4 4 2 4 9 0 4 4 2 4 8 0 4 4 2 4 8 0 4 4 2 4 8 0 4 4 2 4 7 0 4 4 2 4 7 0 4 4 2 4 7 0 4 4 2 4 6 0 4 4 2 4 6 0 4 4 2 4 6 0 4 4 2 4 6 0 4 4 2 4 5 0 4 4 2 4 5 0 4 4 2 4 5 0 4 4 2 4 5 0 4 4 2 4 5 0 4 4 2 4 5 0 4 3 2 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 5 3 8 3 7 3 7 3 6 3 6 3 5 3 4 3 3 3 3 3

43 На рис. 24 приведена дендрограмма, показывающая пошаговый процесс укрупнения кластеров. Рис. 24. Дендрограмма для множества веб-сайтов СПбГУ (случай векторов модулярности) В случае настройки разбиения на 5 кластеров, получаются следующие кластеры: 1: sir; 2: jf; 3: apmath; earth; econ; gsom; phys; 4: artes-liberales; bio; chem; law; phil; philosophy; soc; 5: arts; dent; fvo; history; math; orient; politology; psy. Анализ значений векторов модулярности для полученного разбиения показывает, что в два первых (одноэлементных) кластера попали сайты с самым большим количеством страниц и самым большим количеством

44 модулей. Для остальных кластеров существенное влияние на такое разбиение оказывают значения первых элементов векторов модулярности. В третьем кластере оно находится в пределах от 1127 до 2034, в четвертом от 2045 до 5142, а в пятом от 101 до 793. Можно говорить о « маленьком», «среднем» и «большом» максимальном модуле, оказывающем большое влияние на кластеризацию. Нас в большей степени интересуют не столько размеры, сколько подобие («похожесть») структур сайтов. Поэтому следующая кластеризация была проведена на нормализованном множестве векторов модулярности. Рис. 25. Дендрограмма для множества веб-сайтов СПбГУ (случай нормализованных векторов модулярности) Нормализованный вектор модулярности получается из вектора модулярности делением каждого элемента вектора на общее количество вершин в графе. К примеру, вектор модулярности сайта биологического

45 факультета [2572,2286,1259,1063,79] преобразуется в нормализованный вектор [0.35432,0.31492,0.17344,0.14644,0.01088]. Далее снова был применен метод кластерного анализа Joining (tree clustering) с настройками Euclidean distances и Single Linkage. На рис. 25 приводится дендрограмма для этого случая. Разбиение на 5 кластеров имеет следующий вид: 1: econ; jf; 2: apmath; bio; chem; law; 3: arts; phil; philosophy; politology; 4: artes-liberales; dent; arts; gsom; orient; psy; 5: fvo; history; math; phys; sir; soc. Очевидно, два полученных разбиения на кластеры принципиально отличаются друг от друга. Однако второй случай с нормализованными векторами модулярности представляется более предпочтительным для оценки сходства структур веб-сайтов. Если в первом случае значительное влияние на результаты работы оказывали очень большие максимальные модули и большое количество страниц на сайте в целом, то во втором случае в большей степени учитывается количество модулей и их относительные размеры. Для примера на рис. 26 изображения визуализации двух сайтов из одного (пятого) кластера.

46 https://history.spbu.ru http://fvo.spbu.ru Рис. 26. Сайты Института истории и Факультета военного обучения Сайт Института истории содержит 1574 страницы и 82219 дуг, а сайт Факультета военного обучения – 342 страницы и 45358 дуг. Тем не менее, их структура очень похожа.

47 3.6. Кластеризация веб-сайтов на расширенном множестве Для проверки гипотезы о том, что тематически близкие сайты имеют близкие вектора модулярности, была проделана работа, основные результаты которой кратко опишем в этом пункте. Были отсканированы 8 сайтов, не относящихся к сайтам СПбГУ: - компания МакДональдс в России (www.mcdonalds.ru), - механико-математический факультет Московского государственного университета (www.math.msu.su), - Карельский научный центр РАН (КарНЦ РАН, www.krc.karelia.ru), - Институт биологии КарНЦ РАН (bio.krc.karelia.ru), - Институт леса КарНЦ РАН (forest.krc.karelia.ru), - Институт прикладных математических исследований КарНЦ РАН (mathem.krc.karelia.ru), - Институт экономики КарНЦ РАН (econ.krc.karelia.ru). По указанной выше методике было проведено разбиение на 5 кластеров множества веб-сайтов институтов и факультетов СПбГУ, дополненного указанными восемью сайтами. Были получены следующие кластеры: 1: econ; jf, 2: fvo; history; math; phys; sir; soc; math-mech msu, 3: apmath; bio; chem; law; phil; philosophy; ig krc, 4: arts; politology; Krc RAS; bio krc; forest krc; math krc; econ krc, 5: artes-liberales; dent; earth; gsom; orient; psy; mcdonalds. Сайт механико-математического факультета попал в кластер №2 с 6 сайтами СПбГУ, сайт Института биологии КарНЦ РАН попал в кластер №3 с 6 сайтами СПбГУ, сайт МакДональдс попал в кластер №5 с 6 сайтами СПбГУ. Два сайта СПбГУ попали в кластер №4 с пятью сайтами КарНЦ РАН. Можно сделать вывод о том, что кластеризация по векторам модулярности достаточно хорошо идентифицирует группы сайтов СПбГУ (и КарНЦ тоже), но при этом сами сайты СПбГУ имеют весьма неодинаковую

48 структуру.

49 Выводы и заключение В дипломной работе рассмотрена задача применения вебометрических методов к заданному множеству сайтов с целью исследования вопроса о сходстве структурных характеристик близких по тематике сайтов. В качестве оценки структурной характеристики веб-сайта была взята его модулярность и вектор модулярности, определяемый через мощности модулей, на которые разбивается веб-граф. Была выдвинута гипотеза о том, что тематически одинаковые сайты близки по этим параметрам. Была проделана следующая работа: 1. Был разработан RCCrawler - программа-краулер, сканирующая заданные веб-сайты и строящая их веб-граф. 2. Просканированы сайты институтов и факультетов СПбГУ, а также несколько других сайтов, не относящихся к сайтам СПбГУ, в качестве контрольных образцов. 3. Вычислены меры модулярности просканированных сайтов и построены их вектора модулярности. 4. Произведена процедура разбиения разбиения полученного множества векторов на сравнительно однородные группы методами кластерного анализа. 5. Проведен анализ полученного разбиения. 6. В качестве контрольного теста были построены веб-графы сайтов, не относящихся к СПбГУ, вычислены соответствующие меры модулярности и построены соответствующие вектора модулярности. Эти результаты были добавлены в основную группу, и для полученного множества были повторены пункты 4 и 5. По мере модулярности и по результатам анализа векторов модулярности заданное множество сайтов оказалось неоднородным, однако, его разбиение по этим параметрам дает нам не очень большое количество

50 подмножеств. Таким образом, нельзя утверждать об однозначном подтверждении или опровержении гипотезы: тема требует дальнейшего исследования. По результатам исследования можно отметить, что немалое число сайтов обладает достаточно большой модулярностью и содержит в себе подсайты, которые вполне можно вынести в отдельные веб-ресурсы. Для развития темы и получения более однозначных результатов в будущем необходимо повторить исследование на большем количестве множеств сайтов, объединенных одной тематикой. Разработанное приложение RCCrawler может использоваться для построения веб-графов сайтов с целью последующего их анализа и изучения. Чтобы сделать его более удобным для применения, в дальнейшем планируется реализовать следующее: 1. Механизм выгрузки части данных из оперативной памяти во внешние хранилища. 2. Превращение приложения в сервер и написание к нему клиента с графическим интерфейсом, который будет отправлять команды и получать результаты краулинга. Благодаря заложенной архитектуре эти доработки реализуемы и не столь сложны.

51 Список литературы 1. Björneborn L., Ingwersen P. Toward a basic framework for webometrics // Journal of The American Society for Information Science and Technology. 2004. Vol 55(14). P. 1216-1227. 2. Печников А.А., Чернобровкин Д.И. Об исследованиях веб-графа сайта // Материалы конференции «Управление в технических, эргатических, организационных и сетевых системах». – СПб.: «Концерн «ЦНИИ «Электроприбор», 2012, С. 1069-1072. 3. Pant G. Crawling the Web / G. Pant, P. Srinivasan, F. Menczer // In Web Dynamics. M. Levene and A. Poulovassilis, eds. Springer, 2004. P.153-178. 4. Schonfeld U., Bar-Yossef Z., Keidar I. Do not crawl in the dust: different URLs with similar text // ACM Journal Name, Vol. 3. No.1. 2009. P. 111–131. 5. Newman M.E.J. Modularity and community structure in networks // Proceedings of the National Academy of Sciences of the United States of America. 2006. 103(23). P. 8577–8582. 6. Zhukov L. Network communities [Электронный ресурс]. – режим доступа: http://www.leonidzhukov.net/hse/2014/socialnetworks/lectures/lecture7.pdf. 7. Целых А.А., Целых А.Н., Матвеев Д.А. Методы и средства визуализации массивов научно-технических показателей в виде графов // Современные проблемы науки и образования. 2013. №3. URL: http://www.scienceeducation.ru/ru/article/view?id=9421 (дата обращения: 14.04.2016). 8. Learn how to use Gephi [Электронный ресурс]. – режим доступа: https://gephi.org/users. 9. Левитин А.В. Алгоритмы. Введение в разработку и анализ / М.: Вильямс, 2006. 576 с. 10. Буреева Н.Н. Многомерный статистический анализ с использованием ППП “STATISTICA” / Нижний Новгород, 2007, 112 с. 11. Status codes in HTTP [Электронный ресурс]. – режим доступа: https://www.w3.org/Protocols/HTTP/HTRESP.html. 12. HTTP 300 Status Codes | AT&T Developer [Электронный ресурс]. – режим д о с т у п а : http://developer.att.com/application-resource- optimizer/docs/best-practices/http-300-status-codes.

52 13. HTTP/1.1: Header field definitions [Электронный ресурс]. – режим доступа: https://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html. 14. Network Working Group. RFC 3986 — Uniform Resource Identifier (URI): Generic Syntax. 15. URL normalization - Wikipedia, the free encyclopedia [Электронный ресурс]. – режим доступа: https://en.wikipedia.org/wiki/URL_normalization.

53 Приложение Приложение 1. Использованный файл settings.ini. ApplicationManager = "TextFileAM" ApplicationFinishers = "WorkIsDoneAF,TimeoutAF,StopFileAF" DataManager = "BMICDM" DownloadingThread = "DT0" ParsingThread = "PT0" ParsingThreadsCount = 2 RoutineThread = "RT0" UrlAnalyzingThread = "EmptyUAT" ResultUnloaders = "GephiSiteGraphRU,TestRU" DownloadingThreadPDChunkSizeMultiplier = 5 ParsingThreadPDChunkSize = 20 DownloadingThreadSleepTime = 1 ParsingThreadSleepTime = 1 RoutineThreadSleepTime = 1000 CommonLogFile = "logs/common_log.csv" ErrorLogFile = "logs/error_log.csv" DisplayCommonLog = 1 DisplayErrorLog = 1 RobotsTxtClass = "OnlyDisallowRobotsTxt" TimeoutSeconds = 240000 ResultFolder = "result" SaveDuplicates = 1 StopFile = "stop.txt"

54 Приложение 2. Использованный файл hosts.txt. http://www.apmath.spbu.ru/;2;-1;0 http://fvo.spbu.ru;2;-1;0 http://dent.spbu.ru;2;-1;0 http://gsom.spbu.ru;2;-1;0 http://chem.spbu.ru;2;-1;0 https://history.spbu.ru;2;-1;0 http://jf.spbu.ru;2;-1;0 http://www.psy.spbu.ru;2;-1;0 http://arts.spbu.ru;2;-1;2500 http://sir.spbu.ru;2;-1;0 http://politology.spbu.ru;2;-1;0 http://orient.spbu.ru;2;-1;0 http://phys.spbu.ru;2;-1;0 http://soc.spbu.ru;2;-1;0 http://philosophy.spbu.ru;2;-1;0 http://earth.spbu.ru;2;-1;0 http://math.spbu.ru;2;-1;1000 http://phil.spbu.ru;2;-1;0 http://econ.spbu.ru;2;-1;0 http://law.spbu.ru;2;-1;0 http://bio.spbu.ru;2;4;2500 http://artesliberales.spbu.ru;2;-1;1500

55 Приложение 3. Использованные настройки укладки графа.

56 Приложение 4. Описание параметров settings.ini. ApplicationManager Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация ApplicationManager Строка TextFileAM Всегда "TextFileAM" ApplicationFinishers Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализации ApplicationFinisher через запятую Строка Од н о и л и н е с кол ь ко з н ач е н и й и з м н оже с т ва {WorkIsDoneAF,TimeoutAF,StopFileAF} Всегда "WorkIsDoneAF,TimeoutAF,StopFileAF" CommonLogFile Описание: Тип значения: Диапазон значений: Требуется: Пример: Путь к файлу общего лога Строка Любой валидный относительный или абсолютный файловый путь в системе. Папки, входящий в путь, не создаются автоматически. Всегда "logs/common_log.csv" DataManager Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация DataManager Строка BMICDM Всегда "BMICDM" DisplayCommonLog Описание: Тип значения: Диапазон значений: Требуется: Пример: Выводить ли общий лог в консоль Логическое {0,1} или {false,true} Всегда 1 DisplayErrorLog Описание: Тип значения: Диапазон значений: Требуется: Выводить ли лог ошибок в консоль Логическое {0,1} или {false,true} Всегда

57 Пример: 1 DownloadingThread Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация DownloadingThread Строка DT0 Всегда DT0 DownloadingThreadPDChunkSizeMultiplier Описание: Тип значения: Диапазон значений: Требуется: Пример: Максимальный размер набора PageData, запрашиваемых реализацией DownloadingThread у реализации DataManager для с к ач и в а н и я , п о с а й т у в ы ч и с л я е т с я п о ф о р м ул е : DownloadingThreadPDChunkSizeMultiplier * Количество_одновременных_соединений_с_сайтом. Последнее число будет описано в следующем подразделе. Целое число [1,2147483647/max(Количество_одновременных_соединений_с _сайтом)] Всегда 6 DownloadingThreadSleepTime Описание: Тип значения: Диапазон значений: Требуется: Пример: Комментарий: Время сна потока DownloadingThread в миллисекундах Целое число [0, 2147483647] Всегда 1 Для снижения нагрузки на процессор поток DT0 спит каждую итерацию цикла заданное время. По результатам тестирования RCCrawler было выявлено, что значение в 1мс не влияет на скорость краулинга, но не позволяет загружать ядро процессора полностью. Для выявления основательных результатов т ребует ся изучение работы RCCrawler п р и с ко р о с т и соединения с сетью Интернет намного выше 100 МБит/ c на загрузку и краулинга одновременно многих сайтов с целью загрузить канал. ErrorLogFile Описание: Тип значения: Диапазон значений: Требуется: Пример: Путь к файлу лога ошибок Строка Любой валидный относительный или абсолютный файловый путь в системе. Папки, входящий в путь, не создаются автоматически. Всегда "logs/error_log.csv"

58 ParsingThread Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация ParsingThread Строка PT0 Всегда "PT0" ParsingThreadPDChunkSize Описание: Тип значения: Диапазон значений: Требуется: Пример: М а к с и м а л ь н о е ко л и ч е с т в о PageData, запрашиваемо е реализацией ParsingThread у реализации DataManager Целое число [1, 2147483647] Всегда 10 ParsingThreadsCount Описание: Тип значения: Диапазон значений: Требуется: Пример: Количе ство ре а лизаций ParsingThread, р а б о т а ю щ и х в приложении Целое число [1, Количество_ядер_в_процессоре] Всегда 3 ParsingThreadSleepTime Описание: Тип значения: Диапазон значений: Требуется: Пример: Время сна реализации ParsingThread во время отсутствия работы в миллисекундах Целое число [0, 2147483647] Всегда 1 ResultFolder Описание: Тип значения: Диапазон значений: Требуется: Пример: Каталог выгрузки результата работы краулера Строка Любой валидный относительный или абсолютный путь к каталогу в системе. Папки, входящий в путь, не создаются автоматически. Всегда "result" ResultUnloaders Описание: Тип значения: Диапазон значений: Требуется: Реализации ResultUnloader через запятую Строка Одно или несколько из множества {TestRU,GephiSiteGraphRU} Всегда

59 Пример: "TestRU,GephiSiteGraphRU" RobotsTxtClass Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация RobotsTxt Строка Одно из множества {OnlyDisallowRobotsTxt, DummyRobotsTxt} Всегда "DummyRobotsTxt" RoutineThread Описание: Тип значения: Диапазон значений: Требуется: Пример: Реализация RoutineThread Строка RT0 Всегда "RT0" RoutineThreadSleepTime Описание: Тип значения: Диапазон значений: Требуется: Пример: Время сна для реализации RoutineThread в случае отсутствия работы в миллисекундах Целое число [0, 2147483647] Всегда 1000 SaveDuplicates Описание: Тип значения: Диапазон значений: Требуется: Пример: Комментарий Хранить ли PageData, страницы соответствующие которым являются дублем страниц, встреченных ранее Логическое {0,1} или {false,true} Всегда true Истинное значение увеличивает количество потребляемой оперативной памяти, но исключает повторное скачивание страниц-дублей StopFile Описание: Тип значения: Диапазон значений: Требуется: Пример: Путь к файлу, появление которого останавливает приложение ( р а б о т а е т т о л ь ко , е с л и в ApplicationsFinishers указан StopFileAF) Строка Любой валидный относительный или абсолютный путь к файлу в системе. Папки, входящий в путь, не создаются автоматически. Если в ApplicationsFinishers указан StopFileAF "Stop.txt"

60 TimeoutSeconds Описание: Тип значения: Диапазон значений: Требуется: Пример: Таймаут в секундах по которому приложение заканчивает работу (работает только, если в ApplicationsFinishers указан TimeoutAF) Целое число [0, 2147483647] Если в ApplicationsFinishers указан TimeoutAF 34000 Такие параметры как DownloadingThreadPDChunkSizeMultiplier ParsingThreadPDChunkSize, ParsingThreadSleepTime, RoutineThreadTime созданы чтобы помочь сделать работу максимально эффективной. Это связано с блокировкой ресурсов в хранилищах DataManager.

61 Приложение 5. Описание файла hosts.txt. Данный файл должен представлять из себя набор строк следующего формата: [#]{Протокол}://{Имя хоста};{Максимальное количество одновременных соединений};{Максимальный уровень};{Задержка краулинга} Если строка начинается с #, то она игнорируется. Протокол - значений из множества {http,https}. Максимальное количество одновременных соединений - целое число в диапазоне [1, 2147483647]. Не рекомендуется выбирать большое число, зависит от производительности сайта. Минимальным рекомендуется выбирать 2, так как некоторые страницы могут отдаваться сервером довольно медленно, и тем временем, можно получить на параллельном соединении несколько других страниц. Максимальный уровень - максимальный уровень сканирования включительно. В данном случае под уровнем понимается уровень страниц минимальное количество переходов по гиперссылкам с главной страницы на текущую. Диапазон значений: [-2147483648, 2147483647]. Если задано отрицательное значение, то уровень не ограничен. Задержка краулинга - время в миллисекундах, ожидаемое перед тем, как начать скачивание страницы. Данное время применяется для каждого соединения и не делится на их количество. Следует отметить, что даже в случае необходимости задержки краулинга максимальное количество соединений разумнее выбирать равное двум и просто увеличивать задержку для одного соединения в 2 раза. Пример строки файла hosts.txt: http://www.apmath.spbu.ru;4;-1;0

62 Приложение 6. Фрагменты исходного текста программы RCCrawler. Полная версия исходного текста программы RCCrawler размещена по адресу http://www.apmath.spbu.ru/ru/staff/pechnikov_aa/files/programmnyy_kod_RCCrawler.docx. RCCrawler.pro QT += core network sql QT -= gui CONFIG += c++11 TARGET = RCCrawler CONFIG += console CONFIG -= app_bundle TEMPLATE = app PRECOMPILED_HEADER = precompiled_headers.h SOURCES += main.cpp \ objectcreator.cpp \ application_managers/applicationmanager.cpp \ application_finishers/applicationfinisher.cpp \ data_managers/datamanager.cpp \ data_structures/hostdata.cpp \ data_structures/pagearc.cpp \ threads/downloadingthread.cpp \ threads/parsingthread.cpp \ threads/rccbasethread.cpp \ data_managers/bmicdm.cpp \ data_structures/pagedata.cpp \ application_finishers/workisdoneaf.cpp \ application_managers/textfileam.cpp \ result_unloaders/resultunloader.cpp \ result_unloaders/gephisitegraphru.cpp \ threads/dt0.cpp \ threads/pt0.cpp \ result_unloaders/testru.cpp \ qreplytimeout.cpp \ rccsettings.cpp \ data_structures/pdlogitem.cpp \ robots_txt/robotstxt.cpp \ data_structures/robotstxtrule.cpp \ robots_txt/onlydisallowrobotstxt.cpp \ helpercreator.cpp \ application_finishers/timeoutaf.cpp \ robots_txt/dummyrobotstxt.cpp \ delayedpdpass.cpp \ data_structures/hostdownloaddata.cpp \ application_finishers/stopfileaf.cpp \ threads/routinethread.cpp \ threads/rt0.cpp \ data_structures/pdandpacreatedata.cpp \ rccapplication.cpp

63 HEADERS += \ includes.h \ objectcreator.h \ application_managers/applicationmanager.h \ application_finishers/applicationfinisher.h \ objects.h \ rccconsts.h \ data_managers/datamanager.h \ data_structures/hostdata.h \ data_structures/pagearc.h \ data_structures/pagedata.h \ threads/downloadingthread.h \ threads/parsingthread.h \ threads/rccbasethread.h \ data_structures/pdstore.h \ data_managers/bmicdm.h \ baseobjects.h \ data_structures/pastore.h \ application_finishers/workisdoneaf.h \ application_managers/textfileam.h \ result_unloaders/resultunloader.h \ result_unloaders/gephisitegraphru.h \ threads/dt0.h \ threads/pt0.h \ result_unloaders/testru.h \ qreplytimeout.h \ rccsettings.h \ data_structures/pdlogitem.h \ robots_txt/robotstxt.h \ data_structures/robotstxtrule.h \ robots_txt/onlydisallowrobotstxt.h \ helpers.h \ helpercreator.h \ application_finishers/timeoutaf.h \ robots_txt/dummyrobotstxt.h \ delayedpdpass.h \ data_structures/hostdownloaddata.h \ application_finishers/stopfileaf.h \ threads/routinethread.h \ threads/rt0.h \ precompiled_headers.h \ data_structures/pdandpacreatedata.h \ rccapplication.h RESOURCES += \ resource.qrc data_structures/pagedata.h #ifndef PAGEDATA_H #define PAGEDATA_H #include "includes.h" #include "hostdata.h" struct PageData { PageData();//не присваивает id PageData(const ulong &id, const QString& url, HostData *phD);

64 PageData(const ulong &id, const QString& url, const QString& normalizedUrl, HostData *phD); QString toString() const; static static static static static ulong newIdUnsafe(); ulong newIdSafe(); uint hashContent(const QString& content); ulong lastId; QString normalizeUrl(const QString &urlStr); ulong id; HostData* phD; QString url; QString normalizedUrl; ulong idFrom; uint level; uint outDegree; bool blocked; bool downloaded; bool parsed; QString content; uint contentHash; uint errorCode; ulong replaceId; uint downloadAttempts; bool remove; }; typedef QVector<PageData> PDContainer; data_structures/pagearc.h #ifndef PAGEARC_H #define PAGEARC_H #include "includes.h" struct PageArc { PageArc(); PageArc(const ulong &from, const ulong &to); PageArc(const ulong &id, const ulong &from, const ulong &to); ulong id; ulong from; ulong to; static ulong newIdUnsafe(); static ulong newIdSafe(); static ulong lastId; QString toString() const; }; #endif // PAGEARC_H data_managers/datamanager.h #ifndef DATAMANAGER_H #define DATAMANAGER_H #include "includes.h"

65 #include "rccconsts.h" #include #include #include #include "data_structures/pagedata.h" "data_structures/pagearc.h" "data_structures/pdlogitem.h" "data_structures/pdandpacreatedata.h" typedef QVector<PageArc> PAContainer; typedef QQueue<PDLogItem> PDLIContainer; typedef QVector<PDPACreateData> PDPAContainer; class DataManager { public: enum LogType { CommonLog, ErrorLog }; DataManager(); virtual ~DataManager(); virtual virtual virtual virtual bool addHost(HostData* phD) = 0; bool allWorkIsDone() = 0; QVector<HostData*> getHosts() = 0; void getPDsStartingFromId(PDContainer &result, const ulong &id, const int& countMultiplier = RCCConsts::PAGEDATA_CHUNK_SIZE_COUNT_MULTIPLIER) = 0; virtual void getPAsStartingFromId(PAContainer &result, const ulong &id, const int& count = RCCConsts::PAGEDATA_DEFAULT_CHUNK_SIZE) = 0; virtual void getFreePDsForDownloading(PDContainer &result, HostData *phD, const int& countMultiplier = RCCConsts::PAGEDATA_DEFAULT_CHUNK_SIZE) = 0; virtual void getFreePDsForParsing(PDContainer &result, const int& count = RCCConsts::PAGEDATA_DEFAULT_CHUNK_SIZE) = 0; virtual void insertPDs(const PDContainer &pDs) = 0; virtual void addPDsAndPAs(const PDPAContainer &pDPAs) = 0; virtual void updatePDs(const PDContainer &pDs) = 0;//метод должен удалять, если стоит remove virtual std::pair<bool, PageData> contentSeen(HostData* phD, const QString& content) = 0; virtual void insertPAs(const PAContainer& pAs) = 0; virtual void changePAsByTo(const int &to, const int &newTo) = 0; //Лог virtual PDLIContainer* getLog(const DataManager::LogType &logType, const int size = INT_MAX) = 0; virtual void insertLogItem(const DataManager::LogType &logType, const PDLogItem& pDLI) = 0; virtual void insertLogItems(const DataManager::LogType &logType,const QVector<PDLogItem> &items) = 0; }; #endif // DATAMANAGER_H data_structures/pdstore.h #ifndef PDSTORE_H #define PDSTORE_H

66 #include "includes.h" #include "pagedata.h" using namespace boost::multi_index; namespace PD { struct ById{}; struct ByBlocked{}; struct ByPhDAndBlockedAndDownloaded{}; struct ByBlockedAndDownloadedAndParsedAndErrorCode{}; struct ByPhDAndContentHash{}; struct ByUrlAndPhD{}; struct ByPhDAndNormalizedUrl{}; struct ByIdFrom{}; struct BlockedChange : public std::unary_function<PageData,void> { bool b; BlockedChange(const bool& _b) : b(_b) {} void operator()(PageData& pd) { pd.blocked = b; } }; struct LevelChange : public std::unary_function<PageData,void> { uint l; LevelChange(const uint& _l) : l(_l) {} void operator()(PageData& pd) { pd.level = l; } }; } typedef boost::multi_index_container<PageData, indexed_by< ordered_non_unique< tag<PD::ById>, member<PageData, ulong, &PageData::id> >, ordered_non_unique< tag<PD::ByBlocked>, member<PageData, bool, &PageData::blocked> >, ordered_non_unique< tag<PD::ByPhDAndBlockedAndDownloaded>, composite_key< PageData, member<PageData,HostData*,&PageData::phD>, member<PageData,bool,&PageData::blocked>, member<PageData,bool,&PageData::downloaded> > >, ordered_non_unique< tag<PD::ByBlockedAndDownloadedAndParsedAndErrorCode>, composite_key< PageData, member<PageData,bool,&PageData::blocked>, member<PageData,bool,&PageData::downloaded>, member<PageData,bool,&PageData::parsed>, member<PageData,uint,&PageData::errorCode> > >,

67 ordered_non_unique< tag<PD::ByPhDAndContentHash>, composite_key< PageData, member<PageData,HostData*,&PageData::phD>, member<PageData,uint,&PageData::contentHash> > >, ordered_unique< tag<PD::ByPhDAndNormalizedUrl>, composite_key< PageData, member<PageData,HostData*,&PageData::phD>, member<PageData,QString,&PageData::normalizedUrl> > >, ordered_non_unique< tag<PD::ByIdFrom>, member<PageData, ulong, &PageData::idFrom> > > > PDStore; typedef PDStore::index<PD::ByBlocked>::type BlockedList; #endif // PDSTORE_H application_managers/textfileam.cpp #include "textfileam.h" TextFileAM::TextFileAM() { _pdM = _setupDataManager(); _setupThreads(); _setupApplicationFinishers(); _startThreads(); } int TextFileAM::run() { RCCSettings *psett = RCCSettings::instance(); QElapsedTimer runTimer; runTimer.start(); while(true) { _app->processEvents(); _app->thread()->msleep(1000); bool finish = false; for (auto pfinisher: _appFs) { if (pfinisher->needToFinishApplication()) { finish = true; break; } } if (finish) { _stopThreads(); int crawlingTime = runTimer.elapsed() / 1000; QStringList rUNames = psett->value( "ResultUnloaders", "r").toString().split(","); for (auto rUName: rUNames) {

68 ResultUnloader *prU = ObjectCreator::resultUnloader(rUName.trimmed(), _pdM); prU->unloadResult(); delete prU; } int unloadTime = runTimer.elapsed() / 1000 - crawlingTime; qDebug() << "Work is done." << "Crawling time: << "Unload time: " << "Press Enter to std::cin.get(); } break; } } return 0; << endl " << crawlingTime << "s." << endl << unloadTime << "s." << endl exit";

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв