Google网页排序算法中PageRank值(5)

社会环境下网页重要性的研究

PRin(i)=

?j(Kijn ×?Zijn×PRin(i-1)×Kijn)

nPRi=?PRin

n

Ci=

n1 //设置归一化常数,规范因子的计算，以保证计算结果的正确性

?PRinPRin= Ci PRin

(i)

(i)

//进行规范化得出的结果

i=i+1

}

随着循环次数的增加，计算结果越来越收敛，越来越接近真实的PR值，只要循环次数足够多可以得到任何精度的网页PR值。

3.2.3访问者PR值算法的简单模型

据统计，Web已经拥有100亿左右的静态网页和550亿左右的动态网页，网民数量仅中国就有4.16亿，因此，PageRank要处理的矩阵是“世界上最大的矩阵”，为了便于讨论验证算法的正确性同时也是为了让读者更加容易理解算法的结构逻辑，下面建立简单的模型，验证程序是否可行。

21

社会环境下网页重要性的研究

图3.1

PRin(i)=

?j(Kijn×

?nZijn×PRin(i-1)×Kijn) (3.5)

以上图示为了方便验证下面的结果是否正确，如图，圆圈表示访问者，方框表示网页，直线表示访问相应的网页。 3×0.7表示访问次数3次最终的Kijn为0.7，其他的依次类推。

图3.1设置的数值都很明显,访问者1的被认同度明显是高于其他三人，访问者4的被认同度明显低于其他三人，而访问者2的被认同度又高于访问者3，读者可以明显看出4个访问者的PR是PRi(1)> PRi(2)> PRi(3)> PRi(4)。如果下面的计算结果同上，则说明我所改进的算法，不存在逻辑的错误，计算结果没有错误。

Visual Basic作为非计算机专业科学工作者的常用编程软件深得使用者的好评，用来实现数学运算简单方便，可以将公式的(3.1)的运算关系表达的很清楚，但是存在的缺点是对于多重循环运算，对编程者的编程水平要求较高。Matlab是矩阵实验室（Matrix Laboratory）的简称，作为数学矩阵的专用软件，由美国新墨西哥大学教授设计，自诞生以来，版本从1.0到7.0，一直受到数学工作者的喜爱，对于数学矩阵运算编程方法简单，是数学运算的常用工具。本文改进算法可以表示为矩阵的运算，采用matlab计算比较合适，而且Google

22

社会环境下网页重要性的研究

搜索引擎就是用矩阵运算得出网页PR值的，但是缺点是不能够清楚表达原来的运算关系。比较两者的优缺点，采用两种方法同时编程运算，发挥两者的优点，使读者比较容易理解本文改进算法的设计思路。同时也是检验运算结果是否正确的双保险。[11]

3.2.4 Visual Basic编程验证算法收敛

将上面的算法结合上图编写相应的VB程序，运行循环结构后得出收敛后的结果验证算法的正确性：

private Sub Command1_Click() Dim m, n, l, i, j, k, o Dim PRi(1 To 4) Dim Zi(1 To 4, 1 To 4) Dim Ki(0 To 4, 1 To 4) Dim C(0 To 4) Dim T(0 To 4)

Dim PR(1 To 4, 1 To 9999) Dim P(1 To 4) Dim G(1 To 4)

Zi(1, 1) = 3: Zi(1, 2) = 0: Zi(1, 3) = 1: Zi(1, 4) = 2: Zi(2, 1) = 1: Zi(2, 2) = 4: Zi(2, 3) = 0: Zi(2, 4) = 3

Zi(3, 1) = 0: Zi(3, 2) = 2: Zi(3, 3) = 2: Zi(3, 4) = 0: Zi(4, 1) = 2: Zi(4, 2) = 0: Zi(4, 3) = 0: Zi(4, 4) = 1

PRi(1) = 1 / 4: PRi(2) = 1 / 4: PRi(3) = 1 / 4: PRi(4) = 1 / 4

Ki(1, 1) = 0.7: Ki(1, 2) = 0.5: Ki(1, 3) = 0.2: Ki(1, 4) = 0.1: Ki(2, 1) = 0.4: Ki(2, 2) = 0.5: Ki(2, 3) = 0.5: Ki(2, 4) = 0.1

Ki(3, 1) = 0.5: Ki(3, 2) = 0.5: Ki(3, 3) = 0.5: Ki(3, 4) = 0.5: Ki(4, 1) = 0.8: Ki(4, 2) = 0.5: Ki(4, 3) = 0.5: Ki(4, 4) = 0.2 For m = 1 To 200

P(1) = 0: P(2) = 0: P(3) = 0: P(4) = 0 For j = 1 To 4 o = 0 For n = 1 To 4

C(j) = Zi(j, n) * PRi(n) * Ki(j, n) T(j) = o + C(j) o = T(j) Next n

23

社会环境下网页重要性的研究

For n = 1 To 4 Ki(0, n) = 0 G(n) = Ki(j, n) * T(j) Next n For l = 1 To 4 P(l) = P(l) + G(l) Next l Next j For k = 1 To 4 PR(k, m) = P(k) Next k

Print \/ (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)); \m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)); \Print \第\次循环\ For n = 1 To 4 PRi(n) = PR(n, m) Next n If m = 100 Then

T1.Text = PR(1, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) T2.Text = PR(2, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) T3.Text = PR(3, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) T4.Text = PR(4, m) / (PR(1, m) + PR(2, m) + PR(3, m) + PR(4, m)) End If Next m End Sub

笔者在自己电脑上(电脑配置：主频1.01GHz，内存512MB)用Visual Baisc编制程序实现上述算法,并进行了实际的计算。为了方便论述,我们将网络结构简单化,假设仅仅有4个网页和4个访问者,如图3.1所示通过超链接相互联系。对图3.1所示的网页进行PageRank的计算，结果如图3.4所示(未全部列出, 图3.2中PRi(n)表示访问者n在i领域的PageRank值,精确到小数点后15位)

24

社会环境下网页重要性的研究

图3.2 VB源代码窗口图

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库Google网页排序算法中PageRank值(5)在线全文阅读。