4846
правок
Алгоритм PageRank: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
'''Определение на основе линейной алгебры''' | '''Определение на основе линейной алгебры''' | ||
Пусть n – общее количество веб-страниц. Вектор PageRank – это n-мерный вектор с одной размерностью для каждой веб-страницы. Пусть d – небольшая константа, например 1/8. Обозначим за deg(p) количество гиперссылок в основном тексте страницы p, а за PR(p) – значение PageRank для страницы p. Предположим сначала, что каждая страница содержит хотя бы одну гиперссылку. В такой коллекции веб-страниц вектор PageRank вычисляется путем решения системы линейных уравнений, содержащей для каждой страницы p уравнение | Пусть n – общее количество веб-страниц. Вектор PageRank – это n-мерный вектор с одной размерностью для каждой веб-страницы. Пусть <math>d</math> – небольшая константа, например 1/8. Обозначим за <math>deg(p)</math> количество гиперссылок в основном тексте страницы <math>p</math>, а за <math>PR(p)</math> – значение PageRank для страницы <math>p</math>. Предположим сначала, что каждая страница содержит хотя бы одну гиперссылку. В такой коллекции веб-страниц вектор PageRank вычисляется путем решения системы линейных уравнений, содержащей для каждой страницы <math>p</math> уравнение | ||
PR(q)/deg(q) | <math>PR(p) = d/n + (1 - d) * \sum_{q \; has \; hyperlink \; to \; p} PR(q)/deg(q).</math> | ||
("q has hyperlink to p" = "q содержит гиперссылку на p") | |||
В матричной нотации вектор PageRank представляет собой собственный вектор с 1-нормой матрицы <math>A</math> с <math>d/n+ (1 - d)/deg(q)</math> для записи <math>A_{qp}</math>, если <math>q</math> содержит гиперссылку на <math>p</math>, и <math>d/n</math> в противном случае. | |||
Если в этой линейной системе разрешить веб-страницы без гиперссылок, то они могут стать «стоками PageRank», то есть они будут «получать» PageRank от страниц, указывающих на них, но не будут «отдавать» свой PageRank, что потенциально может привести к «необычно высокому» значению PageRank для таких веб-страниц. Брин и Пейдж предложили два способа борьбы с веб-страницами без исходящих ссылок: либо рекурсивно удалять их до тех пор, пока в совокупности не останется ни одной такой веб-страницы, либо добавлять гиперссылку с каждой такой страницы на ''все'' остальные страницы. | |||
Если в этой линейной системе разрешить веб-страницы без гиперссылок, то они могут стать «стоками PageRank», то есть они будут «получать» PageRank от страниц, указывающих на них, но не будут «отдавать» свой PageRank, что потенциально может привести к «необычно высокому» значению PageRank для таких веб-страниц. Брин и Пейдж предложили два способа борьбы с веб-страницами без | |||
'''Модель случайного серфера''' | '''Модель случайного серфера''' | ||
Пусть веб-граф G = (V | Пусть ''веб-граф'' <math>G = (V, E)</math> – это ориентированный граф, в котором каждая вершина соответствует веб-странице, а каждая гиперссылка – ориентированному ребру от ссылающейся вершины к вершине, на которую производится ссылка. PageRank также можно интерпретировать как случайное блуждание по веб-графу следующего вида. Случайное блуждание начинается со случайной вершины в графе. Предположим, что на шаге <math>k</math> оно посещает страницу <math>q</math>. Затем оно подбрасывает монету и с вероятностью <math>d</math>, или если у <math>q</math> нет исходящих ссылок, выбирает случайную вершину из <math>V</math> и посещает его на шаге <math>k + 1</math>. В противном случае он выбирает случайное исходящее ребро текущей вершины и посещает его оконечную вершину на шаге <math>k + 1</math>. (Обратите внимание, что это соответствует добавлению ориентированного ребра от каждой страницы, не имеющей гиперссылок, к каждой вершине в графе). При определенных условиях (которые не обязательно выполняются в Интернете) стационарное распределение этого случайного блуждания соответствует вектору PageRank. Подробнее об этом см. в [1, 4]. | ||
Брин и Пейдж также предложили вычислять вектор PageRank приблизительно, используя степенной метод, то есть задавая все начальные значения равными 1/n, а затем многократно используя вектор PageRank предыдущей итерации для вычисления вектора PageRank текущей итерации с помощью приведенных выше линейных уравнений. После сотни итераций почти никакие значения не меняются, и вычисления прекращаются. | Брин и Пейдж также предложили вычислять вектор PageRank приблизительно, используя степенной метод, то есть задавая все начальные значения равными <math>1/n</math>, а затем многократно используя вектор PageRank предыдущей итерации для вычисления вектора PageRank текущей итерации с помощью приведенных выше линейных уравнений. После сотни итераций почти никакие значения не меняются, и вычисления прекращаются. | ||
== Применение == | == Применение == | ||
