О методике рассчета PR по Brin&Page

Не совсем понятки исходные посылки - нет формулы, хотя бы в матричном виде, а то неясно, если мы матрицу А умножаем на вектор р, то куда подключается d?

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

Но в целом утверждение небезинтересное, нельзя ли даль ссылку на оригинал?

usual we got 0.1<d<0.15.

У тебя d=1-d (смотря что брать за единицу ), т.е. 0.85<d<0.9

И выбирается оно именно из соображений сходимости процесса...

2paul-

Эта ссылка уже была http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm с алгоритмом расчета PR.

______

We assume page A has pages T1...Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. !2AIK- We usually set d to 0.85. There are more details about d in the next section. Also C(A) is defined as the number of links going out of page A. The PageRank of a page A is given as follows:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.

________

Конечно, вектор умножается на соб.зн-е, но оно=1 либо нормируется к 1 (1, за счет того, что сумма всех PR / к-во страниц = 1 по определению.). Векторной формулы в явном виде не давали, но если вектор=вероятности по сайтам i, а матрица=к-во ссылок с сайта i на j, это просто формализация алгоритма расчета.

2Aik-

Это как, для каждого сайта выбирать d для сходимости процесса? d, насколько я понял, вероятность того, что юзер закончил на этом сайте (или 1 минус это), и для каждого сайта своя, выбирается априори (м.б, из свойств текста). d фиттить для каждого сайта - немаленькое число свободных переменных.

[This message has been edited by euhenio (edited 26-10-2001).]

Цитата оттуда же-

_________

. And, the d damping factor is the probability at each page the "random surfer" will get bored and request another random page. One important variation is to only add the damping factor d to a single page, or a group of pages. This allows for personalization and can make it nearly impossible to deliberately mislead the system in order to get a higher ranking

_________

1) сумма всех PR(A) должна быть равна единице

(вероятность того, что я попаду хотя бы на одну страницу равна 1. Вероятность, того, что я попаду на страницу A есть PR(A))

2) коэффициент затухания выбирается из соображений сходимости процесса умножения матрицы на вектор, т.е. коэффициент один на всех, а не для каждого свой.

PR не может быть делен на число страниц, тк там есть-

PR=(1-d)+d*(Sum), т.е. при каждой итерации PR приближается к 1, dumping и сделан, видимо, для этого. Не сумма PR=1, а =числу страниц, при этом в среднем получится PR=1 по Инету. Это очевидно. Если проводить итерацию N раз, сдвиг к 1 будет слишком велик (от числа, близкого к PR~0=1/N, где N=сайтов в Инете).

Собственно, это и неважно, как считать.

Кроме того, как я понял из описания, d все-таки разные. Если даже и нет, это было бы хорошим улучшением.

Самое главное, неясно, достаточно ли d=0.85 для пресловутой сходимости.... Кто-нибудь знает, как бы это можно посчитать?

Э... либо ты невнимательно читал про PageRank, либо не очень хорошо знаком с теорией вероятности.

Представь, что ты знаешь только две страницы в интернете А и Б. Какова вероятность того, что ты запустив браузер пойдёшь на страницу А? Правильно 1/2. Точно такая же вероятность, что ты пойдёшь на страницу Б. Сумма этих вероятностей равна единице (раз уж ты вылез в Интернет, то на одну из этих страниц ты точно зайдёшь ). И PageRank у каждой из страниц будет равен 1\2, не зависимо от того ссылаются они друг на друга или нет. d вводится потому, что если ты знаешь, скажем два набора не связанных друг с другом страниц, ты рано или поздно перейдёшь от одного набора к другому не по ссылке, а просто наберёшь в браузере URL ручками. Если бы этот коэффициент не вводили, то пришлось бы допустить, что ты бродишь только по взаимосвязанным страницам, что в общем случае не верно.

Теперь если просто считать по формуле (знаем те же 2 страницы и они друг с другом не связаны) PR(A)=PR(Б)=0.15 без нормировки.

По твоему утверждению :

(0.15+0.15)/2 = 0.15 (!=1)

Но, если ты проведёшь нормировку, так что

PR(A) + PR(Б) =1 ты получишь

PR(A)=PR(Б)=0.5, что соответсвует "действительности".

Надеюсь к случаю из N страниц сможешь перейти самостоятельно

Я предполагаю, что слова "сумма всех PR=1" говорятся только для придания формального смысла PR (=вероятность), и то при конечном выводе, а не во время итераций.

Посуди сам- пусть есть 1000000 страниц, тогда:

1) Начнем с ПР=1, сделаем итерацию, получим ПР ПОРЯДКА 1. Разделим сумму ПР на 1000000, получим ПР порядка 0.000001

2 итерация) Начнем с ПР=0.000001, возьмем сумму по ссылкам, получим тот же порядок

+

Затем учтем d=0.85, получим

ПР~0.15+0.85*(~0.000001)~0.15

Разделим сумму ПР на 1000000, получим ПР порядка 0.00000015

3 итерация) Начнем с ПР=0.00000015, возьмем сумму по ссылкам, получим тот же порядок

+

Затем учтем d=0.85, получим

ПР~0.15+0.85*(~0.00000015)~0.15

Разделим сумму ПР на 1000000, получим ПР порядка 0.00000015-------

при этом ПР определяется РЕАЛЬНО ТОЛЬКО числом 0.15

И так далее.

Математически d нивелирует разницу сайтов в ПР, СДВИГАЯ ПР К 1 !!! Если проводить расчеты так, как ты говоришь, это есть сдвигание нулей к 1, тогда у всех сайтов ПР практически одинаков, на уровне (1-d)/N сайтов.

Мне кажется, ты не пробовал сам это считать. Да, в статье на сайте используется тот же метод. Привести это все к вероятности легко можно после того, как сходимость достигнута. А так сходимости у тебя не будет- то ПР ~0.15, то ~0.00000015

Увы, но похоже, действительно расходимости нет... На матрицу и вектор вероятности PR(i) наложены ограничения (элемент 1>P(i)>0).

А так хотелось.