浅谈PageRank的matlab实现

   越来越发现自己学习太不深入了，什么都只懂点皮毛，对于别人的思想没有理解透彻，看来学习还是要深入的，别人的东西要完全理解才能变成自己的。最近开始研究机器学习的算法，今天心血来潮看了下PageRank,思想还是比较简单的，可是要把思想完全理解并用算法实现，对于我这个菜鸟还是花了点时间的。

1.PageRank思想简介

   互联网中的页面是以页面的PageRank来判断其重要性的，值越大越体现其重要性。而页面之间是相互联系的，一个页面可能被多个页面链接，一个页面也可能指向多个页面，从而形成了一个有向图，页面表示有向图的顶点，有向边表示链接，w(i,j)=1表示页面i存在指向页面j的超链接，否则w(i,j)=0。如果页面A存在指向其他页面的超链接，就将A的PageRank的份额平均地分给其所指向的所有页面，一次类推。虽然PageRank会一直传递，但总的来说PageRank的计算是收敛的，下面给出其迭代公式（1-1）：

   PRn(A)=(1-d)+d*（∑PRn-1(Ti)/C(Ti)）（1-1）（页面的初始PageRank均设为1）

    %PRn(A)表示页面A的n次迭代后的PageRank,PRn-1(Ti) 表示页面Ti的n-1的PageRank。

    %C(Ti)表示页面Ti的链接数。

    %d表示阻尼系数（0

算法思想来源 http://wenku.baidu.com/view/e226710e52ea551810a6873d.html

2.PageRank算法描述

   实际应用中可以采用幂法来计算PageRank，假如总共有m个页面，计算如（1-2）所示：

   r=A*x（1-2）其中A=d*P+（1-d)*(e*e'/m)

   %r表示当前迭代后的PageRank，它是一个m行的列向量,x是所有页面的PageRank初始值。

   %P由有向图的邻接矩阵变化而来，P'为邻接矩阵的每个元素除以每行元素之和得到。

   %e是m行的元素都为1的列向量。tyuuyuyfuu

   幂法计算过程如下：

   x<--任意m行列向量;

   r=A*x;

   if(||r-x||

      return r；%r为最终的PageRank

    else

      x=r;goto 2；

3.PageRank算法的maltab实现代码

   %pagerank
    P1=[0 1 10;0 0 0 1; 1 0 0 0;1 1 1 0];%链接的有向图的邻接矩阵表示

   P=[];
   [n,n]=size(P1);%n表示页面数
    fori=1:n
       P=[P;P1(i,:)/sum(P1(i,:))];%将M1的数据除以每行数据之和
    end
   d=0.5;%阻尼系数
   sigma=0.0001;%收敛阈值
   e=ones(n,1);
   A=d*P'+(1-d)*((e*e')/n);
   %x=ones(n,1);
    x=rand(n,1)%页面的pagerank初始值
   r=A*x;%pagerank的计算公式
   while(norm(r-x)>=sigma);%判断是否收敛
       x=r;
      r=A*x;
    end
    r%收敛之后得到最后的pagerank，并输出

输出结果：

   x =

   0.7431             
    0.3922
    0.6555
    0.1712
   r =

   0.5568
    0.4640
    0.4640
    0.4773
另一组结果如下：

   x =

   0.7060
    0.0318
    0.2769
    0.0462

   r =

   0.3011
    0.2509
    0.2509
    0.2581

   通过结果发现页面的重要性与PageRank的初始值无关，虽然当x不同时，得到的r的值也不同，但是页面的重要性排序保持不变。

4.总结

   在理解PageRank算法时，对于其中的数学公式我进行了分析，明白了r=A*x的意义，也明白了为什么A的取值是那样的。下面的将自己的理解介绍如下：

   r=A*x=d*P*x+(1-d)*(e*e'/m)*x  (1)

    PRn(A)=(1-d)+d*（∑PRn-1(Ti)/C(Ti)） (2)

   P1表示有向图的邻接矩阵，P1的第i行中的非零元素表示页面i中链接页面，第j列中的非零元素表示指向页面j的页面，将P1的每个元素除以每行元素之和转置得到P，P的第i行元素表示的就是指向页面i其他页面给页面i的PageRank份额1/C(Ti)。用矩阵表示就是d*P*x，结果也就是（2）的后部分值。而（1）中的后部分表示的是每个页面分出d份额的PageRank之后的PageRank，为了表示成矩阵形式才有了(e*e')/m的表达，这一部分的矩阵表示也就是（2）中的1-d。

   还有一个论文(http://www.cnblogs.com/FengYan/archive/2011/11/12/2246461.html)介绍PageRank,主要思想都差不多，上面的思想用到了阻尼系数d,就相当于这个论文中的C，而论文中的逃脱因子E（E(i)表示第i个网页的逃脱因子）是为了解决Ranksink，我觉得类似与上面的（1-d)*(e*e'/m)*x，对于这一点比较我不是很确定。

   总的来说，对于PageRank还算进行了比较深入的了解。对于海量页面数的相关处理是实际问题的难点，由于我对于分布式处理几乎是0基础，所以还有待好好学习。