页面排名algo在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(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中对此算法的替代实现.

Answer 1

原因是阻尼参数.

您的代码根本没有使用阻尼.的β= 0.page.rank默认使用beta = 0.85.

如果您使用以下代码(使用阻尼(beta变量)),您将获得与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)