Analysis of the Site Structure Using the Concept of Modularity

The analysis of the structure of the website, which has a hierarchical organization of sections, is carried out. The hierarchical structure the division of all information into separate categories by topic is involved. The hypertext model of a website is represented by a mathematical model in the fo...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2020
Автори:	Гук, Наталія, Диханов, Станіслав, Долотов, Іван
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Кам'янець-Подільський національний університет імені Івана Огієнка 2020
Онлайн доступ:	http://mcm-math.kpnu.edu.ua/article/view/224943
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Mathematical and computer modelling. Series: Physical and mathematical sciences

Репозитарії

Mathematical and computer modelling. Series: Physical and mathematical sciences

id	mcm-mathkpnueduua-article-224943
record_format	ojs
institution	Mathematical and computer modelling. Series: Physical and mathematical sciences
collection	OJS
language	Ukrainian
format	Article
author	Гук, Наталія Диханов, Станіслав Долотов, Іван
spellingShingle	Гук, Наталія Диханов, Станіслав Долотов, Іван Analysis of the Site Structure Using the Concept of Modularity
author_facet	Гук, Наталія Диханов, Станіслав Долотов, Іван
author_sort	Гук, Наталія
title	Analysis of the Site Structure Using the Concept of Modularity
title_short	Analysis of the Site Structure Using the Concept of Modularity
title_full	Analysis of the Site Structure Using the Concept of Modularity
title_fullStr	Analysis of the Site Structure Using the Concept of Modularity
title_full_unstemmed	Analysis of the Site Structure Using the Concept of Modularity
title_sort	analysis of the site structure using the concept of modularity
title_alt	Аналіз структури сайту з використанням поняття модулярності
description	The analysis of the structure of the website, which has a hierarchical organization of sections, is carried out. The hierarchical structure the division of all information into separate categories by topic is involved. The hypertext model of a website is represented by a mathematical model in the form of an oriented unweighted web graph. Web pages are vertices of a graph, and hyperlinks between them are edges of a graph. A hypothesis is put forward about the thematic coherence of pages that link to each other. Groups of related pages are thought to form a cluster. Using local information about hyperlinks between site pages, site pages are clustered. As a clustering quality metric the modularity functional is used. Modularity characterizes the difference between the fraction of edges within a cluster at a given partition and the fraction of edges if they were generated in the graph at random. A random graph as the zero model is chosen. The Louvain method to maximize the values of the modularity functional is used. A greedy scheme of the algorithm, which reduces the problem to a sequence of local optimization problems, is developed. It is proposed to select vertex-cluster pairs, the connection of which leads to an increase in the value of the modularity functional. For an arbitrary vertex of the graph, the target cluster is found based on the analysis of the lists of adjacency of the vertex. Using the principles of functional programming application software that implements the algorithm is developed. The software to analyze the structure of the online store site is used. The dependence of the value of the modularity functional on the number of partition clusters and the parameters of the iterative process is investigated. Analysis of the content of the website pages within the cluster, which revealed their thematic similarity, was performed. For most clusters the formation of a semantic description is possible. The results of clustering are compared with the expert partition. The values of accuracy and completeness of division into clusters are calculated.
publisher	Кам'янець-Подільський національний університет імені Івана Огієнка
publishDate	2020
url	http://mcm-math.kpnu.edu.ua/article/view/224943
work_keys_str_mv	AT guknatalíâ analysisofthesitestructureusingtheconceptofmodularity AT dihanovstaníslav analysisofthesitestructureusingtheconceptofmodularity AT dolotovívan analysisofthesitestructureusingtheconceptofmodularity AT guknatalíâ analízstrukturisajtuzvikoristannâmponâttâmodulârností AT dihanovstaníslav analízstrukturisajtuzvikoristannâmponâttâmodulârností AT dolotovívan analízstrukturisajtuzvikoristannâmponâttâmodulârností
first_indexed	2024-04-21T19:24:44Z
last_indexed	2024-04-21T19:24:44Z
_version_	1796973511175045120
spelling	mcm-mathkpnueduua-article-2249432021-02-17T11:21:21Z Analysis of the Site Structure Using the Concept of Modularity Аналіз структури сайту з використанням поняття модулярності Гук, Наталія Диханов, Станіслав Долотов, Іван The analysis of the structure of the website, which has a hierarchical organization of sections, is carried out. The hierarchical structure the division of all information into separate categories by topic is involved. The hypertext model of a website is represented by a mathematical model in the form of an oriented unweighted web graph. Web pages are vertices of a graph, and hyperlinks between them are edges of a graph. A hypothesis is put forward about the thematic coherence of pages that link to each other. Groups of related pages are thought to form a cluster. Using local information about hyperlinks between site pages, site pages are clustered. As a clustering quality metric the modularity functional is used. Modularity characterizes the difference between the fraction of edges within a cluster at a given partition and the fraction of edges if they were generated in the graph at random. A random graph as the zero model is chosen. The Louvain method to maximize the values of the modularity functional is used. A greedy scheme of the algorithm, which reduces the problem to a sequence of local optimization problems, is developed. It is proposed to select vertex-cluster pairs, the connection of which leads to an increase in the value of the modularity functional. For an arbitrary vertex of the graph, the target cluster is found based on the analysis of the lists of adjacency of the vertex. Using the principles of functional programming application software that implements the algorithm is developed. The software to analyze the structure of the online store site is used. The dependence of the value of the modularity functional on the number of partition clusters and the parameters of the iterative process is investigated. Analysis of the content of the website pages within the cluster, which revealed their thematic similarity, was performed. For most clusters the formation of a semantic description is possible. The results of clustering are compared with the expert partition. The values of accuracy and completeness of division into clusters are calculated. У роботі здійснюється аналіз структури веб-сайту, який має ієрархічну організацію розділів. Ієрархічна структура передбачає розбиття всієї інформації на окремі категорії за темами. Гіпертекстову модель веб-сайту зображено математичною моделлю у вигляді орієнтованого незваженого веб-графу, вершинами якого є web-сторінки, а ребрами — гіперпосилання між ними. Висувається гіпотеза, що сторінка, яка посилається на іншу, має з нею тематичну схожість, а групи пов’язаних між собою сторінок утворюють кластер. З використанням локальної інформації про гіперпосилання між сторінками сайту здійснюється кластеризація сторінок. Для оцінки якості кластеризації використовується функціонал модулярності, який характеризує різницю між долею ребер у середині кластеру при заданому розбитті та долею ребер, якщо б вони були сгенеровані в графі випадковим чином. Випадковий граф обирається у якості нульової моделі. Алгоритм було реалізовано у вигляді прикладного програмного забезпечення, побудованого із використанням принципів функціонального програмування, та застосовано для аналізу структури сайту інтернет-магазину. Досліджено залежність значення функціоналу від кількості кластерів розбиття та параметрів ітераційного процесу.Для максимізації значень функціоналу модулярності застосовується Лувенський метод. Розроблено жадібну схему алгоритму, яка зводить задачу до послідовності локальних задач оптимізації. Пропонується здійснювати відбір пар «вершина — кластер», з’єднання яких призводить до збільшення значення функціоналу модулярності. Для довільної вершини графу відшукується цільовий кластер виходячи з аналізу списків суміжності вершини. Здійснено аналіз контенту сторінок веб-сайту всередині кластера, який виявив їх тематичну схожість. Для більшості кластерів є можливим формування семантичного опису. Виконано порівняння результатів кластеризації з експертним розбиттям, обчислено значення точності та повноти розбиття на кластери. Кам'янець-Подільський національний університет імені Івана Огієнка 2020-09-18 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/224943 10.32626/2308-5878.2020-21.99-114 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2020: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 21; 99-114 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2020: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 21; 99-114 2308-5878 10.32626/2308-5878.2020-21 uk http://mcm-math.kpnu.edu.ua/article/view/224943/224992

Analysis of the Site Structure Using the Concept of Modularity

Репозитарії

Схожі ресурси