Google网页排序算法中PageRank值

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

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

指导老师：陈强

邓青云 信息工程 20060003014

1

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

中文摘要

近年来，随着internet的不断发展，Web已经成为人们的重要信息来源，为人们提供了丰富的信息资源。与此同时，它所具有的海量数据、复杂性、极强的动态性和用户的多态性等特点也给We资源的发展发掘造成了相当的难度。通过分析和研究作为一种相当成功的基于超链分析的算法Google PageRank，可以有效地衡量网页重要度权值 ,然而进一步的研究也表明 ,这种纯粹依赖于超链分析的算法由于没有考虑到网页访问者对网页重要度权值的影响 ,所以在一定程度上会造成偏差 。因此 ,合理的将两者进行结合,充分利用访问者的知识水平和网页内容特征对PageRank 算法进行改进，得出最终搜索引擎排序优化算法，可以极大的提高这种算法的有效性和正确性。

关键词：超链分析，PageRank，算法，访问者，优化

2

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

ABSTRACT

In recent years, along with the continuous development of the Internet, Web has become an important source of information, the people for the people provides abundant information resources. Meanwhile, it has the mass data, complexity, and strong dynamics and characteristics of the user to ship polymorphism of the development of resources of excavation caused considerable difficulty. Through the analysis and research as a fairly successful based on the analysis of the algorithm is hyperlinked PageRank Google, which can effectively measure web importance weights, however, further studies have also shown that this kind of dinkum chain analysis depends not considering the algorithm due to web page visitors the influence degree of important value, so to some extent. Therefore, both are reasonable, fully utilize the knowledge level and visitors to page features PageRank algorithm was improved, the search engine optimization algorithm, can sort of improving the correctness and validity of this algorithm.

Keywords: hyperlink analysis algorithm, the visitor, PageRank optimization

3

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

目录

1．Google 搜索引擎简介 ............................................................................................................. 5

1.1 Google的软件文化理念 ................................................................................................... 5 1.2 搜索引擎的分类 ............................................................................................................... 5 1.3 Google搜索引擎工作原理[3] ............................................................................................ 6 2．传统Google PageRank算法分析 ............................................................................................ 9

2.1 传统Google PageRank算法概述[4]................................................................................. 9 2.2 传统 PageRank算法回顾.............................................................................................. 10

2.2.1传统 PageRank算法代数表达形式...................................................................... 10 2.2.2 传统 PageRank算法向量表达形式..................................................................... 12 2.3 传统Google PageRank的缺陷和改进方法 .................................................................. 13 3．Google PageRank 算法改进 .................................................................................................. 15

3.1由访问者知识水平及其投票的情况决定网页排名的 PageRank 算法...................... 15

3.1.1 算法中PR值的含义 ............................................................................................. 15 3.1.2 从投票角度分析算法的本质 ................................................................................ 15 3.1.3 算法改进的详细设计思路 .................................................................................... 16 3.2 计算每个访问者的PageRank值................................................................................... 17

3.2.1 计算访问者PR值的数学表达式 ......................................................................... 17 3.2.2 访问者PR值的循环收敛计算方法 ..................................................................... 19 3.2.3访问者PR值算法的简单模型 .............................................................................. 21 3.2.4 Visual Basic编程验证算法收敛 ............................................................................ 23 3.2.5 matlab编程验证算法收敛 ..................................................................................... 29 3.3 网页PR值的计算方法 .................................................................................................. 37

3.3.1 计算网页PR值的理论基础 ................................................................................. 37 3.3.2 建立数学模型 ........................................................................................................ 38 3.3.3 Visual Basic编程验证算法的正确性 .................................................................... 39 3.3.4 matlab编程验证算法的正确性 ............................................................................. 42

4．改进算法的事实可行性 ......................................................................................................... 44 5．将改进算法与Google PageRank传统算法结合的最完美排序方法 .................................. 46 6．小结 ......................................................................................................................................... 48 附录 ............................................................................................................................................... 49 参考文献 ....................................................................................................................................... 51 致谢 ............................................................................................................................................... 52

4

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

1．Google 搜索引擎简介

1.1 Google的软件文化理念

根据《中国互联网络发展状况统计报告 ( 2005/1) 》用户在互联网上获取信息最常用的方法是通过搜索引擎:占70. 7 %。远远高于位于第二位的直接访问已知的网站:占24. 6% 。搜索引擎的后起之秀 Google 每天处理的搜索请求已达 2 亿次。现在全球有75%的网上信息搜索是靠Google的技术完成，大大促进了人类的信息搜索的效率。而作为品牌价值，仅Google这个名字的无形资产，竟出人意料地在如此短的时间，一下子超过了苹果、IMB、可口可乐，真正实现了跳跃性的发展。Google主页面不以花哨取胜，而以功能表现为本。它的先进的软件理念正是建立在软件功能模块上，研究其功能特点，我们发现Google技术上的先进，来自于文化理念上的先进，并敢于打破传统独树一帜[1]。

首先，Google用先进的PageRank技术理念，以平等、实用、公正为组织原则，优化整合全球Web网页资源。在搜索方法上，Google更是化繁为简，为大多数网民利益考虑，做到软件使用大众化。其次，在对待语言工具的问题上，不搞大国沙文主义，真正摈弃了语言上的贵贱之分，将多种语言平等地整合在同一界面，实现了以人为本的软件理念。同时注重创新，注意吸纳新网站，以组成世界信息大家庭，并且充分尊重新网站的特殊要求和选择权利，再进行搜索引擎数据库的录入处理。再次，Google的中文搜索引擎的完美设计，体现了设计者的国际市场合作精神，Google搜索引擎对中文的支持力度，使它成为目前是收集亚洲网站最多的搜索引擎，同时能够取他人之长，与他人联手，以团队合作精神推出新技术新功能。

1.2 搜索引擎的分类

搜索引擎是指因特网上专门提供查询服务的一类网站,它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理,并为用户提供检索服务，从而起到信息导航的作用。

搜索引擎系统可以分为：目录式搜索引擎、机器人搜索引擎和元搜索引擎。 目录式搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新不及时。

机器人搜索引擎:是指通过网络搜索软件(又称为网络蜘蛛[2],网络爬行机器人,网络搜索机器人) 或网站登录等方式 ,以某种策略自动地在互联网中搜集和发现信息,经过加工处理后建库,从而能够对用户提出的各种查询作出响应,提供用户所需的信息。该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多无关信

5

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

息，用户必须从结果中进行筛选。这类搜索引擎的代表是： AltaVista 、Northern Light 、Excite 、Infos2 eek 、Inktomi 、FAST、Lycos 、Google ; 国内代表为：“天网”、 “百度”等。本文论述的Google 搜索引擎就是机器人搜索引擎，通过网络蜘蛛(Crawler) 搜集和发现网页排序所需要的信息。

