PageRank的java实现

一个网络(有向带权图)中节点u的PageRank的计算公式：

PR(u)表示节点u的PageRank值，d为衰减因子(damping factor)或阻尼系数,一般取d=0.85,N为网络中的节点总数，nb(u)表示节点u的所有邻居节点的集合，d(v)表示节点v的出度(如果是无向图，就是度)，w(u,v)表示节点v的边<u,v>所占的权重(如果对于无权图或者认为每条边的权重都一样，那么w(u,v)=1),PR(v)表示节点v的PageRank值。

由此可以看出要算出节点u的PR值需要先知道它的每个邻居节点的PR值，似乎是个递归的过程。其实初始状态下，可以给每个节点的PR值都赋值为一个任意正数，例如1，然后通过上述公式不断迭代计算更新每个节点的PR值，数学证明，最终每个节点的PR值都会收敛到一个稳定的PR值（初值PR不同，最终的PR值也不同，但最后各节点之间PR的大小排名不因初值而改变）。编程时如何确定某个节点u的PR值已经收敛？如果这次的PR值与上次的PR值相差很小的时候就可以认为收敛了。很小是多小？越小越好，但不要太小，免得迭代次数太多浪费时间，可取10的-4或-5次方。

PageRank的数学原理的详细说明，可参考：

深入浅出PageRank算法

PageRank on undirected and weighted graph

《集体智慧编程》上的例子：

Java实现代码：

Program.java:

 package dd.lt;

 import dd.lt.entity.Node;

 public class Program

 {

     //计算每个节点的PageRank值

     public static void CalcPageRank(ArrayList<Node> graph)

     {

         double distance = 0.00001;

         double d = 0.85;// damping factor

         double common = (1 - d) / graph.size();

         while (true)

         {

             for (Node n : graph)

             {

                 double sum = 0.0;

                 for (int nodeId : n.getNeighbors())

                 {

                     Node nb = getNodeById(nodeId,graph);

                     sum += nb.getPR() / nb.getDegree();

                 }

                 double newPR = common + d * sum;

                 //如果尚未收敛，赋新值，否则结束迭代

                 if (Math.abs(n.getPR() - newPR) > distance)

                     n.setPR(newPR);

                 else

                     return;

             }

         }

     }

     public static Node getNodeById(int nodeId,ArrayList<Node> graph)

     {

         for(Node n:graph)

         {

             if (n.nodeId==nodeId)

                 return n;

         }

         return null;

     }

     public static ArrayList<Node> buildGraph()

     {

         ArrayList<Node> graph = new ArrayList<Node>();//图以节点集合形式来表示

         //加载数据，组装好图结构

         ....

         return graph;

     }

     public static void main(String[] args)

     {

         ArrayList<Node> graph = buildGraph();

         CalcPageRank(graph);

         for(Node n:graph)

         {

             System.out.println("PageRank of %d is %.2f",n.nodeId,n.getPR());

         }

     }

 }

Node.java:

 package dd.lt.entity;

 import java.util.ArrayList;

 public class Node implements Comparable<Node>

 {

     public int nodeId;

     private ArrayList<Integer> neighbors = new ArrayList<Integer>();//邻接表的形式表示图结构

     private double pr=1;

     public Node(int nodeId)

     {

         this.nodeId = nodeId;

     }

     public int getDegree()

     {

         return this.neighbors.size();

     }

     public ArrayList<Integer> getNeighbors()

     {

         return this.neighbors;

     }

     public void setNeighbors(ArrayList<Integer> neighbors)

     {

         this.neighbors=neighbors;

     }

     public double getPR()

     {

         return pr;

     }

     public void setPR(double val)

     {

         this.pr=val;

     }

     // 按PageRank值排序

     public int compareTo(Node anotherNode)

     {

         if (this.neighbors != null && anotherNode.neighbors != null)

         {

             // 降序排列

             if (anotherNode.getPR() >this.getPR())

                 return 1;

             else if (anotherNode.getPR() <this.getPR())

                 return -1;

             else

                 return 0;

             // 升序排列

             // return this.getPR()-anotherNode.getPR();

         }

         return 0;

     }

 }

巴特西

PageRank的java实现

最新文章

热门文章