База данных внешних гиперссылок Гостевой вход: guest/guest. - презентация

1 База данных внешних гиперссылок Гостевой вход: guest/guest

2 Присутствие целевых множеств в Вебе может быть значительно улучшено как за счет увеличения количества взаимных гиперссылок, так и за счет увеличения их связности с помощью сайтов- коммуникаторов. Далее рассматриваются три задачи: –задача расстановки гиперссылок в множестве сайтов, повышающая их присутствие в Вебе с точки зрения поисковых машин, –задача дележа затрат на создание веб-коммуникатора, –задача об оценке полезности участия в множестве сайтов, ссылающихся на один и тот же сайт-коммуникатор и имеющих обратные гиперссылки с него. Задачи рационального поведения в Вебе 2 из 10

3 n – количество сайтов-участников, c i – значимость i-го сайта, c i >0, i=1..n, X=(x ij ), i,j=1..n, x ij =1, если существует ссылка от i-го сайта на j-й, x ij =0, если нет. Задача расстановки гиперссылок 3 из 10 0< 0, i=1..n. Значимость (Google, Яндекс): – чем больше ссылок на ресурс, тем он «значимее»,

4 (1) (2) (3) (4) (5) 4 из 10 Исследование (1-5): Задача 1: (1) Задача 2: Замена приводит к задаче линейного программирования для её решения верно Приближенный алгоритм: в каждой строке i матрицы значение 1 получают те, для которых имеет максимальное значение в этой строке. Исследование (1, 2-5): Строится функция Лагранжа Находятся условия Приближенный алгоритм: в каждой строке i выбирается элемент t c наименьшим и новым значением, наиболее близким к среднему по столбцу.

5 Апробация на данных Яндекса: 20 реальных сообществ, содержащих от 7 до 84 участников, в качестве приняты значения тИЦ, =0,85 ( damping-factor - Brin, Page ). Сообщества с согласованным поведением: Сайты КарНЦ РАН, Министерства РФ, Баннерная сеть Ket.Ru, Религия. Православие, Целлюлозно-Бумажная Баннерная Сеть. 5 из 10

6 Задача о дележе затрат 6 из Пример: h Тогда, midd h (i) 2. Веб-граф G ( T,E,W ) – сильно связный со взвешенными дугами, веса w i1. d(i,t) – длина кратчайшего пути из i в t, Критерий доступности сайта t на целевом множестве T : Владельцы сайтов – игроки договорились создать веб-коммуникатор h, с которого обязательно будут сделаны гиперссылки c весом 1 на любой сайт из T и с каждого сайта из T будет сделана гиперссылка на h, имеющая вес 1.

7 Коалиция S – (под)множество сайтов из T, участвующих в создании h, причем h будет ссылаться только на участников коалиции, и только они будут ссылаться на коммуникатор. Характеристическая функция для i-го участника v(i) = midd(i)–midd h S (i) рассчитывается с учетом того, того что коммуникатор создается только для членов коалиции S, midd h S (i) - средняя длина пути в вершину i из всех других вершин коалиции S, кроме h и её самой. Решение основано на разделении платы пропорционально компонентам вектора Шепли, строящемуся с учетом среднего вклада каждого участника в выигрыш гранд-коалиции, z 1, z 2, …, z n делится пропорционально величинам 7 из 10 Z – стоимость сайта h, z i - взнос каждого игрока,. Вопрос: каковы должны быть значения z 1, z 2, …, z n, справедливые (в некотором смысле) для каждого игрока-владельца сайта целевого множества?

8 Взвешенный веб-граф КарНЦ РАН Кооперативный: Z={0.000, 0.105, 0.169, 0.129, 0.105, 0.153, 0.169, 0.169} Одинаковый: Z={0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125} 8 из 10

9 Задача об участии в сообществе динамического каталога (СДК) 9 из 10 0 (головной сайт) Каталог ссылок 1 2 k k+1 n 1 n i Пользователи Веба p i вероятность попадания пользователя на i-й сайт СДК, p i 0 вероятность перехода с i-го рядового сайта на головной сайт (вероятность того, что пользователь, попав на i-й рядовой сайт, останется на нем, равна 1-p i 0 ); 1-p i 0 pipi pi0pi0 p0p0 q 0 вероятность того, что пользователь, попав на головной сайт, останется на нем; q0q0 qjqj q j cat – вероятность перехода с j-й позиции каталога, q 1 cat q 2 cat … q k cat, q k+1 cat = q k+2 cat =… q n cat =0. Рядовые сайты Неизвестны: q j - вероятность перехода на любой рядовой сайт с j-й позиции каталога. Известны q j cat

10 Для нахождения ij построена система n 2 +2n уравнений 10 из 10 Для случая двух рядовых сайтов достаточное условие выигрыша обоих участников Обозначим ij - вероятность нахождения ссылки i-го рядового сайта на j-й позиции в каталоге, Тогда Доход от участия в СДК для i-го сайта:

11 Некоторые результаты имитационного моделирования: 11 из 10 Тестовый пример «Кольцо сайтов» LawDir