Аналіз структури сайту з використанням поняття модулярності

Анотація

У роботі здійснюється аналіз структури веб-сайту, який має ієрархічну організацію розділів. Ієрархічна структура передбачає розбиття всієї інформації на окремі категорії за темами. Гіпертекстову модель веб-сайту зображено математичною моделлю у вигляді орієнтованого незваженого веб-графу, вершинами якого є web-сторінки, а ребрами — гіперпосилання між ними. Висувається гіпотеза, що сторінка, яка посилається на іншу, має з нею тематичну схожість, а групи пов’язаних між собою сторінок утворюють кластер.

З використанням локальної інформації про гіперпосилання між сторінками сайту здійснюється кластеризація сторінок. Для оцінки якості кластеризації використовується функціонал модулярності, який характеризує різницю між долею ребер у середині кластеру при заданому розбитті та долею ребер, якщо б вони були сгенеровані в графі випадковим чином. Випадковий граф обирається у якості нульової моделі.

Алгоритм було реалізовано у вигляді прикладного програмного забезпечення, побудованого із використанням принципів функціонального програмування, та застосовано для аналізу структури сайту інтернет-магазину. Досліджено залежність значення функціоналу від кількості кластерів розбиття та параметрів ітераційного процесу.Для максимізації значень функціоналу модулярності застосовується Лувенський метод. Розроблено жадібну схему алгоритму, яка зводить задачу до послідовності локальних задач оптимізації. Пропонується здійснювати відбір пар «вершина — кластер», з’єднання яких призводить до збільшення значення функціоналу модулярності. Для довільної вершини графу відшукується цільовий кластер виходячи з аналізу списків суміжності вершини.

Здійснено аналіз контенту сторінок веб-сайту всередині кластера, який виявив їх тематичну схожість. Для більшості кластерів є можливим формування семантичного опису. Виконано порівняння результатів кластеризації з експертним розбиттям, обчислено значення точності та повноти розбиття на кластери.