目录式搜索引擎和机器人搜索引擎，各有优缺点，应用都很广泛。机器人搜索引擎的自动化程度比目录式搜索引擎高。网络信息量太大了，用计算机代替人去查找，可以节省大量的人力。

元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表是WebCrawler 、InfoMarket 等 .

1.3 Google搜索引擎工作原理[3]

搜索引擎一般由网络爬行机器人crawler、知识库Repository、索引系统(包括索引器indexer，桶barrels ,文件索引等)、排序器Sorter和搜索器Searcher 5个部分组成。

Google PageRank一般一年更新四次(由crawler程序的效率及搜索引擎的规模决定)，所以刚上线的新网站不可能获得PR值。你的网站很可能在相当长的时间里面看不到PR值的变化，特别是一些新的网站。PR值暂时没有，这不是什么不好的事情，耐心等待就好了。Google PageRank每更新一次都是按照以下的步骤进行：

(1)Google使用高速的分布式爬行器(Crawler)系统中的漫游遍历器(Googlebot)定时地遍历网页，将遍历到的网页送到存储服务器(Store Server)中。

(2)存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据Repository中。Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号(docID)。

(3)索引器(Indexer)从Repository中读取数据，以后做以下四步工作：

(4)(a)将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词(wordID)的若干索引项(Hits)，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(Barrels)中，并生成以文档号(docID)部分排序的顺排档索引。 索引项根据其重要程度分为两种：

当索引项中的关键词出现在URL、标题、锚文本(Anchor Text)和标签中时，表示该索引项比较重要，称为特殊索引项(Fancy Hits)；其余情况则称为普通索引项(Plain Hits)。 顺排档索引和Hit的存储结构如图1.1所示。

6

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

(b)索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其Anchor Text、URL指向等关键信息存入到Anchor文档库中。

(c)索引器生成一个索引词表(Lexicon)，它包括两个部分：关键词的列表和指针列表，用于倒排档文档相连接(如图1.1所示)。

(d)索引器还将分析过的网页编排成一个与Repository相连接的文档索引(Document Index)，并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL Server，以便在下一次工作流程中进行索引分析。

(5)URL分析器(URL Resolver)读取Anchor文档中的信息，然后做⑥中的工作。 (6)(a)将其锚文本(Anchor Text)所指向的URL转换成网页的docID；(b)将该docID与原网页的docID形成“链接对”，存入Link数据库中；(c)将Anchor Text指向的网页的docID与顺排档特殊索引项Anchor Hits相连接。

(7)数据库Link记录了网页的链接关系，用来计算网页的PageRank值。 (8)文档索引(Document Index)把没有进行索引分析的网页传递给URL Server，URL Server则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析。

(9)排序器(Sorter)对数据桶(Barrels)的顺排档索引重新进行排序，生成以关键词(wordID)为索引的倒排档索引。倒排档索引结构如图所示：

图1.1

(10)将生成的倒排档索引与先前由索引器产生的索引词表(Lexicon)相连接产生一个新的索引词表供搜索器(Searcher)使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引(Document Index)和Link数据库计算的网页PageRank值来匹配检索。

在执行检索时，Google通常遵循以下步骤(以下所指的是单个检索词的情况)： (1)将检索词转化成相应的wordID；

7

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

(2)利用Lexicon，检索出包含该wordID的网页的docID；

(3)根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引；

(4)根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序；

(5)调用Document Index中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。

这些过程都是离线进行的。当用户在线提交一个查询时，先从反向索引库中查找含有查询关键词的网页，返回一系列相关的网页的docID，由docID在存储PageRank的库中找到它们对应的PageRank值，然后将所有结果进行排序输出给用户。可以看出，整个过程中在线进行的只是查询，所有的计算都是离线进行的，因此搜索引擎能以较快的速度将结果返回给用户。另外，查询过程没有考虑用户提交的关键词和访问者的自身情况。基于链接的PageRank离线进行计算一次后，会在一段时间保持不变。据资料称，Google的PageRank计算周期大概是三个月。

8

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

2．传统Google PageRank算法分析

2.1 传统Google PageRank算法概述

我要做的工作是将PageRank的算法改进，所以先简述Google PageRank的情况方便下面的改进修改和对照。

超链分析技术主要是指利用网页间存在的各种超链指向, 对网页之间的引用关系进行分析，依据网页链入数的多少计算该网页的重要度权值，一般认为 ,如果A网页有超链指向B网页，相当于A网页投了B网页一票，即A认可B网页的重要性。深入理解超链分析算法，可以根据链接结构把整个网页文档集看作一个有向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的链接就构成了结点间的有向边，按照这个思想，可以根据 每个结点的出度和入度来评价网页的作用。

其中有代表性的算法主要是 Larry Page等人设计的PageRank算法和 Kleinberg 创造的HITS算法。其中PageRank算法在实际使用中的效果要好于 HITS算法，这主要是由于以下原因: a. PageRank 算法可以一次性、脱机并且独立于查询地对网页进行预计算，以得到网页重要度的估计值，然后在具体的用户查询中，结合其他查询指标值再一齐对查询结果进行相关性排序，从而节省了系统查询时的运算开销；b. PageRank 算法是利用整个网页集合进行计算的，不像HITS算法易受到局部连接陷阱的影响而产生“主题漂移”,所以现在这种技术广泛地应用在许多信息检索系统和网络搜索引擎中，Google 搜索引擎的成功也表明了以超链分析为特征的网页相关度排序算法日益成熟。

但是 PageRank算法由于只考虑到网页间的超链关系并仅仅以此进行网页重要度的分析，所以不可避免地会产生很多问题，其中，比较明显的问题在于它在计算每个网页具体的重要度权值的时候，根本没有考虑到任何网页本身内容特征对权值的影响，如PageRank算法完全忽略了网页具有的不同主题，不同的主题应该具有不同的重要度权值，进一步说，在用户查询的时候，网页的重要程度值的大小与查询所表达的主题关系很大，其实，在HITS算法[5]中恰恰考虑了这种因素，所以它更易于表达与特定查询主题的相关度排序，有效地在PageRank算法中考虑查询主题对网页权重值的影响是一个有效改进此算法的重要方法，再如，PageRank算法也没有考虑网页的创建时间 ,并不对新旧网页进行有效的区分,相反 ,按照 PageRank 的既有算法甚至会产生旧网页比新网页具有较高重要度权值的可能性。这些都是Google PageRank存在的缺点，也是本文对PageRank算法进行改进的原因。

[4]

9

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

2.2 传统 PageRank算法回顾

PageRank技术：通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。

