PageRank算法

一、算法原理：

1、如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
2、如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页PageRank值也会相应提高。
例子：
如果一个网页有k条出 链，那么跳转任意一个出链上的概率是1/k ；如果用n表示网 页的数目，则转移矩阵M是一个n*n的方阵；如果网页j有k个出链，那么对每一个出链指向的网页i，有M[i][j]=1/k，而其他网页的M[i] [j]=0

假设上网者在每一个网页的概率都是相等的，即1/n，于是初试的概率分布就是一个所有值都为1/n的n维列向量V0，用V0去右乘转移矩阵M，就得到了第一步之后上网者的概率分布向量MV0,（nXn）*(nX1)依然得到一个nX1的矩阵

矩阵M中M[i][j]不为0表示用一个链接从j指向i，M的第一行乘以V0，表示累加所有网页到网页A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最终V会收敛，即Vn=MV(n-1)，上面的图示例，不断的迭代，最终V=[3/9,2/9,2/9,2/9]

二、注意事项：

如果有些网页不指向其他网页（可能是垃圾网页），如果按照上面的计算，上网者到达这样的网页后便走投无路、四顾茫然，导致前面累计得到的转移概率被清零，这样计算下去得到的概率分布向量所有元素几乎为0

三、算法改进

解决终止点问题和陷阱问题
地址栏输入而跳转到各个网页的概率是1/n；
上网者每一步查看当前网页的概率为a，那么从浏览器地址栏跳转的概率为(1-a)

[注]采用矩阵相乘， 不断迭代，直到迭代前后概率分布向量的值变化不大，一般迭代到30次以上就收敛了,取e为所有分量都为1/n的列向量。真的web结构的转移矩阵非常大，目前的网页数量已经超过100亿， 转移矩阵是100亿*100亿的矩阵，直接按矩阵乘法的计算方法不可行，需要借助Map-Reduce的计算方式来解决。

四、算法总结：

PageRank算法的缺点
这是一个天才的算法， 原理简单但效果惊人。 然而， PageRank算法还是有一些弊端。
第一， 没有区分站内导航链接。 很多网站的首页都有很多对站内其他页面的链接， 称为站内导航链接。 这些链接与不同网站之间的链接相比，肯定是后者更能体现PageRank值的传递关系。
第二， 没有过滤广告链接和功能链接（例如常见的“分享到微博”）。这些链接通常没有什么实际价值， 前者链接到广告页面， 后者常常链接到某个社交网站首页。
第三， 对新网页不友好。一个新网页的一般入链相对较少，即使它的内容的质量很高，要成为一个高PR值的页面仍需要很长时间的推广。