страница реализации ранга алго в R

Question

Я пытаюсь реализовать алгоритм ранга страницы в 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 (г) для данного конкретного графа они в значительной степени совпадают с незначительными различиями. Однако, когда я пробую это на этом графике:

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.

Answer 1

Причиной является параметр затухания.

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

Если вы используете следующий код, который использует демпфирование (бета-переменная), вы получите те же результаты, что и page.rank. Или вы можете изменить свой код с помощью чего-то вроде M = beta * M + (1-бета) * 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)