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

Рис. 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.

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

Для остальных кластеров существенное влияние на такое разбиение оказывают значения первых элементов векторов модулярности. В третьем кластере оно находится  в пределах от 1127 до 2034, в четвертом от 2045 до 5142, а в пятом от 101 до 793. Можно говорить о « маленьком», «среднем» и «большом» максимальном модуле, оказывающем большое влияние на кластеризацию.

Нас в большей степени интересуют не столько размеры, сколько подобие («похожесть») структур сайтов. Поэтому следующая кластеризация была проведена на нормализованном множестве векторов модулярности.

Рис. 25. Дендрограмма для множества веб-сайтов СПбГУ (случай нормализованных векторов модулярности)

Нормализованный вектор модулярности получается из вектора модулярности делением каждого элемента вектора на общее количество вершин в графе. К примеру, вектор модулярности сайта биологического факультета [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 изображения визуализации двух сайтов из одного (пятого) кластера.

https://history. spbu. ru	http://fvo. spbu. ru

Рис. 26. Сайты Института истории и Факультета военного обучения

Сайт Института истории содержит 1574 страницы и 82219 дуг, а сайт Факультета военного обучения – 342 страницы и 45358 дуг. Тем не менее, их структура очень похожа.

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

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

Были отсканированы 8 сайтов, не относящихся к сайтам СПбГУ:

- компания МакДональдс в России (www. mcdonalds. ru),

- механико-математический факультет Московского государственного университета (www. math. ),

- Карельский научный центр РАН (КарНЦ РАН, 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 с пятью сайтами КарНЦ РАН.

Можно сделать вывод о том, что кластеризация по векторам модулярности достаточно хорошо идентифицирует группы сайтов СПбГУ (и КарНЦ тоже), но при этом сами сайты СПбГУ имеют весьма неодинаковую структуру.

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

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

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

Была выдвинута гипотеза о том, что тематически одинаковые сайты близки по этим параметрам.

Была проделана следующая работа:

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

2. Просканированы сайты институтов и факультетов СПбГУ, а также несколько других сайтов, не относящихся к сайтам СПбГУ, в качестве контрольных образцов.

3. Вычислены меры модулярности просканированных сайтов и построены их вектора модулярности.

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

5. Проведен анализ полученного разбиения.

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

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

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

Для развития темы и получения более однозначных результатов в будущем необходимо повторить исследование на большем количестве множеств сайтов, объединенных одной тематикой.

Разработанное приложение RCCrawler может использоваться для построения веб-графов сайтов с целью последующего их анализа и изучения. Чтобы сделать его более удобным для применения, в дальнейшем планируется реализовать следующее:

1. Механизм выгрузки части данных из оперативной памяти во внешние хранилища.

2. Превращение приложения в сервер и написание к нему клиента с графическим интерфейсом, который будет отправлять команды и получать результаты краулинга.

Благодаря заложенной архитектуре эти доработки реализуемы и не столь сложны.

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

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. , Об исследованиях веб-графа сайта // Материалы конференции «Управление в технических, эргатических, организационных и сетевых системах». – СПб.: «Концерн «ЦНИИ «Электроприбор», 2012, С. 1069-1072. 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. 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. 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. Zhukov work communities [Электронный ресурс]. – режим доступа: http://www. /hse/2014/socialnetworks/lectures/lecture7.pdf. , , Матвеев и средства визуализации массивов научно-технических показателей в виде графов // Современные проблемы науки и образования. 2013. №3. URL: http://www. science-education. ru/ru/article/view? id=9421 (дата обращения: 14.04.2016). Learn how to use Gephi [Электронный ресурс]. – режим доступа: https://gephi. org/users. Левитин . Введение в разработку и анализ / М.: Вильямс, 2006. 576 с. Буреева статистический анализ с использованием ППП “STATISTICA” / Нижний Новгород, 2007, 112 с. Status codes in HTTP [Электронный ресурс]. – режим доступа: https://www. w3.org/Protocols/HTTP/HTRESP. html. HTTP 300 Status Codes | AT&T Developer [Электронный ресурс]. – режим доступа: http://developer. /application-resource-optimizer/docs/best-practices/http-300-status-codes. HTTP/1.1: Header field definitions  [Электронный ресурс]. – режим доступа:  https://www. w3.org/Protocols/rfc2616/work Working Group. RFC 3986 — Uniform Resource Identifier (URI): Generic Syntax. URL normalization - Wikipedia, the free encyclopedia  [Электронный ресурс]. – режим доступа: https://en. wikipedia. org/wiki/URL_normalization.

Приложение

Приложение 1. Использованный файл settings. ini.

ApplicationManager = "TextFileAM"

ApplicationFinishers = "WorkIsDoneAF, TimeoutAF, StopFileAF"