虽然 PageRank 认为网页的链入超链数可以反应该网页的重要程度 ,但是现实中人们在设计网页的各种超链时往往并不严格，有很多网页的超链纯粹是为了诸如网页导航、商业推荐等目的而制作的，显然这类网页对于它所指向网页的重要度贡献程度并不高，但是，由于算法的复杂性，PageRank 没有过多考虑网页超链内容对网页重要度的影响,只是使用了两个相对简单的方法： 其一，如果一个网页的链出网页数太多，则它对每个链出网页重要度的认可能力相应降低；其二， 如果一个网页由于本身链入网页数很低造成它的重要度降低，则它对它的链出 网页重要度的影响也相应降低。综上而言，一个网页的重要性决定着同时也依赖于其他网页的重要性。

PageRank绝对是个很科学的小创意。说他科学，你会在我以后的文章中看到Google是如何将数学(具体来说多数是统计学)理论淋漓尽致地发挥在搜索技术之中。说他“小”，因为这些理论对于搞数学的人来说实在太微不足道了，甚至稍微有些科学高数知识的人都能理解。他所用到的统计学就是循环迭代计算收敛值的方法！[6]

2.2.1传统 PageRank算法代数表达形式

按照上面思路，Page给出了PageRank的简单定义[7]：

R?u??Cv?B?u??R?v??N?v? (2.1)

此处的u表示一个网页，R ( u) 表示网页u的PageRank值，B ( u)表示链接到网页u的网页集合，即网页u 的链入网页集合，N ( v ) 表示从网页 v 向外的链接数量，即网页v 的链出网页数，C为规范化因子，用于保证所有网页的PageRank总和为常量 (如为1)。

这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则Aij=1/Ni，否则Aij=0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。

具体计算时，可以给每个网页一个初始的PageRank值，然后反复迭代运算，即 ：

R(i+1)(v)=

u?B?v??R(i)(u)/Nu (2.2)

此处的 v 代表所有的网页集合,每一个第i+1次的PageRank 值都是基于上次的PageRank值重新计算的。具体的迭代次数在实际运算中是有限的。

Lawrence Page和Sergey Brin在个别场合描述了PageRank最初的算法。这就是 PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 式中：PR(A) :网页A页的PageRank值；

PR(Ti) :链接到A页的网页Ti的PageRank值；

10

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

C(Ti) :网页Ti的出站链接数量； d :阻尼系数，0

上式最初算法只是表达了PageRank的基本计算原理，并不具有普遍性，因为没有迭代收敛的步骤。

所有PR(Ti)之和还要乘以一个阻尼系数d，它的值在0到1之间。阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。

一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。并且，阻尼系数d减低了这个概率。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。

PageRank的特性可以通过以下范例用插图表示。

图2.1

假设一个小网站由三个页面A、B、C组成，A连接到B和C，B连接到C，C连接到A。虽然Page和Brin实际上将阻尼系数d设为0.85，但这里我们为了简便计算就将其设为0.5。尽管阻尼系数d的精确值无疑是影响到PageRank值的，可是它并不影响PageRank计算的原理。因此，我们得到以下计算PageRank值的方程： PR(A) = 0.5 + 0.5 PR(C) PR(B) = 0.5 + 0.5 (PR(A) / 2) PR(C)=0.5+0.5(PR(A)/2+PR(B))

这些方程很容易求解，以下得到每个页面的PageRank值： PR(A)= 14/13 = 1.07692308 PR(B)=10/13 = 0.76923077 PR(B)=15/13 = 1.15384615

很明显所有页面PageRank之和为3，等于网页的总数。就像以上所提的，此结果对于这个简单的范例来说并不特殊。

对于这个只有三个页面的简单范例来说，通过方程组很容易求得PageRank值。但实际上，互联网包含数以亿计的文档，是不可能解方程组的。下面阐述迭代过程。

由于实际的互联网网页数量，Google搜索引擎使用了一个近似的、迭代的计算方法计算PageRank值。就是说先给每个网页一个初始值，然后利用上面的公式，循环进行有限次运算得到近似的PageRank值。我们再次使用“三页面”的范例来说明迭代计算，这里设每个页面的初始值为1。 迭代次数 PR(A) PR(B) PR(C) 0 1 2

1 1 1.0625

1 0.75 0.765625

1 1.125 1.1484375

11

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

3 4 5 6 7 8 9 10 11 12

1.07421875 0.76855469 1.15283203 1.07641602 0.76910400 1.15365601 1.07682800 0.76920700 1.15381050 1.07690525 0.76922631 1.15383947 1.07691973 0.76922993 1.15384490 1.07692245 0.76923061 1.15384592 1.07692296 0.76923074 1.15384611 1.07692305 0.76923076 1.15384615 1.07692307 0.76923077 1.15384615 1.07692308 0.76923077 1.15384615

重复几次后，我们的到一个良好的接近PageRank理想值的近似值。根据Lawrence Page和Sergey Brin共开发表的文章，他们实际需要进行100次迭代才能得到整个互联网的满意的网页级别值。

同样，用迭代计算的方式，每个网页的PageRank值之和仍然收敛于整个网络的页面数的。因此，每个页面的平均的PageRank值为1。实际上的值在(1－d)和(dN+(1-d))之间，这里的N是互联网网页总数。如果所有页面都连接到一个页面，并且此页单独地连接自身，那么将出现理论上的最大值。

2.2.2 传统 PageRank算法向量表达形式

2的计算,首先每个网页文档的PageRank 值可上述过程在本质上可以表达为特征向量○

以表示一个向量 ,即一个 N 行1列的向量 (N 为所有的网文档数)，为了便于计算，开始时可以给每个元素的值设为 1/ N。

Rank = ［1/ N ］n ×1

设M为一个随机矩阵，它的横纵行列数分别为整个网页集合的文档数，每个矩阵元素值表示两两网页之间的链接关系,即如果网页Di指向Dj，则矩阵元素Mij 对应的值为1/ Ni ( Ni表示Di的链出网页数)；如果网页Di不指向Dj，则M ij值为 0。

?m11,m12,..........,m1n???m21,m22,.........,m2n??? M=?..................................???mn1,mn2,..........mnn?所以 , PageRank 值的计算就可以表示为：

Rank = MT ×Rank (2.3)

而且这个过程是个反复迭代的过程,直至 Rank值最终收敛。但是，实际的网页结构并

12

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

非表现为一个完全牢固的链接图，不是所有的网页都可以从其他网页 通过超链来达到，而PageRank值的计算正依赖于此，所以Page等人就提出了改进方案，对存在的等级沉没(Rank Sink)和等级泄漏(Rank Leak)[8]等问题进行了有效的解决。整个网页图中的一组紧密链接的网页如果没有外出的链接就产生等级沉没，一个独立的网页如果没有外出的链接就产生等级泄漏。所以，Page改进措施为：一是剔除产生等级泄漏的独立网页以消除其不利影响；二是给产生等级沉没的网页添加一个指向链入网页的返回链接，此时使得所有网页 PageRank 值的计算就不完全依赖现有链接了，所以修正的PageRank计算公式为 ：

