/*
描述: 小型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 03 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 03 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;
}