本科毕业设计（论文）

外文翻译

谷歌矩阵的若当标准形：

对网页级别计算的潜在贡献

作者：STEFANO SERRA-cAPiZZANO

国籍：意大利

出处：SiAM Journal on Matrix Analysis and Applications 27.2（2005）：305-312。

中文译文：

摘要：我们考虑谷歌用于计算网页级别的网页超链接矩阵，其形式由A(c)= [cP (1-c)E] ^T给出，其中P是行随机矩阵，E是行随机秩1矩阵，cisin;[0,1]。我们确定了A(c)的若当标准形表达式，特别是关于用c表示出了网页级别的合理公式。当c接近或等于1时，使用外推程序可以非常有效地计算网页级别。

关键词： 谷歌矩阵，若当标准形，外推公式

AMS主题分类：65F10,65F15,65Y20

DOi：10.1137 / S08954798044414071

1. 引言：我们将网页看作一个巨大的有向图，其节点是所有网页，其边缘由页面之间的所有链接构成。在下面，deg(i)表示从页面直接链接到达的页面的基数。基础谷歌矩阵P定义如下：如果deg(i)gt; 0并且网页中存在从第i页到某个页面j的链接i;对于其中deg(i)= 0的行i为P_i，j = 1 /deg(i)，我们假设P_i，j = 1 / n，其中n是的大小矩阵，即所有网页的基数。此定义是通用网页用户行为的模型：如果用户正在访问页面i，则概率为1 / deg(i)他将移动到由i链接的页面j之一，如果没有链接，那么用户将只做一个随机选择，均匀分布1 / n。基本网页级别是一个n大小的向量，它可以衡量网络中每个页面的重要性：一个简单的推理表明，基本网页级别是与主要特征值1相关的P的左特征向量（参见[6]，[9]）。由于矩阵P是非负的并且行和等于1，很明显与1相关的右特征向量是e（所有1的向量）并且所有其他特征值的模数最多等于1。因为P是这样的，我们不能保证它的非周期性和它的不可约性：因此1和第二大特征值的模数之间的差距可以是零。这意味着网页级别的计算标准幂方法（见[3]）在矩阵A = P _t中的应用（或者我们特定问题的变化之一）不收敛或非常缓慢收敛。通过考虑模型的变化找到解决方案：给定值cisin;[0,1]，从基本的谷歌矩阵P中我们定义参数化的谷歌矩阵P(c)为cP （1 - c）E，其中E =ev^T且v_igt; 0，||v||₁ = 1.此变化对应以下用户行为：如果用户正在访问第i页，则下一步将进行根据基本谷歌矩阵P描述的规则，使用概率c和可能概率为1-c，根据v描述的规则。通常是一个值，在文献中考虑c为0.85（参见[6]）。对于c lt;1，可以得到PageRank(c)，即左支配特征向量，可以快速计算，因为P(c)（现在有行和1，非负，不可约和非周期）具有第二个特征值，其模数由c [4]支配：因此，收敛到PageRank(c)使得步骤k的误差衰减为c^k。当然，如果c被选择为接近1，则计算变慢，并且如果c = 1则不能保证收敛。在本文中，给定基本谷歌矩阵P的若当标准形，我们以分析方式描述若当标准形。 特别是我们获得了谷歌矩阵P(c)的形式：

PageRank(c) = PageRank R(c)

用R(c)的有理向量函数。由于当c远离1时可以有效地计算PageRank(c)，因此当c接近或等于1时，使用向量外推方法[1]可以让我们快速计算PageRank(c)（见[ 2]了解更多细节）

1. 分析PageRank(c)封闭形式.分析分两步给出：首先我们给出若当标准形和PageRank(c)的理性表达式，假设P是可对角化的;那么我们考虑一般情况。

定理2.1：设P是大小为n的行随机矩阵，设cisin;(0,1)，令E = evt是行随机秩为1的矩阵，其中e为所有的向量，1和v表示概率分布的n大小向量，即v_igt; 0并且||v||₁ = 1.考虑矩阵P(c)= cP (1-c)E并设P是对角阵。如果，，然后有：

此外，以下此结果也适用：

bull;如果P是可还原的并且其图形至少具有，两个不可减少的闭合集，则。

bull;我们有

证明：从假设我们得到，但（行和等于1），P是非负的;因此在 ，和时，有;此外，如果P是可简化的，则，并且其图形通过标准马尔可夫理论可知具有至少两个不可约闭集（参见，例如，[4]）。因此， ，特别是（规范基础的第一个向量）。我们有

则有：

但是v^T e = 1，因为v是假设的概率向量。最后，我们有：

（2.1）

最后一步是对前一个矩阵进行对角化：将R调用为矩阵

（2.2）

并考虑到（2.1），直接计算表明

例如：

最后：

推论2.2 使用定理2.1的表示法，PageRank(c)向量由下式给出

是基本的PageRank向量（即当c =1时）

证明:对于c = 1，由于P(c)= P，因此无需证明PageRank(c) = PageRank。我们取c lt;1。通过定理2.1我们有PageRank(c)是矩阵Z^minus;1 = RX^minus;1的第一行的转置。由于 X^minus;1 = [y₁|y₂|··· |y_n]^T，关于R的结构原理阐述详细可以看式子（2.2）。我们现在考虑P是一般的（因此可能不是可对角化的）的情况：除了表达式R(c)之外，结论是形式上相同的。我们首先观察到，如果lambda;₂ = 1，那么，如[4]中所证明的，P的图形具有至少两个不可约的闭集：因此特征值1的几何多样性也必须至少为2.总结：一般我们有 P = XJX^minus;1，其中

(2.4)

*表示可以是0或1的值。

定理2.3.令P为大小为n的行随机矩阵，令cisin;(0,1)，并且令E = ev^T为行随机秩一个大小为n的矩阵，其中e为所有1的向量且v为n阶的表示概率分布向量，即 v_i gt; 0和||v||₁ = 1.考虑矩阵 P (c) = cP (1 minus; c)E 和令P = XJ(1)X^minus;1有X = [e|x₂|··· |x_n], [X^minus;1]^T = [y₁|y₂|··· |y_n]

和：

（2.5） D = diag(1, c,..., cnminus;1)

*表示可以是0或1的值。然后我们有

P (c) = ZJ(c)Z^minus;1, Z = XR^minus;1

此外，以下情况也适用：

bull;1 ge; |lambda;₂|ge; ··· ge; |lambda;_n|如果P是可简化的并且其图形具有至少两个不可约的闭集，则lambda;₂ = 1。

bull;当R = in e₁w^T , w^T = (0, w₂,..., w_n),

(2.6) ,

(2.7)

证明：从假设我们得到P = Xdiag(lambda;₁, lambda;₂,..., lambda;_n)X^minus;1，但P e = e（P的行和等于1）并且P是非负的：因此 X = [x₁|x_{2 剩余内容已隐藏，支付完成后下载完整资料}

英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[272206]，资料为PDF文档或Word文档，PDF文档可免费转换为Word