利用MATLAB:
A=[0 0 0 0.5;1/3 0 0 0;1/3 0.5 0 0.5;1/3 0.5 0 0];
[V,D]=eig(A);
diag(D)
输出的四个特征值的模都小于1，且1不是A的特征值。此时，就无法利用特征值1对应的特征向量对该网络的网页进行排名。
（2）存在无法确定排名的情况.
考察由图3所示的小型网络 图3
该网络由两个互不相连的子网络构成，其对应的链接矩阵A为：本文来自辣%文,论'文.网，
毕业论文 www.751com.cn
利用MATLAB计算可得这个矩阵有1和－1两个二重特征根，还有一个单重特征根0，特征根1对应的两个线性无关的归一化特征向量为：
， 。
显然，利用上述特征向量无法对网页进行排名.
5.2改进的PageRank算法
若矩阵A中存在某列全为0，则矩阵M的每个元素都大于零，所以M是一个正的方阵，此时M存在模最大的唯一正特征根，且有对应的唯一归一化特征向量. 我们可采用此特征向量对网络进行排名。
以图2所示的小型网络为例， ，通常取p=0.85，那么用MATLAB，易得
(16)
而M的模最大的正特征值 ，对应的归一化特征向量为
这样我们得到
。
对照前面解决这个问题的方法，可见用M代替A得到的排名结果保持不变。
回到图3所示的小型网络，n=5，p=0.85，利用MATLAB：
p=0.85;
A=[0 0 0 0 0;0.5 0 1 0 0;0.5 1 0 0 0;0 0 0 0 1;0 0 0 1 0];
S=ones(5,5)/5;
M=p*A+(1-p)*S;
[V,D]=eig(M);
diag(D)
可以得到M的最大正特征根为1，进而可得其对应的归一化特征向量为
，
利用该特征向量就可以对不同子网络中的网页进行排名. 其对应的网页排名为：
。
5.3 PageRank算法-幂法
值得注意的是，前面的作为例子的小型网络的规模微小，用数学软件直接求解矩阵方程x=Ax或求A的特征根和特征向量都无困难. 当问题的规模很大，甚至A的阶数可能达到上万甚至上亿时，就必须寻找合适的数值计算方法. 下面我们介绍用于计算矩阵特征值的幂迭代算法。
再次考察图2所示的小型网络，相应的矩阵M如(16)式所示。那么给定初始向量 ，利用MATLAB编程:
M=[0.0375,0.0375,0.0375,0.4625;0.32083,0.0375,0.0375,0.0375;0.32083,0.4625,0.0375,0.4625;0.32083,0.4625,0.0375,0.0375];
x(:,1)=[0,0,0,1]';
y(:,1)=[0,0,0,1]';
for k=2:20
y(:,k)=M*x(:,k-1);
x(:,k)=y(:,k)/norm(y(:,k),1);
end
经计算得到幂法的迭代20次的序列如下
上一页 [1] [2] [3] [4] [5] [6] [7] [8] 下一页
网页排名PageRank算法初探+数学建模与求解 第6页下载如图片无法显示或论文不完整，请联系qq752018766
