实验九 网站排名问题

实验九 网站排名问题

实验九 网站排名问题

一、问题背景与实验目的
　　几乎每个人都有使用Google搜索引擎进行网上搜索的体验．我们在Google搜索引擎中输入一些关键词后，Google会很快地找到所有与搜索关键词匹配的网页，并给出所有的网站排名情况（一般认为排在第一个的最重要，以下类推）．到目前为止，世界上有近千万个网站，十多亿个网页，难道Google搜索引擎真的如此神奇，能够在几秒、几十秒的时间内扫遍世界上所有的网站（网页）吗？答案是否定的．事实上，Google网站是基于自己的大型数据库系统的网站，它定期地（比如每个月一次）对世界上的所有网站进行大搜索，并将结果保存在自己的数据库中．我们通过Google搜索引擎进行网上搜索，实际上是在Google网站的数据库里进行搜索，因此，所用时间一般不会太长．
　　要验证这一点并不难．假如你是一个"网管"，你可以控制一个网站，比如你可以很快地向网站发布信息（内含某些特殊的关键词）．此后，你迅速利用Google搜索引擎搜索你刚才的关键词，一般情况下是找不到的．
　　我们关心的重点是：与某个关键词相关的网站可能有几个、几十、......、最多可能有几百万个，Google是如何给出网站排名情况的呢？本实验将要介绍的PageRank(网页级别)算法就是Google用于评测一个网页"重要性"的一种方法．虽然现在不断地有改善的排名算法，但其本质上与PageRank(网页级别)算法十分接近．相信如能彻底理解PageRank算法，对于理解、设计其它算法将是十分有益的．本实验将主要介绍该算法．
　　PageRank算法用到的数学知识看上去并不十分高深，但十分实用．主要用到线性代数的一些知识，包括：正矩阵性质、特征向量与特征值关系、幂迭代方法（Power Iteration）和Gauss-Seidel迭代方法等．
　　实验中的一些程序看起来是小题大作，比如对已知的6阶方阵，用Matlab求解代数方程不是十分困难的事．但如若方阵的阶数是60、600、6000、60000，你的方法将可能彻底崩溃．因此，认真学习本实验的一些计算方法是有意义的．通过实践对比，你会发现这些算法的效率是相当高的，特别适合大规模计算．事实上，Google采用的是大规模的并行计算技术，以求解高达上亿阶的代数方程．
　　
　　下面我们先简要介绍一下什么是PageRank算法．
　　
1． 什么是PageRank(网页级别)？
　　PageRank(网页级别)是Google用于评测一个网页"重要性"的一种方法．在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具"重要性"的网页在搜索结果中令网站排名获得提升，从而提高搜索结果的相关性