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

对于复杂的PageRank算法，考虑到PageRank sink和PageRank减损，引入
衰减系数d，表示可以从当前网页以概率(1-d)/n跳往任何网页。引入d后的
PageRank算法表示为 PR(T) = (PR(T1)*(1-d)/n+PR(T2)*(1-d)/n+....+PR(Tn)*(1-d)/n)
                           +d*((PR(T1)/C(T1)+...+PR(Tn)/C(Tn))
写成向量相乘的式子即为PR(T) = ((1-d)/n+1/C(T1), (1-d)/n+1/C(T2),...(1-d)/n+1/C(Tn)) * (PR(T1), PR(T2), ...PR(Tn))
可见最后的马尔可夫转移矩阵的元素变为简单的马尔可夫转移矩阵元素： 乘以d+(1-d)/n。

本程序是模拟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

复杂马尔可夫转移矩阵元素为简单马尔可夫转移矩阵元素*d+(1-d)/n
*/
＃i nclude <iostream>
＃i nclude <vector>
＃i nclude <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()
{
const int N = 7; //7个网页
const double d = 0.85; //衰减系数，一般取值为0.85
//构造马尔可夫转移矩阵
vector<vector<double> > arr;
double a1[N] = {0, 1, 0.5, 0, 0.25, 0.5, 0};
double a2[N] = {0.2, 0, 0.5, 1.0/3, 0, 0, 0};
double a3[N] = {0.2, 0, 0, 1.0/3, 0.25, 0, 0};
double a4[N] = {0.2, 0, 0, 0, 0.25, 0, 0};
double a5[N] = {0.2, 0, 0, 1.0/3, 0, 0.5, 1};
double a6[N] = {0, 0, 0, 0, 0.25, 0, 0};
double a7[N] = {0.2, 0, 0, 0, 0, 0, 0};
vector<double> row1(a1, a1 + N);
vector<double> row2(a2, a2 + N);
    vector<double> row3(a3, a3 + N);
vector<double> row4(a4, a4 + N);
vector<double> row5(a5, a5 + N);
vector<double> row6(a6, a6 + N);
vector<double> row7(a7, a7 + N);
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);

//马尔可夫转移矩阵元素改变
for (size_t i = 0; i < N; ++i)
{
   for (size_t j = 0; j < N; ++j)
   {
    arr[i][j] = arr[i][j] * d + (1-d) / N;
   }
}

double f[N] = {0, 0.8, 1, 0.3, 0.2, 0.7, 0.4};
//double f[N] = {1, 0, 0, 0, 0, 0, 0}; 初始向量可以设置不同，最后收敛结果是相同的，迭代次数可能稍微有所不同
vector<double> vec(f, f + N); //初始向量
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;
}

转自：http://hi.baidu.com/cuifenghui/blog/item/658c4d54d126fc51564e00ce.html