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

1 Исследование регламентируемых фрагментов российского Веба Печников Андрей Анатольевич, к.ф.-м.н., ст.н.с. Институт прикладных математических исследований Карельского научного центра РАН

2 2 Регламентируемый веб-ресурс - это веб-ресурс, для которого существует (должен существовать) нормативный документ, в котором изложены цели, задачи, основные структурные составляющие, правила обновления, добавления и изменения информации веб-ресурса. Целевое множество - задаваемое прямым перечислением множество регламентируемых сайтов. Сопутствующее множество - множество сайтов, не входящих в целевое множество, на которые существуют гиперссылки с сайтов целевого множества. Фрагмент Веба - объединение сайтов целевого и сопутствующего множеств и множество связывающих их гиперссылок. 2

3 3 Объекты исследований : академический фрагмент Веба (целевое множество – официальные сайты научных учреждений РАН); университетский фрагмент Веба (целевое множество – официальные сайты классических университетов РФ); бюрократический фрагмент Веба (целевое множество – официальные сайты органов государственной власти Республики Карелия). 3

4 Информационная система для вебометрических исследований: 1.Робот-сборщик гиперссылок 2.База данных Операции, функции, фильтры БД ВИ: Разработаны около 20 штук по мере возникновения необходимости. Первая – ВЫБОРКА,.... затем – ССЫЛКИ НА ЗАДАННЫЙ САЙТ, ССЫЛКИ С ЗАДАННОГО САЙТА, СОПУТСТВУЮЩЕЕ МНОЖЕСТВО,.... МАТРИЦА СМЕЖНОСТИ,..... И т.д. 4

5 5 Академический Веб: 288 сайтов целевого множества, отсканированы все, 2,190,000 страниц, обнаруженных ссылок – 720,000, из них уникальных Из сайтов сопутствующего множества отсканировано 2300, обнаруженных ссылок – 1,100,000, из них уникальных уровень, откуда, зачем, куда Пример Уникальная гиперссылка – это ссылка из множества всех гиперссылок, имеющих одинаковый контекст и адрес целевой страницы, сделанная со страницы с наивысшим уровнем.

6 6 Много ссылок – с 10 и более сайтов из T, Мало – менее, чем с 10 сайтов из T. На примере академического Веба

7 Диаграмма академического Веба Дробь N/R обозначает количество сайтов, входящих в данное подмножество ( N ) и среднее количество уникальных гиперссылок, сделанных на сайты этого подмножества с целевого множества ( R ).

8 Вывод 1: слабая связность на целевом множестве Максимальная компонента сильной связности содержит 175 сайтов и имеет диаметр, равный 6 (вершины более темного цвета), а каждая из остальных 113 состоит из единственной вершины (более светлые вершины).

9 Прикладные проблемы управления макросистемами Академические коллекторы (17) 1РФФИ1029 2Научная электронная библиотека621 3ВАК443 4Московский государственный университет334 5МАИК Наука_Интерпериодика532 6Роснаука РФ263 Примеры: Сайты-коммуникаторы академического Веба Академические посредники (8) 1Новосибирский государственный университет2710 2Отделение ГПНТБ СО РАН2314 3Междисциплинарный научный сервер Московский физико-технический институт2213 5Библиотека по естественным наукам РАН Новосибирский государственный технический университет1610 Академические индукторы (8) 1Все о геологии824 2Общероссийский математический портал813 3Портал для аспирантов717 4Библиотека Академии Наук620 5Исторический факультет МГУ619 6Издательство СО РАН620

10 Вывод 2 : ценность коммуникаторов При добавлении коллекторов: мощность максимальной компоненты связности увеличивается до 214. При добавлении индукторов: мощность максимальной компоненты связности увеличивается до 190. При добавлении посредников: мощность максимальной компоненты связности увеличивается до 191. При добавлении всех трех подмножеств коммуникаторов: мощность максимальной компоненты связности увеличивается до 237. Во всех четырех случаях диаметр наибольшей компоненты связности становится равным 7.

11 11 Пример взвешенного веб-графа для 4 сайтов. Граф – сильно связный. Дуги имеют различные веса. d(i,t) – длина кратчайшего пути из вершины i в вершину t в графе G( T,Е), где i,t T. Критерий доступности сайта t на множестве T - средняя длина пути в заданную вершину t T из любой вершины i T, it, которая задается следующим образом: На примере для вершины 1: midd(1)=(1+3+1)/3=5/3. Далее будем использовать просто сумму, а не среднюю сумму, т.к. это не влияет на результат. Задача дележа затрат (1)

12 12 Вариант 2. сайтmidd(i)midd hub (i) выигрыш v(i) Задача дележа затрат (2)

13 13 Вариант 3. Кооперативные игры. Вектор Шепли принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме ее формирования. Задача дележа затрат (3)

14 14 На нашем примере сайтmidd(i) (i) выигрыш w(i) 154,670, ,837,17 392,676, ,838,17 выигрыш v(i) Вар 2 выигрыш w(i) Вар 3 14,55%0,331,50% 731,82%7,1732,59% 313,64%6,3328,77% 1150,00%8,1737,14% Задача дележа затрат (4)

15 Пусть n – количество участников, c i – значимость i-го участника, c i >0, i=1..n, m i – максимально возможное количество прямых ссылок от i-го на других участников, m i >0, i=1..n. Матрица ссылок X=(x ij ), i,j=1..n, где x ij =1, если существует ссылка от i-го участника к j-му, и x ij =0, если нет. Ограничения будут определены несколько ниже. F(X) функция, характеризующая некоторый интегральный показатель значимости всех участников веб-системы и зависящая от того, каким образом расставлены ссылки между ее участниками. Функция приращения значимости: – чем больше ссылок на ресурс, тем он становится «значимее», – чем больше значимость ресурса i, тем больше возрастает значимость ресурса j, если x ij =1, – чем больше исходящих ссылок от ресурса i, тем меньше приращение значимости каждого ресурса j, для которого x ij =1. Задача расстановки ссылок в локализованной системе веб-ресурсов (1)

16 Ограничения Целевая функция 1 Чем меньше, тем больше Целевая функция 2 Задача расстановки ссылок в локализованной системе веб-ресурсов (2)

17 Задача расстановки ссылок в локализованной системе веб-ресурсов (3) Апробация и модификация моделей на данных Яндекса ограничение заменено на строгое равенство, в качестве приняты значения тИЦ, отобрано 20 реальных сообществ, содержащих от 7 до 84 участников. По модели 1: Религия. Православие, Баннерная сеть Ket.Ru, Министерства РФ, Сайты КарНЦ РАН (0.905), Целлюлозно-Бумажная Баннерная Сеть По модели 2: Сайты КарНЦ РАН, Министерства РФ, Баннерная сеть Ket.Ru, Религия. Православие, Целлюлозно-Бумажная Баннерная Сеть., Задача расстановки ссылок в локализованной системе веб-ресурсов (3)

18 18