R?u??C?v?B(u)R(v)/N(v)?CE(u) (2.4)

其中，‖R′‖1=1，对应的矩阵形式为V’=c(AV’+E)。

E(u)是个常量，它可以抑制 PageRank 值的传播，使得所有网页的PageRank 值至少会为E ( u) ，而不会为0。具体的E ( u)值可以有多种取法，简单的做法可以设为p，如取1/ N ( N为网页文档总数)。

从特征向量的角度来考察，可以设置P列向量以代表每个网页文档都有的、相同的E ( u)

P??1/N?n?1

PageRank迭代运算都利用了特征向量作为理论基础和收敛性依据[9]，这是超链接环境下此类算法的一个共同特征。

设置 D 向量以代表网页文档的链出网页数是否为 0 , 即 1 如果网页Di的链出网页数为0 Di= 0 如果网页Di的链出网页数非0

则上述 PageRank 的计算可以进一步表达为 :

Rank = C ( M + P ×D T ) ×Rank + C P

2.3 传统Google PageRank的缺陷和改进方法

基于链接分析的算法 ,目前的研究都还很不成熟，无论是Page Rank算法，还是HITS算法等，有一些共同的问题影响着算法的精度。

( 1) 根集的质量。根集质量应该是很高的 , 否则 , 扩展后的网页集会增加很多无关的网页 , 产生主题漂移、主题泛化等一系列的问题 ,计算量也增加很多。 算法再好 ,也无法在低质量网页集找出很多高质量的 网页。

(2) 锚文本的利用。锚文本有很高的精度 ,对链接 和目标网页的描述比较精确。上述算法在具体的 实现中利用了锚文本来改进算法。如何准确充分地利用锚文本 ,对算法的精度影响很大。

13

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

(3) 噪音链接。Web 上不是每个链接都包含了有用的信息，比如广告、站点导航、赞助商、用于友情交换的链接，对于链接分析不仅没有帮助，而且还影 响结果。如何有效去除这些无关链接，也是算法的一个关键点。

(4) 查询的分类。每种算法都有自身的适用情况 , 对于不同的查询 ,应该采用不同的算法 ,以求获得最好的结果。因此 ,对于查询的分类也显得非常重要。

文中对Google PageRank算法进行了深入探讨和比较,但在这几个方面需要继续做深入的研究,相信在不久的将来会有更多的有价值的成果出现。本文正是针对Google PageRank存在的问题进行算法的改进，将改进的算法和Google PageRank的传统算法完美结合，不仅解决的Google PageRank完全不考虑访问者自身知识水平的缺陷，还预示了将不同算法结合是未来搜索引擎的发展趋势。

14

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

3．Google PageRank 算法改进

3.1由访问者知识水平及其投票的情况决定网页排名的 PageRank 算法

3.1.1 算法中PR值的含义

在Google PageRank传统算法中，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，Google才更改了度量。 转化为0~10度量 。因此可以认为传统算法的网页PR值，反映了网页的热度(访问人数)，PR值越大，则表示网页越热，越多人访问。

在改进算法中，访问者的PR值表示为PRin，PRin越大则表示访问者的专业知识水平越高。网页的PR值表示为Pij，Pij越大表示网页的权威性、正确性越大。

3.1.2 从投票角度分析算法的本质

从投票的角度来分析两种算法的本质：Google PageRank传统算法中，从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票，由其他网页对网页本身的投票来计算网页的PR值。在改进算法中，访问者对网页的投票的被认同度就是其他访问者对他的投票，由其他访问者对他的投票来计算访问者的PR值。在计算网页PR值时，网页由访问者对它的投票来决定网页的PR值。

不是每个访问者和网页的投票都是对访问者或者网页的PR值贡献一样的，因为每个访问者和网页的权重不一样，两者的权重分别与它们的知识水平和网页权威性有关。因此计算两者PR值之前要计算两者的权重。

权重是一个相对的概念，是针对某一指标而言。某一指标的权重是指该指标在整体评价中的相对重要程度。

权重表示在评价过程中，是被评价对象的不同侧面的重要程度的定量分配，对各评价因子在总体评价中的作用进行区别对待。事实上，没有重点的评价就不算是客观的评价。

打个比方说, 一件事情, 你给它打100分, 你的老板给它打60分, 如果平均, 则是(100+60)/2=80分. 但因为老板说的话分量比你重, 假如老板的权重是2, 你是1, 这时求平均值就是加权平均了, 结果是(100*1 + 60*2)/(1+2)=73.3分, 显然向你的老板那里倾斜了。假如老板权重是3，你的权重是1，结果是(100*1+60*3)/(1+3)=70。这就是根据权重的不同进行的平均数的计算，所以又叫加权平均数。

同样道理每个访问者和每个网页的权重都是不同的因为他们的权威性是不同的。例如：一个工程院院士关于PageRank网页的投票的权重，比我对PageRank网页的投票的权重大

15

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

得多，因为院士的该领域知识水平(PR值)远远高于我。

接着是看投票情况，如果院士投了反对票，这个网页的PR将大打折扣，如果我投了反对票，对网页PR的影响可能不大，因为我的权重比院士的权重小很多。

网页也有它的权重，因为访问者在不同权重的网页被认同，对访问者的PR值贡献是不同的。例如，我在中国期刊网的投票被别人赞同，和在自己QQ空间被被人赞同，前者将大大增加我的PR值，后者影响较小，因为两个网页的权重差几个数量级。

权重就是反映影响力的一个值，访问者的权重越大，则对网页的PR值影响越大，至于是正面还是负面影响，还有看投票评价情况。在计算PRin时，网页的权重越大，则对访问者的PR影响越大，至于是正面还是负面影响，还有看投票评价被认同情况。

3.1.3 算法改进的详细设计思路

事实上，PageRank 值虽然在一定程度上表达了网页与用户查询的相关度 ,但是存在的问题也是明显的, 其中最明显的在于 PageRank 的计算是独立于用户查询而进行的先期运算，根本没有考虑访问者自身的情况和访问者对网页的评价，这样，网页的PageRank值只是一个基于全部网页集合计算出来的一个独立值。而网页的排名不应该单单看网页的访问量，还要看网页内容的权威性和正确性，因为每个用搜索引擎的访问者希望自己搜索的结果是正确的具有一定的权威性的，当然网络多人访问在一定程度上说明了它的正确性，但是也不能够完全这样来判断网页的正确性，还要结合访问者对网页的评价来决定网页的权威性和正确性。但是PageRank算法仅仅根据访问量来决定网站的重要性，这个有点不完善，搜索引擎不单只要返回多人关注的网站排位，而且还要考虑网站的内容是否正确权威，这个可以从访问者的知识水平来判断网页的权威性。

