реализация алгоритма ранжирования страницы в R

Я пытаюсь реализовать алгоритм ранжирования страницы в R, используя следующие шаги:

  1. Загрузите образец графика, такой как этот:

    0 1
0 2
0 3
1 2
1 5
2 0
2 4
3 1
3 0
3 4
4 1
4 5
5 2
5 3

  2. Создайте матрицу смежности из этого графика

  3. Создайте цепь Маркова (матрицу перехода)
  4. Найдите стационарное распределение и нормализуйте его

Ниже приведен код, реализующий все эти шаги:

g = read.graph(x)

a = get.adjacency(g)

markov = a / rowSums(a)

e = eigen(t(markov))

v <- e$vec[,1]

normalized <- v / sum(v)

когда я сравниваю вектор из нормализованного объекта с вектором, созданным page.rank(g) для этого конкретного графика, они почти одинаковы с небольшими отличиями. Однако, когда я пробую это на этом графике:

    0 1
    0 2
    0 3
    1 2
    1 5
    2 0
    2 4
    3 1
    3 0
    3 4
    4 1
    4 5
    5 2
    5 3
    6 1
    6 2
    6 5
    6 0
    7 3
    7 4
    7 6
    7 7
    7 1
    8 2
    8 5
    9 8 
    9 7
    9 1 
    9 5
    10 2 
    10 3
    10 9

Разница огромная!

У кого-нибудь есть объяснение этому или альтернативная реализация этого алгоритма в R.


r igraph pagerank
person bytebiscuit    schedule 26.11.2013    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Причина в параметре демпфирования.

Ваш код вообще не использует демпфирование. бета=0. По умолчанию page.rank использует бета=0,85.

Если вы используете следующий код, который использует демпфирование (бета-переменная), вы получите те же результаты, что и page.rank. Или вы можете изменить свой код, например, M=beta*M+(1-beta)*U и применить метод собственных векторов. (Если какой-то столбец равен 0 вектору, вам нужно изменить свою матрицу с 1/n в этом столбце, прежде чем добавлять эффект демпфирования).

Я использовал ваш первый пример, чтобы показать три разных способа получить одинаковые точные результаты. Без мелких отличий.

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

Вот код:

g <- graph(c(
  1, 2, 1, 3, 1, 4, 
  2, 3, 2, 6, 3, 1, 
  3, 5, 4, 2, 4, 1, 
  4, 5, 5, 2, 5, 6, 
  6, 3, 6, 4), 
            directed=TRUE)

M = get.adjacency(g, sparse = FALSE)
M = t(M / rowSums(M))
n = nrow(M)

U = matrix(data=rep(1/n, n^2), nrow=n, ncol=n)
beta=0.85
A = beta*M+(1-beta)*U
e = eigen(A)
v <- e$vec[,1]
v <- as.numeric(v) / sum(as.numeric(v))
v

page.rank(g)$vector

library(expm)
n = nrow(M)
U = matrix(data=rep(1/n, n^2), nrow=n, ncol=n)
beta=0.85
A = beta*M+(1-beta)*U
r = matrix(data=rep(1/n, n), nrow=n, ncol=1)
t(A%^%100 %*% r)
person Roc    schedule 09.10.2014
comment
Я думаю, что он использует демпфирование = 1, а не демпфирование = 0. - person vonjd; 21.05.2018

arrow_upward
0
arrow_downward

@Roc неверно утверждает, что вы используете коэффициент демпфирования 0, верно и обратное: вы используете коэффициент демпфирования 1.

При запуске следующего кода вы получаете одинаковые результаты для трех разных методов (igraph, возведение матрицы в n't power и собственный вектор):

library(igraph)
library(expm)

set.seed(1415)
n <- 10
g <- sample_gnp(n, p = 1/4, directed = TRUE) # create random graph
df <- data.frame(pr = page_rank(g, damping = 1)$vector)

r <- c(1, rep(0, (n-1)))
adj_m <- t(as_adjacency_matrix(g, sparse = FALSE))
adj_m_mod <- prop.table(adj_m, 2)

lr <- eigen(adj_m_mod)$vectors[ , 1]
lr <- Re(lr/sum(lr))

matrix(lr, ncol = 1)
##             [,1]
##  [1,] 0.27663551
##  [2,] 0.02429907
##  [3,] 0.08878505
##  [4,] 0.06915888
##  [5,] 0.14579439
##  [6,] 0.10654206
##  [7,] 0.06915888
##  [8,] 0.07289720
##  [9,] 0.05327103
## [10,] 0.09345794
adj_m_mod %^% 100 %*% r
##             [,1]
##  [1,] 0.27663574
##  [2,] 0.02429905
##  [3,] 0.08878509
##  [4,] 0.06915881
##  [5,] 0.14579434
##  [6,] 0.10654199
##  [7,] 0.06915881
##  [8,] 0.07289723
##  [9,] 0.05327107
## [10,] 0.09345787
df
##            pr
## 1  0.27663551
## 2  0.02429907
## 3  0.08878505
## 4  0.06915888
## 5  0.14579439
## 6  0.10654206
## 7  0.06915888
## 8  0.07289720
## 9  0.05327103
## 10 0.09345794

Еще один момент: вы всегда должны быть осторожны с тем, как определяется матрица смежности, т.е. находятся ли входящие и исходящие ссылки в строках или столбцах. Чтобы преобразовать одну форму в другую, используйте функцию транспонирования t().

ИЗМЕНИТЬ
Я опубликовал запись в блоге об алгоритме рейтинга страниц в R:
http://blog.ephorie.de/googles-eigenvector-or-how-a-random-surfer-находит-самые-релевантные-веб-страницы

person vonjd    schedule 24.05.2018