Кванты Скотт Паттерсон Brainiac Кен Дженнингс Moneyball

Р А С П У Т Ы В А Н И Е В С Е М И Р Н О Й П А У Т И Н Ы
199
1
1
X
Y
Z
3
6
1
2
Значения PageRank
после одного обновления
В последующих кругах правило обновления остается прежним. Если 
обозначить через x, y, z текущий счет страниц X, Y и Z, то в результате 
обновления получим такой счет:
х' = z
y' = ½ x
z' = ½ x + y,
где штрихи говорят о том, что произошло обновление. Подобные мно-
гократно повторяющиеся вычисления удобно выполнять в электронной 
таблице (или вручную, если сеть маленькая, как в нашем случае).
После десяти повторений обнаружим, что от обновления к обновле-
нию цифры практически не меняются. К этому моменту доля X составит 
40,6% от всего PageRank, доля Y — 19,8%, а Z — 39,6%. Эти значения 
подозрительно близки к числам 40, 20 и 40%, что говорит о том, что ал-
горитм должен к ним сходиться. 
Так и есть. Эти предельные значения алгоритм Google и определяет 
для сети как PageRank.

---

М Н О Г О Л И К И Е Д А Н Н Ы Е
200
1
X
Y
Z
5
2
5
2
5
Предельные значения PageRank
Вывод для данной маленькой сети такой: страницы X и Z одинаково 
важны, несмотря на то что у Z в два раза больше входящих ссылок. Это 
и понятно: страница X равна Z по значимости, поскольку она получает 
от нее полное одобрение, однако взамен дает ей лишь половину своего 
одобрения. Вторая половина отправляется Y. Это также объясняет, по-
чему Y достается только половина от долей X и Z.
Интересно, что эти значения можно получить, не прибегая к много-
кратным итерациям. Надо просто подумать над условиями, определяю-
щими стационарное состояние. Если после очередного обновления ни-
чего не меняется, то x' = x, y' = y и z' = z. Поэтому, заменив переменные 
со штрихом в уравнениях обновлений на их эквиваленты без штрихов, 
получим систему уравнений
х = z
y = ½ x
z = ½ x + y,
при решении которой x = 2y = z. Поскольку сумма значений x, y и z 
должна равняться 1, отсюда следует, что x = 2/5, y = 1/5 и z = 2/5, что 
соответствует ранее найденным значениям.

---