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();
}
}