我做的工作就是增加访问者的具体情况影响PageRank值，首先就是访问者的知识水平不同他对网站的PR值贡献不同，在不同的领域不同的访问者具有不同PR(PageRank，下同)值，这个PR值，首先计算每个访问者的PR值，类似PageRank根据链接数量判断网页重要性的算法首先假设有N个访问者每个访问者本身有一个PR值1/ N。有的网站允许访问者对网页内容评价，这时多数的访问者表态代表了正确的评价，即访问者的评价对网页的评价得到越多的人的赞同则访问者的PR值越高，否则就越低，通过大量的访问记录，则统计结果表明访问者本身的PR值，同时由于访问者在不同领域的知识水平不同，应该在不同的领域有不同的PR值，假设网页根据内容可以划分为i类，即分为i个领域，则访问者在i领域的PageRank值为PR(i)，网络网站总量为T，i领域的网站的总量是T(i)。

将所有网站分为两类：一种是访问者可以投票的网站，第二种是访问者不可以投票。投票网站一般给出 好、中、差 或者是赞成、反对、中立等几个选项给访问者直接选择，访问者只可以选择其中一个对网页进行评价。投票又可以分为登录投票和匿名投票，都没有问题，因为下面会讲到本文是由物理地址标志访问者的。同时现在的网站大部分都是分主题的，一个网站就是讲一个领域的知识，按照现在的比例百分之九十八的网站都是讲一

16

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

个领域或者说是主题的内容(分类网页)，例如体育、军事、健康、新闻、娱乐……等等，大概有百分之二的网站是同时具有几个主题的(非分类网页)，根据这个情况，我们可以抓主要的先，先将网页分为i个主题，每个主题的网页是j个，最后才考虑多个主题的少数网页，这些非分类网页的PR值可以通过由分类网页计算出来的访问者PR值计算，因为分类网页的算法是根据绝大部分网页(约98%)来计算访问者PR值的，非分类网页(约2%)对访问者PR值的计算的影响微乎其微[10]。因此由分类网页计算出来的访问者PR值来计算网页的PR值具有统计特性，可以准确反映每个访问者的实际情况，这样计算出来的PR值是可靠的，反映了网页的真实重要性(也就是网页的权威性和正确性)，所以计算访问者的PR值只需要根据分类网页来计算即可，根据计算出来的每个访问者在不同领域的不同PR值，结合某个网页被每一个访问者的访问次数和投票情况决定了网页的PR值，因为搜索者不但要找的是人气高的、重要的网站，而且要求网站的内容是权威的准确的，所以访问者每次访问这个网站的投票情况，将影响网页的排名。为了表示投票情况，先设置一个参数Kijn，表示访问者对网页Pij的投票评价的被认同度。

由于本论文研究的改进搜索引擎排序算法是由访问者的知识水平及其投票情况决定网页的排名，因此在计算网页的PR值之前首先就要求出访问者本身的PR值，第二步才是求网页的PR值，下面将改进方法分两步详细说明。

3.2 计算每个访问者的PageRank值

3.2.1 计算访问者PR值的数学表达式

为了下面的运算现在设置好运算的变量，假设总共N个访问者，整个网络的网页有b=98%的网页是单一主题的，另外的2%网页具有多个主题，单一主题的网页可以分为i个领域，每个领域有j个网页，因此Pij就指向具体的任何一个网页。

首先计算某个访问者n在i领域的PR值PRin，设Zijn表示访问者n对网页Pij的访问次数，Kijn为访问者n对网页Pij的投票评价的被认同度 (例如：10个访问者访问网页Pij，其中8人投赞成票，2人投反对票。则投了赞成票的8个人的Kijn为80%或0.8，投反对票的2人的Kijn为20%或0.2)。 访问者在i领域的PR值PRin可以用下式表示

PRin=

?j(Kijn ×?Zijn×PRin×Kijn) (3.1)

n 上式两边都有PRin，不是说上式存在错误，上式只是表达出了一种计算思路，遇到由自身求自身的数学问题，类似先有蛋还是先有鸡的问题，在这里和Google PageRank传统算法计算网页PR的情况类似了，式(2.1)也是由网页自身PR值求网页自身PR值，因此我们可以完全借鉴Google PageRank传统的计算思路，利用循环计算收敛值的方法解决

17

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

这个问题。

下面详细分析一下上式(3.1)的思路：

?Zijn×PRin×Kijn (3.2)

n1，这个权重乘以Kijn得出网页j对访问者n的PR值的式(3.2)整体可以看做网页j权重○

贡献，将i领域所有网页的贡献叠加就得到访问者n在i领域的PR值表示为PRin。笼统来说访问者在每一个网页的被认同度越高，访问者的PR值就越高，但是每个网页对访问者的PR值计算中贡献的份量是不一样的，也就是权重不同，举个例子，像中国期刊网的权重是非常大的，比一般的QQ空间要大几个数量级，当访问者在中国期刊网得到认同，和访问者在自己的QQ空间被别人认同对访问者的PR计算的贡献是差异极大的，相差好几个数量级。所以计算PRin时首先要算出网页的权重。

?Zijn×PRin×Kijn

n式(3.2)中的Zijn×PRin也是一个权重，表示访问者n在计算网页j权重中的份量，乘以Zijn的原因是，访问者访问的次数越多，说明这个网页越受访问者n关注，称为关注度，当然一个网页受访问者n关注越多，并不表示网页j的权重(3.2)越大，还要看访问者的被认同度Kijn，Zijn×PRin只是作为一个权重 ，还要看他的意见是否得到大家的赞同，所以乘以Kijn，简单举个例子，一个资深的学者访问一个本专业的网页，并不是访问次数越多对网页权重的贡献就越大，还要乘以一个系数Kijn，当没有人同意这位资深学者的评价时，这位资深学者本身在这个领域很高的PR值当然不可以贡献在网页j的权重上，相反如果很多人赞同这位资深学者的评价，即Kijn很大，这位资深学者本身的PR就会很大比例地对网页j的权重做出贡献。

Kijn表示在投票网页Pij的所有访问者之中，与访问者n有相同投票的人占得比例。考虑到不是每个网站都设置有投票栏，也不是每个领域所有的网站，访问者n都会去访问，有的访问者访问了网站却不一定会投票，因此上式中的Kijn分四种情况，具体如下：

与访问者n相同的评价(投票)占所有评价的比例

Kijn= 50% ，网页没有投票栏

表达式一

50%，访问者没有投票

0 ，访问者n没有访问网页Pij

18

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

