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