《海量数据挖掘-王永利》Pagerank 算法及其实现.pdfVIP

Pagerank 算法及其实现 黄东东 314106002383 1、基本思想 Pagerank 算法的核心思想主要是： 1. 如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是该网页 的pagerank 值比较高； 2. 如果一个pagerank 值很高的网页链接到一个其他的网页，那么被链接到的网页的 pagerank 值会相应地因此而提高。 2、数学模型 假设n 是网络中所有可访问网页的数目。根据以上思想可以得到一个很直观的公式： R (i ) ? R (j ) j ?B (i ) 其中R (x )表示x 的pagerank，B (x ) 表示所有指向x 的网页。 该公式的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。该公 式很好的表达出了pagerank 的核心思想。但是该公式很有一个很明显的缺陷：无论J 有 多少个超链接，只要J 指向I，I 都将得到与J 一样的重要性。当J 有多个超链接时，这 个思想就会造成不合理的情况。例如：一个新开的网站N 只有两个指向它的超链接，一 个来自著名并且历史悠久的门户网站 F，另一个来自不为人知的网站 U。根据该公式， 就会得到N 比F 更优质的结论。这个结论显然不符合人们的常识。 弥补这个缺陷的一个简单方法是当J 有多个超链接（假设个数为 N），每个链接得到的 重要性为R(j)/N。于是公式(1)就变成： R (j ) R (i ) ? j B (i ) N (j ) 3、简单的模型示例及实现 互联网中的网页可以看出是一个有向图，其中网页是结点，如果网页 A 有链接到 网页B，则 存在一条有向边A ?B ,下面是一个简单的示例： 这个例子中只有四个网页，如果当前在 A 网页，那么悠闲的上网者将会各以 1/3 的概率跳转到B、C、D，这里的3 表示A 有3 条出链，如果一个网页有k 条出链，那么 跳转任意一条出链上的概率是1/k，同理D 到B、C 的概率各为1/2，而B 到C 的概率为 0 。一般用转移矩阵表示上网者的跳转概率，如果用n 表示网页的数目，则转移矩阵M 是n*n 的方阵； 网页j 有 k 个出链，那么对每一个出链指向的网页i，有M[i][j]=1/k， 而其他网页的M[i][j]=0;上面示例图对应的转移矩阵如下： ? 0 1/2 1 0 ? ? ? M ?1/3 0 0 1/2? ?1/3 0 0 1/2? ? ? ?1/3 1/2 0 0 ? 初始假设上网者在每一个网页的概率相等，即 1/n，于是初始的概率分布就是一个所有 V V 值都为1/n 的n 维列向量 ，用 去右乘转移矩阵M，就得到了第一步之后上网者的 0 0 V 概率分布向量M , （nXn）*(nX1)依然得到一个nX1 的矩阵。下面是 的计算过程：