网页排名PageRank算法初探+数学建模与求解 第3页

1.4.3 PageRank算法—幂法
    假设矩阵A的特征值满足条件 ，其中 是特征方程的实根，相应的特征向量 可以取成实向量，对于任意给定的非零初始向量 ，迭代格式
                                                      （6）
称为计算矩阵特征值的幂法. 假设A有n个线性无关的特征向量  ，则初值 可以用它们线性表示，即
 
从而幂法的迭代由下式给出
            
                              （7）
若对所有的 ，均有 . 所以只要 ，当k足够大时，由(6）式可得
                       ,                               （8）
                                                      （9）
即有
                                                      （10）
而 ，故有
                                                             (11)
这意味着， 最终会趋于 . 但是，直接采用幂法往往会导致迭代序列趋向于无穷大（而 的绝对值小于1时则会趋于零）.故在每次迭代是应当对 进行归一化处理，所以上述算法可以改写为
                                                           （12）
,       其中                              （13）

2 问题提出
今天，如果你打算了解某种信息，多半会利用互联网.在google首页搜索栏输入一些关键词，跟此有关的网页会很快迅速显示出来，也许只用不到一秒钟.而且这些网页会依照某些次序排列，通常是越靠前的越重要(也许是关注的人越多).那么google的搜索引擎是如何做到这一点的呢？通过调查发现Google是采用了一种叫做PageRank的算法来给网页进行排名的。从最初的简化的PageRank算法到后来为了解决一下特殊情况下无法计算出网页排名而改进的PageRank算法，再到之后的解决特征值收敛问题的幂迭代法。
针对以上问题，我采用了线性代数的方法。首先对于简化的PageRank算法，对于一个例子进行了解读并对其进行改动发现在某些特殊情况下无法求得特征根的情况，从而有了改进的PageRank算法。最后通过改进的PageRank算法和幂迭代法对与哈佛大学主页有关的500个网页的排名情况进行了具体的分析。

3 数学基本概念的介绍
3.1基本数学概念的介绍
3.1.1有向图的定义
数学中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。
记这些点为 ，而它们的连线用 表示，记为 ，那么一个图 是指一个二元组 ，其中：
1)  是非空有限集，称为顶点集，其中元素称为图 的顶点。
2） 是顶点集 中的无序或有序的元素对 组成的集合，称为边集,其中的元素称为边. 若图G中的边均为无序对，称G为无向图，若图G中的边均为有序对，称G为有向图。

上一页  [1] [2] [3] [4] [5] [6] [7] [8] 下一页

网页排名PageRank算法初探+数学建模与求解 第3页下载如图片无法显示或论文不完整，请联系qq752018766