PageRank 初探
in 自然语言处理 with 0 comment

PageRank 初探

in 自然语言处理 with 0 comment

算法简介

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,依次类推可以画出一个表格:

----ABCD
A01/210
B1/3001/2
C1/3001/2
D1/31/200

使用矩阵表示为:

在第一次访问时,由于现在的模型符合古典概型,即访问的页面是等可能的,即访问每个页面的可能性都为1/4,Vn表示第n次访问的概率

在未来的多次访问中,我们用相同的方法计算,直到矩阵收敛(Vn=MV(n-1)):

即此时的矩阵为页面的PageRank。

Comments are closed.