PageRank 初探
算法简介
Google的经典算法--PageRank
。点击了解更多关于PageRank。
PageRank的核心目标在于计算网页的重要性,从而提供一个自上向下的排名。而TextRank主要为文章中的单元的重要性(或关键词)。
计算方法
我们煮一个简单的栗子。(如果你想看的更多请移步至PageRank算法简介及Map-Reduce实现,本例为其例子的简化版)
首先模拟一个PageRank的场景,如图(在本例中,假设互联网中只存在4个页面ABCD。且满足:1. 图是强连通的,即从任意网页可以到达其他任意网页;2.禁止出现网页不存在指向其他网页的链接,但存在指向自己的链接。):
当某位用户在访问A页面时,他有1/3的概率去访问BCD页面中一(在AB之间的直线A→B表示A可以访问B,BA中的B→A表示B可以访问A。相对于A来说,前者为出链,后者为入链)。
同理,在D页面时,有1/2的概率访问BC,依次类推可以画出一个表格:
---- | A | B | C | D |
---|---|---|---|---|
A | 0 | 1/2 | 1 | 0 |
B | 1/3 | 0 | 0 | 1/2 |
C | 1/3 | 0 | 0 | 1/2 |
D | 1/3 | 1/2 | 0 | 0 |
使用矩阵表示为:
在第一次访问时,由于现在的模型符合古典概型,即访问的页面是等可能的,即访问每个页面的可能性都为1/4,Vn表示第n次访问的概率
在未来的多次访问中,我们用相同的方法计算,直到矩阵收敛(Vn=MV(n-1)):
即此时的矩阵为页面的PageRank。