个页面的得分来源于其他页面对这个页面的链接，如图页面的得分来源于。前链页面得到另个页面的链接，则是的前链，对于结点而言，前链数为的出度数。如图有为的前链,的出度为。背链页面给予另个页面的链接，则是的背链，对于结点而言，背链数为的入度数。如图有为的背链。悬点不含出度的页面结点，如图有为悬点。的基本模型如果我们把整个因特网络看作个大型的拓扑结构图，网页页面看作节点，页面之间的超链接看作有向边，于是就形成的了个巨大的有向图。如何进行网页等级排序，最初的两个创始人拉里佩奇和谢尔盖布林把这个问题转化为二维矩阵相乘的问题，并且用迭代的方法解决。他们提出的模型用于具有超链结构的网络的页面排序。设,,边表示网页存在的超链接，考虑在有向图上随机游走的马可夫链，个用户在时刻访问了页面。在下时刻该用户通过随机选择上的个超链接，访问到了的个指向的页面，其中。另方面，在时刻，访问者在的机率是。转移概率矩阵由的链接情况定义，即当存在超链接从网页链接到的时候，其余的，即为此马可夫链的平稳分布。设页面的出度记为，则矩阵用于描述有向图中页面与之间的传输，并且有,于是构造了个以转移概率矩阵为特征的马可夫链。由马可夫链遍历定理,只有当转移矩阵是非周期不可约的情况下才有唯的平稳分布。此非周期不可约条件保证了稳定向量存在，其值与初始值的选取无关。通过计算该马可夫链的稳定向量得到值值，并且收敛速度取决于矩阵的第二特征值的大小。图理想图图存在悬点图存在子图根据转移矩阵的定义，从上图可得到,,,,有从上图可得到,,,从上图可得到,,,若矩阵为式的形式，我们发现有特征值,事实上取,,则有。定义个稀疏矩阵称为列随机方矩阵，如果该矩阵中所有的元素均为非负的，且每列的总和均为。不包含悬点的网络结构图得到的转移概率矩阵的转置是列随机矩阵，我们只需要证明下面的命题。命题每个列随机方阵都有特征值。证明设是列随机矩阵，为全的维列向量。则对有,所以是的特征值，因此也是的特征值。下面我们用来表示列随机矩阵的特征值为的特征向量空间。以下均表示由网络结构图得到的转移概率矩阵的转置。同时将会发现，如果对进行必要的修正见节后，将满足马可夫链遍历定理和列随机性，此时必存在对应于主特征值的稳定特征向量，此主特征向量即可作为向量。定理定理设，则的每个特征值必属于下述个圆盘之中,证明设为的任意个特征值，为对应的特征向量，即记,及，,所以从式的第个方程以及，有,这说明属于复平面上以为圆心为半径的个圆盘。定理的证明，不仅指出了的每个特征值必属于的个圆盘中，而且指出，若个特征向量的第个分量最大，则对应的特征值定属于第个圆盘中。更重要的点，可以发现列随机矩阵的特征值均不大于，所以列随机矩阵的特征值可以表示为,其中,存在的问题由于网络的复杂性，导致从些网络结构图中得到的转移矩阵得不到个稳定的特征向量。下面主要讨论两种情形存在悬点得到的主特征向量不唯。悬点如果个网络中出现悬点，这种情况也是很常见的，如图将导致转移矩阵的列或几列全。此时矩阵是列子随机的，也就是的各列元素之和小于或等于。在这种情形下，必然会有所有的特征值小于或等于由定理得。可是，在存在悬点的网络结构中，我们仍然可以用同样的方式来处理排名问题。相应的列子随机阵必定有个非负的特征值满足,其相应的特征向量是非负的称为特征向量，此特征向量符合页面排序的要求。主特征向量空间不是维的我们希望矩阵的主特征向量空间是维的，这样就可以标准化为唯的所需排名得分向量满足。但并不定能满足这个要求，如上图得到的矩阵,是二维的，其中可行的基向量为,,但与的任意线性组合均属于,例如,,，可见不能明确的得到个稳定的向量。当然这种情形并非偶然，如果个网络结构图是非连通图，即由些子连通图,构成，则有。不访设图对应于矩阵,子图对应于子矩阵，得到如下转移矩阵设总页面数为，对于矩阵中的每个的子矩阵是列随机的，因此存在个向量,。很容易得到组线性无关的特征向量,,如下，，满足可知,又线性无关，所以的维数至少为。所以不能得到个确定的向量,。对上述问题的修正为了避免上述的两个问题，需要对原先定义的矩阵做些修改，以满足向量的唯性。对出现悬点的修正如果网络结构图中出现悬点，则的些列是全的，使得转移矩阵不满足列随机。对这个问题有几种修正方法，最常用的是用另个矩阵代替。设概率向量,，为总页面数，满足且向量,满足为悬点其他，有。其中附加的矩阵是可行的，如果个用户搜索到了为悬点的网页，此时已经不存在其他页面的超链接，则假定用户以概率向量来跳转到其他页面。般可设,即以相同的概率跳转。可知矩阵是列随机的，因此有特征值为的向量。又由定理可知，的特征值均不大于。对的修正如果图又出现多个子图，则矩阵可约，即矩阵特征值为的特征向量不是维的。中给出了这种情形的修正，此时被另矩阵代替,其中阻尼因子,，在中常取，为概率向量同上，又称为个性化向量，又可表示从子链接图跳到另子链接图的概率。此时矩阵非负不可约，列随机且存在向量。因为同时我们发现为完全稠密矩阵。定理修正矩阵,的第二特征值定理若矩阵具有至少个不可约的子集，则修正矩阵的第二特征值为以上两个定理的证明可参见。对问题的求解方法在些工程物理问题中，通常只需要求出矩阵的按模最大的特征值称为的主特征值和相应的特征向量，对于解这种特征值问题，应用幂法是合适的。幂法幂法是种计算矩阵主特征值矩阵按模最大的特征值及对应特征向量的数值迭代方法，它最大的节验证了基于链接的页面等级排序的合理性，下面通过个现实的网络来测试外推法的收敛加速效果。测试数据来源于。这个数据库包含个网页和个超链接，相关的链接情况如下图。图复杂网络的链接图为了体现出第节中提供的外推法的效果，取阻尼因子以降低收敛速率，使得外推法的作用更为明显。基于图的现实网络，图给出了这种情形下的幂法与外推法在求其主特征值时的收敛情况。从图中可以看出幂法与外推法在迭代数次后均变得很平稳，其主特征值序列均收敛于。以误差容限为时，幂法迭代次后符合要求，外推法迭代次后符合要求。图幂法与外推法的主特征值变化曲线同时为了更好的反映外推法对于阻尼因子的不同取值的加速效果，根据上面的伪代码，在，,内存,环境上实现,程序参见附录。表给出了此现实网络的的幂法与外推法迭代次数与运行时间。表幂法与外推法的收敛测试表方法方法主特征值迭代次数运行时间秒主特征值迭代次数运行时间秒图直观地反映了幂法与外推法在应用中阻尼因子与迭代次数的关系比较。可以看出在计算大型网络的等级排序中外推法在收敛加速中有优异的表现。当阻尼因子取值较小时，加速不明显但仍然比传统的幂法收敛的快当阻尼因子接近时，有明显地加速效果迭代次数不超过。图幂法与外推法的迭代曲线结语与展望可以说是当今最成功的搜索引擎之，而国内对的研究文章较少，对其核心技术进行深入的剖析对于搜索引擎研究开发具有极大的借鉴作用。作为商业的搜索引擎，其最核心的技术细节是保密的，文中主要参考资料多为商业化之前设计者公开发表的学术论文，因此在很大程度上增加了对这技术介绍的难度。但是其排序算法的机理并没有本质的变化，技术仍然具有研究的价值。网页排序是项复杂的计算，其本质就是求个大型矩阵的主特征值最大特征值对应的特征向量，而传统的幂法是针对此类问题求法中最有效的种数值方法，由于网络的复杂性，本文通过对转移矩阵的分析和修正，同时利用网络结构中的这种稀疏性，将幂法作用于矩阵完全稠密转化为由向量矩阵乘积形式作用于大型稀疏矩阵实现，在此过程中无需构造并存储修正矩阵和，极大的减少了存储空间。由于矩阵是极为稀疏的，每行中非零元素平均不超过个同时有很多全零行,使得幂法的收敛速度很快。在参考文献，通过最小二乘法对整体进行外推计算得到的向量再次利用于原迭代中，而本文中给出的外推法仅仅检测原迭代得到的向量序列，并将此序列外推成个新的更快收敛的序列，同时考察这个新序列的终止条件。与不同的是并不将新的序列运用到原迭代中。当然幂法中收敛速度除了和特征值有关，还与开始的初始状态有关，所以可以考虑优化初始状态使其更快地收敛。对于大型稀疏阵也可以做定的矩阵的初等变换，使悬点下沉即全零行下沉，再利用矩阵分块的性质可以减少存储空间同时加速运算速度，具体的理论可以参考。当前有些网站制作者通过站点链接和网站地图等来提高站内的的反馈值。那么会不会对这样的站点内部链接投票值打折呢而这样做会不会影响这种基于链接的等级排序计算方法因为这本身偏偏正是工作的最基本的机理，所以有人认为在排序算法中的作用已经下降,可对于超过亿的页面的偌大网络链接图，人为影响又能多大呢剖析技术也并非我们的最终目的，关键在于通过对排名算法的深入了解，以提出新的网络搜索引擎排名机制以及研究并运用些新的运算加速算法。网络变得越来越庞杂，的搜索效果也并非完美同时面临同行的竞争，排序算法的优化还有很长的路要走。参考文献