跳到内容

Page Rank 算法

来源：R/centrality.R
page_rank.Rd

计算指定顶点的 Google PageRank 值。

用法

page_rank(
  graph,
  algo = c("prpack", "arpack"),
  vids = V(graph),
  directed = TRUE,
  damping = 0.85,
  personalized = NULL,
  weights = NULL,
  options = NULL
)

参数

graph

图对象。

algo

字符标量，用于指定用于执行计算的实现方式。 默认值为 "prpack"，它使用 PRPACK 库（https://github.com/dgleich/prpack）通过求解一组线性方程来计算 PageRank 分数。 这是 igraph 0.7 版本中的一个新实现，也是建议的实现方式，因为它是最稳定的，并且对于除小型图以外的所有图来说都是最快的。 "arpack" 使用 ARPACK 库，这是从 igraph 0.5 版本到 0.7 版本的默认实现。 它通过求解特征值问题来计算 PageRank 分数。

vids

感兴趣的顶点。

directed

逻辑值，如果为 true，则对于有向图，将考虑有向路径。 对于无向图，此参数将被忽略。

damping

阻尼因子（原始论文中的“d”）。

personalized

可选向量，用于提供概率分布以计算个性化的 PageRank。 对于个性化的 PageRank，当放弃随机游走时，跳转到节点的概率不是均匀的，而是由该向量给出。 该向量应包含每个顶点的条目，并且将被重新缩放以使其总和为 1。

weights

数值向量或 NULL。 此参数可用于为计算顶点的加权 PageRank 提供边权重。 如果此参数为 NULL 且图具有 weight 边属性，则将使用该属性。 如果 weights 是数值向量，则即使图具有 weights 边属性，也会使用它。 如果此参数为 NA，则不使用任何边权重（即使图具有 weight 边属性）。 此函数将边权重解释为连接强度。 在随机冲浪者模型中，具有较大权重的边更有可能被冲浪者选择。

options

一个命名列表，用于覆盖一些 ARPACK 选项。 有关详细信息，请参见 arpack()。 如果使用 PRPACK 实现，则忽略此参数。

值

一个包含以下条目的命名列表

vector

一个数值向量，包含 PageRank 分数。

value

使用 ARPACK 方法时，此处返回与具有 PageRank 分数的特征向量相对应的特征值。 预计它正好为 1，并且可以用来检查 ARPACK 是否已成功收敛到预期的特征向量。 使用 PRPACK 方法时，它始终设置为 1.0。

options

有关底层 ARPACK 计算的一些信息。 有关详细信息，请参见 arpack()。 如果未使用 ARPACK 实现，则此条目为 NULL。

详细信息

有关 PageRank 算法的说明，请参见以下网页：http://infolab.stanford.edu/~backrub/google.html，或以下参考资料

Sergey Brin 和 Larry Page：大规模超文本 Web 搜索引擎的剖析。 第七届万维网国际会议论文集，澳大利亚布里斯班，1998 年 4 月。

page_rank() 函数可以使用 PRPACK 库或 ARPACK（请参见 arpack()）来执行计算。

请注意，给定顶点的 PageRank 取决于所有其他顶点的 PageRank，因此即使您只想计算某些顶点的 PageRank，也必须计算所有顶点的 PageRank。 仅请求某些顶点的 PageRank 不会导致任何性能提升。

参考文献

Sergey Brin 和 Larry Page：大规模超文本 Web 搜索引擎的剖析。 第七届万维网国际会议论文集，澳大利亚布里斯班，1998 年 4 月。

参见

其他中心性分数：closeness(), betweenness(), degree()

中心性度量 alpha_centrality(), authority_score(), betweenness(), closeness(), diversity(), eigen_centrality(), harmonic_centrality(), hits_scores(), power_centrality(), spectrum(), strength(), subgraph_centrality()

作者

Tamas Nepusz ntamas@gmail.com 和 Gabor Csardi csardi.gabor@gmail.com

personalized_pagerank().

示例


g <- sample_gnp(20, 5 / 20, directed = TRUE)
page_rank(g)$vector
#>  [1] 0.07461604 0.02846375 0.05027611 0.03185239 0.04070845 0.08028440
#>  [7] 0.05465747 0.03305534 0.05659133 0.02317787 0.05008794 0.03142401
#> [13] 0.07471363 0.09566876 0.01078353 0.07489727 0.01963811 0.03487668
#> [19] 0.07330366 0.06092326

g2 <- make_star(10)
page_rank(g2)$vector
#>  [1] 0.49008499 0.05665722 0.05665722 0.05665722 0.05665722 0.05665722
#>  [7] 0.05665722 0.05665722 0.05665722 0.05665722

# Personalized PageRank
g3 <- make_ring(10)
page_rank(g3)$vector
#>  [1] 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
reset <- seq(vcount(g3))
page_rank(g3, personalized = reset)$vector
#>  [1] 0.08305627 0.07206568 0.07367581 0.08203783 0.09368592 0.10631408
#>  [7] 0.11796217 0.12632419 0.12793432 0.11694373