Weighted PageRank算法实现

PageRank里面的边是没有权重的，就是说每一个点对另一个点的影响都是一样的，但是会有一些情况，一个点对另一个点的影响大小不一致，这就需 要用到了给边加权重的方法，这就有了Weighted PageRank这个算法。WPR算法的理论资料相对于PR算法会少很多的，可以在Google scholar 上找到这篇论文 Weighted PageRank Algorithm . ，还可以到一些学校的网站找到这个算法的讲解，就差不多了。

我的实现方法是，先构建一个没有权重的关系矩阵，然后根据已经获得的矩阵，和WPR的权重出度和入读的方法计算出权重矩阵，然后有WPR的算法实现。实现的只是一个简单的实例，具体到实际的数据时还需要做修改。

代码如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class WeightPageRank {
       private static int count;            //矩阵的维数
       static int[][] matrix;        //二维数组，构造关系矩阵
       static double[][] weightMatrix; //二维数组，边的权重矩阵
       static double[] outLinks;      //每个点的出链接数
       static double[] inLinks;      //每个点的入链接数
       static double[] pageRank;   //PageRank值
       static double d = 0.85;        //抑制因素，设为0.85
       boolean flag = true;        //控制循环，收敛后则为false，停止计算
       
       /**
        * 构造函数
        * @param count  //矩阵的维数
        */
       public WeightPageRank(int count)
       {
           this.count = count;
           pageRank = new double[count];
           for(int i = 0; i < count; i++)
               pageRank[i] = 1/count;           //将每个页面的初始PR值设为1
       }
       
       
       /**
        * 初始化矩阵
        * @throws IOException
        */
       public void InitialMatrix() throws IOException
       {
           matrix = new int[count][count];               //关系矩阵
           File file = new File("graph.txt"); //读取文件中的关系信息
           FileReader fr;
           BufferedReader br;
           if(file.exists())            //文件存在
           {
                fr = new FileReader(file);
                br = new BufferedReader(fr);  //读取文件信息
                int i;
                while(br.ready())
                {
                    String[] words = new String[20];
                    String[] fromNodes = new String[20];  //起始点
                    String[] toNodes = new String[20];    //指向的点
                    words = br.readLine().split("-");
                    fromNodes[0] = words[0];
                    toNodes = words[1].split(",");
                    int row = 0;
                    for(i = 0;i < toNodes.length;i++)
                    {
                        int column = 0;
                        //System.out.println(fromNodes[0]+toNodes[i]);
                        switch(fromNodes[0].charAt(0))
                        {
                        case 'A': row = 0;break;
                        case 'B': row = 1;break;
                        case 'C': row = 2;break;
                        case 'D': row = 3;break;
                        case 'E': row = 4;break;
                        case 'F': row = 5;break;
                        case 'G': row = 6;break;
                        case 'H': row = 7;break;
                        case 'I': row = 8;break;
                        default : row = 0;break;
                        }
                        switch(toNodes[i].charAt(0))
                        {
                        case 'A': column = 0;break;
                        case 'B': column = 1;break;
                        case 'C': column = 2;break;
                        case 'D': column = 3;break;
                        case 'E': column = 4;break;
                        case 'F': column = 5;break;
                        case 'G': column = 6;break;
                        case 'H': column = 7;break;
                        case 'I': column = 8;break;
                        default : column = 0;break;
                        }  
                        matrix[row][column] = 1;      //将有边的两点赋值为1
                        //System.out.println(matrix[row][column]);
                    }
                   
                }
           }
           else            //文件存在
           {
               System.out.println("文件不存在!");
               System.exit(0);
           }
       }
       
       /**
        * 计算每个点的入链接数
        * 即，计算矩阵中每一列的和
        */
       public void inLinks()
       {
           inLinks = new double[count];
           for(int i = 0;i < count; i++)
           {
               for(int j = 0; j < count; j++)
               {
                   inLinks[i] += matrix[j][i];
               }
               //System.out.println(inLinks[i]);
           }
       }
       /**
        *
        * 计算每一个点的链出数
        * 即，计算矩阵中的每一行的和
        */
       public void outLinks()
       {
           outLinks = new double[count];
           for(int i = 0;i < count; i++)
           {
               for(int j = 0; j < count; j++)
               {
                   outLinks[i] += matrix[i][j];
               }
               //System.out.println(outLinks[i]);
           }
       }
       
       /**
        * 构建权重矩阵，根据关系矩阵，有边则计算该边的权重
        * 由入度权重和出度权重相乘得到
        * 入度权重计算方法为：(i,j)边的入度权重为i指向的边j的入度除以i指向的所有点的入度和
        * 出度权重计算方法为：(i,j)边的出度权重为i指向的边j的出度除以i指向的所有点的出度和
        */
       public void weightMatrix()
       {
           weightMatrix = new double[count][count];
           int[] sumIn = new int[count];
           int[] sumOut = new int[count];
           for(int i = 0;i < count;i++)
           {
               for(int j = 0; j < count; j++)
               {
                   if(matrix[i][j] == 1)               //有边，则统计起始点的所指向的点的入度和出度和
                   {
                       sumIn[i] += inLinks[j];         //统计点i指向的所有点的入度和
                       sumOut[i] += outLinks[j];       //统计点i指向的所有点的出度和
                   }
               }
           }
           
           //构建权重矩阵
           for(int i = 0;i < count;i++)
           {
               for(int j = 0; j < count; j++)
               {
                   if(matrix[i][j] == 1)               //有边，则计算该边的权重
                   {
                       weightMatrix[i][j] = (inLinks[j]/sumIn[i])*(outLinks[j]/sumOut[i]);
                       //System.out.println(weightMatrix[i][j]);
                   }
               }
           }
           
           
       }
       /**
        * 计算每一个页面PR值
        */
       public double[] CalculatePR(double[] pagerank)
       {
           double totle = 0;
           double pageRank1 = pagerank[0];           //第一个点前一次的PR值
           double pageRank2;                         //第一个点下一次的PR值，两个值用于判断是否收敛
           for(int j = 0; j < count; j++)
           {
               double sum = 0;
               for(int k = 0; k < count; k++)
               {
                   sum += weightMatrix[j][k]*pageRank[k]*matrix[k][j]/outLinks[k]; //计算各个PR总和
               }
               pageRank[j] = (1-d)/count + d*sum;                  //PR的计算
               totle += pageRank[j];
               System.out.print(pageRank[j]+":");
           }
           pageRank2 = pageRank[0];                        //下一次的PR值
           if(Math.abs(pageRank1-pageRank2) < Math.pow(10, -10))//收敛条件，两次的PR值的差的绝对值小于0.0000000001
               flag = false;
           else
               flag = true;
           
           //归一化处理
           for(int i = 0; i < count; i++)
           {
               pageRank[i] = pageRank[i]/totle;
           }
           return pageRank;
       }
       
       /**
        *
        * 迭代计算直到收敛
        *
        */
       public void CalculateResult()
       {
           double[] pageRanks = pageRank;
           int i = 0;
           while(flag)
           {
               System.out.println("第"+(i+1)+"轮迭代:");
               pageRanks = CalculatePR(pageRanks);           //循环调用计算PR值
               System.out.println();
               i++;
           }
           
           for(int j = 0; j < count; j++)
           {
               System.out.println("最终的结果为：");
               System.out.println((j+1)+"-----"+pageRanks[j]);
           }
               
       }
       
       public static void main(String[] args) throws IOException
       {
           WeightPageRank pg = new WeightPageRank(8);   //n维矩阵，有n个点
           pg.InitialMatrix();
           pg.inLinks();
           pg.outLinks();
           pg.weightMatrix();
           for(int i = 0; i < count;i++)
           {
               for(int j = 0; j < count; j++)
               {
                   System.out.print(matrix[i][j]+"  ");
               }
               System.out.println();
           }
           
           for(int i = 0; i < count;i++)
           {
               for(int j = 0; j < count; j++)
               {
                   System.out.print(weightMatrix[i][j]+"  ");
               }
               System.out.println();
           }
           
           pg.CalculateResult();
       }

}