表达式一的表示其实不严密，有少数访问者会多次访问同一个网页但是在这部分人之中又会有极少数的人会对网站的评价进行多次不同的投票也就是给出不同的评价，这并不奇怪，因为人的思想是随着认知水平和社会情况而变化的，因此越后面的投票越具有权威性，因此最后面投票基本反映了最近的社会情况，越后的投票时访问者经过更加缜密结合了最新的事实综合考虑的结果，因此我们只需要考虑访问者最好一次的投票，为了使计算更加精确所以有必要对Kijn进行修正：

与访问者最后一次的评价(投票)相同的评价占所有评价的比例

Kijn= 50 %，网页没有投票栏 表达式二

50%，访问者没有投票

0 ，访问者n没有访问网页Pij

这时有人可能会问，既然上面已经对Kijn进行了修正，Kijn其实是考虑最后一次投票的，再乘以访问次数，显得不合理，这样的说法其实不对因为访问者访问这个网站越多就说明对这个网站关注越多，说明这个网站比较重要，再乘以访问者对网站的最终评价，正好反映了网站的权威性重要性。一个本身PR值越高的人访问某网页的次数越多则网页越重要。对网页内容的评价越高则网页越权威相应的PR值越高，因此以上表达式是合理的可行的。

3.2.2 访问者PR值的循环收敛计算方法

类似Google PageRank计算方法，首先赋予每个访问者相同的PageRank值简称PR值，首先假设每个访问者的PR值为常数。

PRin(i+1)=

?j(Kijn ×?Zijn×PRin(i)×Kijn) (3.3)

n这里是根据上一次的PRin计算下一次的PRin，设

L=?Zijn×PRin(i)×Kijn

n则上式可以表达为

PRin(i+1)=

?j(Kijn×L)。

19

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

上式表示对i领域的所有网页中访问者n被认同度的叠加得到PRin，但是相同的认同度对于不同的网页所对访问者的PR值贡献是不同的，所以对于不同的网页有不同的权重，乘以这个权重就比较准确反映了 j网页对访问者n的PR值的贡献。L的具体算法是

(i)

?Zijn×PRin×Kijn

n L权重是由访问者本身的权重乘以访问次数(访问次数越多说明网页越受关注)。访问者本身有PR值但是只有访问者被认同越高，他本身的PR值才会对网页的权重做出越多贡献(只有访问者被认同越高，本身的PR值才会对网页的PR做出相应的贡献，所以乘以Kijn)。

考虑到还有2?的网站是非分类网页，非分类网页的PR值需要根据每个访问者在相关领域的PR值来计算，与两个以上的领域有关的非分类网页的PR值，是将本网页有关的领域的PR值的叠加再除以涉及到的领域数，而不是在单独的领域计算总的PR值，如果不将不同领域的所有访问者的PR值进行归一化将出现以下的情况，一个访问者在两个不同的领域的知识水平一样但是他在这两个领域的PR值相差很大，如果一个非分类网页包含这两个领域，将各个领域的网页PR相加得到总的PR的方法计算的结果将会出现偏差，因为式(3.1)中，不同领域的PRin是独立运算的，计算分类网页时只需要结果分出相对大小就行，对计算出来的PRin本身的大小则不要求，式(3.1)仅仅限于单领域网页即分类网页的PR计算，因此在不同领域它们的基数不一样，为了使计算结果更加准确，所以必须要对PRin进行归一化以方便跨领域的PR值叠加运算。为了避免出现不同领域总的PR值不同给下面计算非分类网页总的PR值带来偏差的情况，下面对计算所有访问者对各个领域的总的PR值的和。

PRi=?PRin

n设置归一化常数Ci=

n1

?PRin因此最后得出某个访问者n在i领域的PR值

PRin(i+1)=Ci

?j(Kijn ×?nZijn×PRin(i)×Kijn) (3.4)

上式就是结合访问者的自身情况得出的改进算法 算法描述如下：

PRin(0) =

1N //初始化每个访问者的PageRank

while (|PRin(i)- PRin(i-1)|>ε) //PageRank收敛前的循环计算判断 {ε=0.0000000000001 i=1

for each n∈N

20

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

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

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

图3.3 VB运行结果图

26

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

27

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

图3.4 PageRank的计算结果

由上式可以看出，每一个第i+1次的PageRank值都是基于上次的PageRank值重新计算的。具体的迭代次数在实际中是无限的。循环次数越多，计算结果越收敛于(越接近)网

28

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

页的真实PR值。数据的精度设置越高则循环次数就越多[12]，但是实际上将网页的PR值按大小排序无需太高的精度，可以区分出网页PR值大小就行，这样对PRin的精度要求也无需太高，精确到小数点后十五位就足够。上面的循环运算的计算结果越来越趋向一个值，根据计算结果，第十六次的循环计算已经收敛到小数点后14位，我开始定义的数组数据类型为双精度(Double)占8个字节，16位的最高位数已经被突破，再下去的循环计算已经没有意义，在另一方面也反映了我的算法具有无限的精度，循环次数越多则精确位数越多，所以我的算法在精度方面是完全符合要求无可挑剔的。但是循环次数少就达到收敛效果不是说明我的循环次数设置那么高是多此一举，因为上面是属于最简单的模型，达到收敛所需的次数当然是最少的，同样的算法对于互联网数以亿计的网页和访问者，运算量是巨大的，循环次数更是非常巨大，上面只是简单的模型，目的是使读者更加理解我设计的算法，同时也验证了我的算法的正确性。

3.2.5 matlab编程验证算法收敛

上述过程本质上可以表达为特征向量的计算，首先每个访问者在i领域的PR值可以表示一个矩阵，即一个N行N列的矩阵(N为整个网络访问者的总数，j为i领域所有的网页数)为了方便计算，开始时可以给每个元素的值都设为

1N。

1?1111?,,,,....,?NNNNN???11111?,,,,....?,?NNNNN???11111,,,....? PRin=?1???n×n= ?,?NNNNN??................................???1??1111,,,....,?NNNNN?????

设Zijn为一个随机矩阵它的横向表示同一个网页被不同访问者访问的次数，纵向表示同一访问者对同一领域不同网页的访问次数

?Zi11,Zi12,Zi13.....,Zi1n???Zi21,Zi22,Zi23.....,Zi2n??Zijn= ?Zi31,Zi32,Zi33.....,Zi3n?

??.......,.........,.......,......,......???Zij1,Zij2,Zij3.....,Zijn???同理设Kijn为一个随机矩阵它的横向表示同一个访问者不同网页的Kijn 。纵向表示不同

29

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

访问者对同一个网页的Kijn

?Ki11,Ki12,Ki13,......Ki1n???Ki21,Ki22,Ki23,......Ki2n??Kijn=?Ki31,Ki32,Ki33,......Ki3n?

??........,........,.........,.....,.....,???Kij1,Kij2,Kij3,......Kijn???PRin=

?j(Kijn×

?nZijn×PRin×Kijn) (3.1)

