学习笔记——PageRank

自从前两天在不周山的博客上看到一篇用PageRank算法来给R包计算权重的文章后，突然对PageRank产生了兴趣。于是相当虔诚的拜读了Lawrence Page在1998年发表的文章"The PageRank Citation Ranking: Bringing Order to the Web"。

Naive Idea

PageRank的核心思想说起来非常简单。一个网页通常既有正向链接（链接到别的网页）又有反向链接（从别的网页链接过来），如果一个网页拥有很多的反向链接，那么这个网页通常比那些只拥有少量反向链接的网页更“重要”。在此基础上更进一步，如果一个网页的反向链接网页都比较“重要”，那么这个网页比那些反向链接网页不太“重要”的网页更“重要”一些（绕口令@_@）。这就是PageRank的基本思想，一个网页的权重取决于其反向链接网页权重的线性组合。

Definition

考虑最简单的情况，假设u为一个网页。Fu表示u的正向链接网页的集合，Bu表示u的反向链接网页的集合。Nu表示u的正向链接的数量，即Fu中元素的个数。则网页u的权重Ru可以表示为
Ru = c * sum(Rv/Nv)，v取遍B_u中的所有元素
其中，c为归一化因子，使得所有网页的总权重和为1。

通过矩阵，可以更简洁的来表示上面的意思。
令A为N*N方阵，N为网页的总数。若存在链接v到u，则A[u,v]=1/N_v，否则A[u,v]=0。设向量R为所有网页的权重，则R满足R = c * A %*% R。很眼熟的等式吧？没错！把c移到左边(1/c) * R = A %*% R，R就是以1/c为特征值的特征向量，可以取特征值最大的特征向量作为网页权重的一种近似。

Example

仅从最基本的理论角度，很容易在R中求得网页的PageRank。

library(Matrix)
links <- list(c(2,3,4,5,7),c(1),c(1,2),c(2,3,5),c(1,3,4,6),c(1,5),c(5))  ## 网页链接关系

toMatrix.links <- function(links) {
    nodes <- 1:length(links)
    res <- Matrix(0,nrow=length(nodes),ncol=length(nodes),sparse=TRUE)
    idx <- unlist(links)+rep((1:length(nodes))-1,times=sapply(links,length))*length(nodes)
    res[idx] <- 1
    res <- t(t(res)/colSums(res))
    return(res)
}

pageRank.naive <- function(links) {
    trans.Matrix <- toMatrix.connection(links)
    res <- eigen(trans.Matrix)
    return(list(val=res$values[1],vec=res$vectors[,1]))
}

pageRank.naive(links)

Conclusion

实际的PageRank算法当然要更复杂，这里只是简单介绍了一下最基本的原理。今天就写到这里，下次再写～