PageRank迭代求解方法

╰半夏微凉° 2022-08-26 05:53 215阅读 0赞

## PageRank算法迭代求解第二版程序 ##

/\*  
描述: 小型Web超链图的PageRank算法迭代求解  
作者: xiaocui  
时间: 2008.4.19  
版本: v1.0  
\*/

/\*简单的PageRank算法为 PR(T) = PR(T1)/C(T1)+...+PR(Tn)/C(Tn)),  
最后写成了 P = M \* P, P为n个网页的pagerank值组成的列向量，  
M为马尔可夫转移矩阵，其每列元素表示该网页跳转到其他网页的概率。  
PageRank算法的求解就是求M矩阵特征值为1的特征向量，1是M的最大特  
征值，可以通过幂法进行迭代求解。

本程序是模拟PageRank算法的迭代计算，只用了7个网页，其链接关系图用邻接矩阵  
表示为：  
      1    2  3  4  5  6  7  
  1  0    1  1  1  1  0 1  
  
  2  1    0  0  0  0  0  0

3  1    1  0  0  0  0  0

4  0    1  1  0  1  0  0

5  1    0  1  1  0  1  0

6  1    0  0  0  1  0  0

7  0    0  0  0  1  0  0

转置归一化后对应的马尔可夫转移矩阵为：  
      1     2    3      4       5       6      7  
  1  0     1    0.5    0       0.25    0.5    0  
  
  2  0.2  0    0.5    1/3     0       0      0

3  0.2  0    0      1/3     0.25    0      0

4  0.2  0    0      0       0.25    0      0

5  0.2  0    0      1/3     0       0.5    1

6  0     0    0      0       0.25    0      0  
  
  7  0.2  0    0      0       0       0      0  
\*/  
\#include <iostream>  
\#include <vector>  
\#include <cmath>  
using namespace std;

/\* 计算矩阵和向量的乘积  
输入：arr表示矩阵，vec表示向量  
输出：结果向量  
\*/  
vector<double> arrayVecMul(const vector<vector<double> >& arr, const vector<double>& vec)  
\{  
vector<double> rstVec; //结果向量  
double sum = 0.0;  
for (size\_t i = 0; i < arr.size(); ++i)  
\{  
   sum = 0.0;  
   for (size\_t j = 0; j < arr\[i\].size(); ++j)  
   \{  
    sum += arr\[i\]\[j\] \* vec\[j\];  
   \}  
   rstVec.push\_back(sum);  
\}

return rstVec;  
\}

/\* 向量归1化  
输入：vec表示向量  
输出：归1化的向量vec  
\*/  
void toOne(vector<double>& vec)  
\{  
double sum = 0.0;  
for (size\_t i = 0; i < vec.size(); ++i)  
\{  
   sum += vec\[i\];  
\}  
for (size\_t i = 0; i < vec.size(); ++i)  
\{  
   vec\[i\] /= sum;  
\}  
\}

/\* 返回向量的最大元素(绝对值最大)  
输入：vec为向量  
输出：最大元素值  
\*/  
double getMaxElement(const vector<double>& vec)  
\{  
double max = fabs(vec\[0\]);  
for (size\_t i = 0; i < vec.size(); ++i)  
\{  
   double tmp = fabs(vec\[i\]);  
   if ( tmp > max )  
   \{  
    max = tmp;  
   \}  
\}

return max;  
\}

/\* 判断误差是否满足，误差满足后迭代结束  
输入：向量vecPrior表示前一次的结果，向量vec表示本次结果，e表示误差界  
输出：true表示误差满足，迭代结束；false表示误差不满足  
\*/  
bool isFinish(const vector<double>& vecPrior, const vector<double>& vec, double e)  
\{  
double maxE = 0.0; //表示前后两个向量对应分量的最大误差  
for (size\_t i = 0; i < vecPrior.size(); ++i)  
\{  
   double tmp = fabs(vec\[i\] - vecPrior\[i\]);  
   if ( tmp > maxE )  
   \{  
    maxE = tmp;  
   \}  
\}  
if ( maxE < e )  
\{  
   return true;  
\}

return false;  
\}

int main()  
\{  
//构造马尔可夫转移矩阵  
vector<vector<double> > arr;  
double a1\[7\] = \{0, 1, 0.5, 0, 0.25, 0.5, 0\};  
double a2\[7\] = \{0.2, 0, 0.5, 1.0/3, 0, 0, 0\};  
double a3\[7\] = \{0.2, 0, 0, 1.0/3, 0.25, 0, 0\};  
double a4\[7\] = \{0.2, 0, 0, 0, 0.25, 0, 0\};  
double a5\[7\] = \{0.2, 0, 0, 1.0/3, 0, 0.5, 1\};  
double a6\[7\] = \{0, 0, 0, 0, 0.25, 0, 0\};  
double a7\[7\] = \{0.2, 0, 0, 0, 0, 0, 0\};  
vector<double> row1(a1, a1 + 7);  
vector<double> row2(a2, a2 + 7);  
     vector<double> row3(a3, a3 + 7);  
vector<double> row4(a4, a4 + 7);  
vector<double> row5(a5, a5 + 7);  
vector<double> row6(a6, a6 + 7);  
vector<double> row7(a7, a7 + 7);  
arr.push\_back(row1);  
arr.push\_back(row2);  
arr.push\_back(row3);  
arr.push\_back(row4);  
arr.push\_back(row5);  
arr.push\_back(row6);  
arr.push\_back(row7);

double f\[7\] = \{0, 0.8, 1, 0.3, 0.2, 0.7, 0.4\};  
vector<double> vec(f, f + 7); //初始向量  
double e = 0.000001; //误差界  
int count = 0; //迭代计算次数  
vector<double> rstVec; //特征向量  
double maxValue; //最大特征值

while ( 1 )  
\{  
   count++;  
   rstVec = arrayVecMul(arr, vec);  
   maxValue = getMaxElement(rstVec);  
   for (size\_t i = 0; i < rstVec.size(); ++i)  
   \{  
    vec\[i\] = rstVec\[i\] / maxValue;  
   \}  
    
   if ( isFinish(vec, rstVec, e) )  
   \{  
    break;  
   \}  
   else  
   \{  
    maxValue = getMaxElement(rstVec);  
    for (size\_t i = 0; i < rstVec.size(); ++i)  
    \{  
     vec\[i\] = rstVec\[i\] / maxValue;  
    \}  
   \}  
\}

cout << "总共迭代了: " << count << "次" << endl;  
cout << "最大特征值为: " << maxValue << endl;  
for (size\_t i = 0; i < rstVec.size(); ++i)  
\{  
   cout << rstVec\[i\] << "  ";  
\}  
cout << endl;

cout << "正确性检验： " << endl;  
cout << "矩阵和特征向量的乘积: " << endl;  
rstVec = arrayVecMul(arr, rstVec);  
for (size\_t i = 0; i < rstVec.size(); ++i)  
\{  
   cout << rstVec\[i\] << "  ";  
\}  
cout << endl;

cout << "特征值和特征向量的乘积: " << endl;  
for (size\_t i = 0; i < rstVec.size(); ++i)  
\{  
   rstVec\[i\] = maxValue \* rstVec\[i\];  
\}

return 0;  
\}