因此?Zijn×PRin×Kijn可以用矩阵运算表示为((Kijn.*(PRin.*Zijn))*L)

n(在matlab数学矩阵运算中，对于行列数相同的矩阵A和B，A.*B表示A与B的各元素对应相乘，所得的结果作为结果矩阵相应位置的元素。

举例：??1,2??5,6??1?5,2?6?[13]

?.*??=??) ?3,4??7,8??3?7,4?8?

?1???1??其中L为N行一列的矩阵列向量?1?

???...??1??? (Kijn.*(PRin.*Zijn)与L相乘，相当于数学表达式的求和符号?，在这里L起到的作用

n是求和，L的各元素的值为1，相乘之后不改变值的大小，其起的作用相当于+号，将(Kijn.*(PRin.*Zijn)的行元素相加，所得的结果为j行1列的矩阵。 上式可以用矩阵相乘表示为 ((Kijn.*(PRin.*Zijn))*L)=

30

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

(

?Ki11,Ki12,Ki13,......Ki1n???Ki21,Ki22,Ki23,......Ki2n???Ki31,Ki32,Ki33,......Ki3n? ??........,........,.........,.....,.....,???Kij1,Kij2,Kij3,......Kijn???.*

(

1?1111,,,,....,?NNNNN??1,1,1,1,....,1?NNNNN?11111 ?,,,,....?NNNNN?................................?1?1111,,,....,?NNNNN????????????????n??Zi11,Zi12,Zi13.....,Zi1??Zi21,Zi22,Zi23.....,Zi2n??.*?Zi31,Zi32,Zi33.....,Zi3n???.......,.........,.......,......,......???Zij1,Zij2,Zij3.....,Zijn???))*

?1???1???1? (3.6)???...??1???

上式前三个矩阵相乘的结果是一个j行N列的向量，每一行的N个元素分别表示每个访问者对网页j的权重贡献，为了计算Pij网页的总的PR值必须将同一行N个贡献相加，为了实现相加的结果，可以在上面三个矩阵的后面乘多一个N行1列每个元素为1的列向量矩阵

?1???1???1????...??1???

计算的结果将是一个N行一列的列向量矩阵，设这个列向量矩阵为Sj，Sj就表示所有的

访问者对网页Pij贡献的权重值。 则式(3.1)表示为

PRin=

?j(Kijn ×S)

上面的运算思想参考了Google PageRank的排序算法

R(i+1)(v)=C

v?B?v??R(i)(u)/Nu (2.2)

R(i)(u)表示第i次叠加运算时的网页PR值,相当于Sj(上一次运算网页Pij的权重值) 乘以

1Nu。Nu表示网页的链接数，Nu少说明此网页链接出的单条链接贡献给链接到网页

的PR值越大，这与乘以Kijn (被认同度越高，则访问者的PR值越高)的思想是完全一致的。同样经过叠加运算，最后的结果必然收敛于一个特定的值。具体详细的迭代下面再详解

31

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

下面先用矩阵表示PRin=

?j(Kijn ×S)

PRin=ST *Kijn (矩阵ST为矩阵S的转置矩阵)

ST是一个行矩阵，各元素表示每个网页的权重，矩阵Kijn的每一列表示同一个访问者对于每个网页的被认同度，ST与Kijn的每一列元素对应相乘再相加的结果就是Kijn中相应列的访问者的PRin。

上式得到的结果是一个一行N列的行向量，各元素分别表示每个访问者自身的PRin上面是矩阵运算，是一种计算方法的总的表达方式，要验证上面的矩阵算法是否正确需要举例验证，就像上面VB编程一样，下面我仍然用图3.1的数据例子用矩阵运算，如果运算结果和VB算法一样说明计算结果没有错误，同时证明两种方法都是可行的。Matlab能处理数、向量和矩阵．但一个数事实上是一个1×1的矩阵，1个n维向量也不过是一个1×n或n×1的矩阵．从这个角度上来讲，Matlab处理的所有的数据都是矩阵．Matlab的矩阵处理能力是非常灵活、强大的．以下我们将用matlab来进行矩阵运算。 下面首先编写matlab程序： PRi1=0.25; PRi2=0.25; PRi3=0.25; PRi4=0.25; L=[1;1;1;1]; i=1 while i<=20

PRin=[PRi1,PRi2,PRi3,PRi4;PRi1,PRi2,PRi3,PRi4;PRi1,PRi2,PRi3,PRi4;PRi1,PRi2,PRi3,PRi4];

Zijn=[3,0,1,2;1,4,0,3;0,2,2,0;2,0,0,1];

Kijn=[0.7,0.5,0.2,0.1;0.4,0.5,0.5,0.1;0.5,0.5,0.5,0.5;0.8,0.5,0.5,0.2]; zPRin=((Kijn.*(PRin.*Zijn))*L)'*Kijn ; PRi=(1/(zPRin*[1;1;1;1]))*zPRin t=1; y= PRi (1,1); m=2; x= PRi (1,2); n=3; v= PRi (1,3); l=4; p= PRi (1,4);

32

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

hold on

plot(t+0.05*i,y,'-r',m+0.05*i,x,'-r',n+0.05*i,v,'-r',l+0.05*i,p,'-r') PRi1= PRi (1,1); PRi2= PRi (1,2); PRi3= PRi (1,3); PRi4= PRi (1,4); i=i+1 end

运算结果显示如下 i = 1 PRi =

0.342207792207792 i = 2 PRi =

0.348649402475917 i = 3 PRi =

0.349386378902118 i = 4 PRi =

0.349467206106789 i = 5 PRi =

0.349476125018587 i = 6 PRi =

0.349477108296626

0.292207792207792 0.292668797871656 0.292734440342258 0.29274125949571 0.292742016418722 0.292742099801721 0.243506493506493 0.122077922077922 0.240348430560621 0.118333369091806 0.240023620867169 0.117855559888455 0.23998737951074 0.117804154886761 0.239983388537883 0.117798470024808 0.239982948433407 0.117797843468246

33

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

i = 7 PRi =

0.349477216709329 0.292742108996117 0.23998289991064 0.117797774383914 i = 8 PRi =

0.349477228662355 i = 9 PRi =

0.349477229980236 i = 10 PRi =

0.349477230125539 i = 11 PRi =

0.34947723014156 i = 12 PRi =

0.349477230143326 i = 13 PRi =

0.349477230143521 i = 14 PRi =

0.349477230143542 i = 15 PRi =

0.349477230143544

0.292742110009832 0.239982894560747 0.292742110121599 0.239982893970895 0.292742110133922 0.239982893905861 0.292742110135281 0.239982893898691 0.29274211013543 0.2399828938979 0.292742110135447 0.239982893897813 0.292742110135449 0.239982893897803 0.292742110135449 0.239982893897802 34

0.117797766767066 0.117797765927269 0.117797765834678 0.117797765824469 0.117797765823344 0.117797765823219 0.117797765823206 0.117797765823204

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

i = 16 PRi =

0.349477230143545 0.292742110135449 0.239982893897802 0.117797765823204 i = 17 PRi =

0.349477230143545 i = 18 PRi =

0.349477230143545 i = 19 PRi =

0.349477230143545 i = 20 PRi =

0.349477230143545 i = 21 >>

>>显示图形如图：

0.292742110135449 0.292742110135449 0.292742110135449 0.292742110135449 0.239982893897802 0.117797765823204 0.239982893897802 0.117797765823204 0.239982893897802 0.117797765823204 0.239982893897802 0.117797765823204 35

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

图3.5 Matlab运行结果图形

上面四条收敛曲线的点分别对应每次循环计算得出的PRin的值，从左往右分别表示PRi(1)、PRi(2)、PRi(3)、PRi(4)。四条收敛曲线反映了改进算法计算的PRin值最后是收敛的，验证了原先的推理，因此算法最后收敛成立。同时说明上面设计的改进算法是可行的。

36

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

3.3 网页PR值的计算方法

3.3.1 计算网页PR值的理论基础

最后结合每个访问者对网页Pij的访问次数和投票情况来计算网页Pij的PR值：Zijn为访问者对网页Pij的访问次数，因为搜索者总希望找到权威的网站，权威网站里面的内容相对准确，怎样找到权威网站呢，PRin×Zijn表明访问者本身的PR值较高，访问的次数越多，表明网页受关注的程度越高，则网页自然应该排在前面，PRin×Zijn是访问者n对网页PR值计算中的权重，这个权重越大，则访问者n对网页Pij的PR值影响越大，但是我要做的工作是网页的权威性内容的正确性决定网页排名，网页是否权威还要考虑访问者对网页的投票，在这里不同于计算访问者的本身PR值(即访问者在专业领域的学术水平)需要事先获取访问者对网页的投票的被认同度，现在要获取的是访问者对网页的评价，这个与网页内容的被认同有关。PRin×Zijn作为一个权重，影响网页PR值，其起的是正面影响还是负面影响还要看访问者对网页的投票评价如何。[14]

因此设一个系数Hjn，Hjn表示访问者对网页内容的投票评价(访问者n对网页内容的认同度)，Hjn为0到1之间的数，1表示访问者完全认同网页的内容，0表示访问者完全否认网页的内容，Hjn的值越大则表明访问者越赞同网站的内容，当网页没有投票栏或者有投票栏但是访问者没有投票时Hjn取0.5。

访问者对网页Pij的内容的认同度

Hjn = 50 %，网页没有投票栏或者有投票栏但是访问者没有投票时 0 ，访问者没有访问网页j

为了继续计算每个网页的PRij我们必须获取Hjn信息即每个访问者对网页Pij的内容的认同度，在权重PRin×Zijn的基础上再乘以认同度Hjn就可以客观反映网页本身的PR值。因此网页的PR可统一用下式表示：

PRij=?nPRin×Zijn×Hjn (3.7)

对于非分类网页的PR值，可以先将非分类网页分到各个相关领域计算，再取各个相

关领域的PR值的平均值就可以综合反映网页的PR值。

为了继续验证上面算法的正确性，下面继续用上面的简单模型进行计算，首先给Hjn设置数据如下图：

37

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

3.3.2 建立数学模型

图3.6

上图3.6中的数据就是相应的访问者对网页内容的认同度

PRij=?nPRin×Zijn×Hjn (3.7)

PRin×Zijn表示访问者对网页的关注度[15]，这里可以看做一个权重，网页的受关注度高低并不可以反映网页的权威性和正确性，如果大部分访问者对网页的评价很低，就算网页的受关注度越高，它的权威性越低，因为越多的人不认同网页的内容。相反如果大部分访问者对网页的评价很高，网页的受关注度越高，它的权威性越高，因为越多的人认同网页的内容。这说明PRin×Zijn只是一个权重，并不可以决定一个网页的权威性和正确性，而PRin×Zijn×Hjn就可以客观地反映了访问者n对网页Pij的权威性和正确性的贡献，将每个访问者的贡献值相加就可以得到一个网页的PRij，因此PRij=

?nPRin×Zijn×Hjn

38

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

对于非分类网页的PR值计算只需将不同领域计算得的PRij相加除以涉及领域数即可。即：

PRij= (?n,iPRin×Zijn×Hjn)/K (3.8)

K：非分类网页涉及的领域数

根据收敛算法的计算结果PRi(1)> PRi(2)> PRi(3)> PRi(4)，其中PRi(2)与PRi(3)比较接近，两者和PRi(1)相差不大，而PRi(4)比其他三个小很多因此考虑前三者即可，可以知道粗略由PRi(1)PRi(2)和 PRi(3)决定PRij，三者的PR值较大，根据PRij计算公式可以知道网页的PR值主要由三者的评价决定，访问者1的评价为2>1>4,访问者2的评价为3>2,可以看出仅仅由以上两个访问者难以比较4个网页的PR大小，由于访问者3的PR仅次于两者，所以网页的PR大小还要考虑访问者3的评价，访问者3的评价为3>1。根据上面3个访问者的评价结合每个人的PR可以得出结论：网页PR值排名为：3>2>1>4,即Pi(3)> Pi(2)> Pi(1)> Pi(4),如果公式

PRij=

?nPRin×Zijn×Hjn (3.7)

算出的结果和上面的结果相同则可以说明上述的算法是正确的、可行的。

3.3.3 Visual Basic编程验证算法的正确性

为了继续验证算法的正确性，下面继续沿用上面计算的PRin的程序结合图3.6的Hjn 用VB编程和matlab编程计算PRij，上图标示的数据Hn设置情况结合计算出的PRin可以明显看出网页PRij的排名，便于检验计算结果是否正确。

VB编程如下：在上面计算PRin的基础上再添加一小段程序变成以下程序： Private Sub Command1_Click() Dim H(1 To 4, 1 To 4) Dim Pi(1 To 4)

H(1, 1) = 0.2: H(1, 2) = 0.5: H(1, 3) = 0.2: H(1, 4) = 0.6: H(2, 1) = 0.5: H(2, 2) = 0.3: H(2, 3) = 0.5: H(2, 4) = 0.4

H(3, 1) = 0.5: H(3, 2) = 0.9: H(3, 3) = 0.6: H(3, 4) = 0.5: H(4, 1) = 0.1: H(4, 2) = 0.5: H(4, 3) = 0.5: H(4, 4) = 0.3 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)

39

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

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 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 For n = 1 To 4 PRi(n) = PR(n, m)

40

本文来源：https://www.bwwdw.com/article/laz3.html