third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/PageRankWithPriors.java

   1 /*
   2  * Created on Jul 6, 2007
   3  *
   4  * Copyright (c) 2007, the JUNG Project and the Regents of the University
   5  * of California
   6  * All rights reserved.
   7  *
   8  * This software is open-source under the BSD license; see either
   9  * "license.txt" or
  10  * http://jung.sourceforge.net/license.txt for a description.
  11  */
  12 package edu.uci.ics.jung.algorithms.scoring;
  13
  14 import org.apache.commons.collections15.Transformer;
  15
  16 import edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight;
  17 import edu.uci.ics.jung.graph.Hypergraph;
  18
  19 /**
  20  * A generalization of PageRank that permits non-uniformly-distributed random jumps.
  21  * The 'vertex_priors' (that is, prior probabilities for each vertex) may be
  22  * thought of as the fraction of the total 'potential' that is assigned to that
  23  * vertex at each step out of the portion that is assigned according
  24  * to random jumps (this portion is specified by 'alpha').
  25  *
  26  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
  27  * @see PageRank
  28  */
  29 public class PageRankWithPriors<V, E>
  30         extends AbstractIterativeScorerWithPriors<V,E,Double>
  31 {
  32     /**
  33      * Maintains the amount of potential associated with vertices with no out-edges.
  34      */
  35     protected double disappearing_potential = 0.0;
  36
  37     /**
  38      * Creates an instance with the specified graph, edge weights, vertex priors, and
  39      * 'random jump' probability (alpha).
  40      * @param graph the input graph
  41      * @param edge_weights the edge weights, denoting transition probabilities from source to destination
  42      * @param vertex_priors the prior probabilities for each vertex
  43      * @param alpha the probability of executing a 'random jump' at each step
  44      */
  45     public PageRankWithPriors(Hypergraph<V,E> graph,
  46                 Transformer<E, ? extends Number> edge_weights,
  47             Transformer<V, Double> vertex_priors, double alpha)
  48     {
  49         super(graph, edge_weights, vertex_priors, alpha);
  50     }
  51
  52     /**
  53      * Creates an instance with the specified graph, vertex priors, and
  54      * 'random jump' probability (alpha).  The outgoing edge weights for each
  55      * vertex will be equal and sum to 1.
  56      * @param graph the input graph
  57      * @param vertex_priors the prior probabilities for each vertex
  58      * @param alpha the probability of executing a 'random jump' at each step
  59      */
  60     public PageRankWithPriors(Hypergraph<V,E> graph,
  61                 Transformer<V, Double> vertex_priors, double alpha)
  62     {
  63         super(graph, vertex_priors, alpha);
  64         this.edge_weights = new UniformDegreeWeight<V,E>(graph);
  65     }
  66
  67     /**
  68      * Updates the value for this vertex.  Called by <code>step()</code>.
  69      */
  70     @Override
  71     public double update(V v)
  72     {
  73         collectDisappearingPotential(v);
  74
  75         double v_input = 0;
  76         for (E e : graph.getInEdges(v))
  77         {
  78                 // For graphs, the code below is equivalent to
  79 //          V w = graph.getOpposite(v, e);
  80 //          total_input += (getCurrentValue(w) * getEdgeWeight(w,e).doubleValue());
  81                 // For hypergraphs, this divides the potential coming from w
  82                 // by the number of vertices in the connecting edge e.
  83                 int incident_count = getAdjustedIncidentCount(e);
  84                 for (V w : graph.getIncidentVertices(e))
  85                 {
  86                         if (!w.equals(v) || hyperedges_are_self_loops)
  87                                 v_input += (getCurrentValue(w) *
  88                                                 getEdgeWeight(w,e).doubleValue() / incident_count);
  89                 }
  90         }
  91
  92         // modify total_input according to alpha
  93         double new_value = alpha > 0 ?
  94                         v_input * (1 - alpha) + getVertexPrior(v) * alpha :
  95                         v_input;
  96         setOutputValue(v, new_value);
  97
  98         return Math.abs(getCurrentValue(v) - new_value);
  99     }
 100
 101     /**
 102      * Cleans up after each step.  In this case that involves allocating the disappearing
 103      * potential (thus maintaining normalization of the scores) according to the vertex
 104      * probability priors, and then calling
 105      * <code>super.afterStep</code>.
 106      */
 107     @Override
 108     protected void afterStep()
 109     {
 110         // distribute disappearing potential according to priors
 111         if (disappearing_potential > 0)
 112         {
 113             for (V v : graph.getVertices())
 114             {
 115                 setOutputValue(v, getOutputValue(v) +
 116                         (1 - alpha) * (disappearing_potential * getVertexPrior(v)));
 117             }
 118             disappearing_potential = 0;
 119         }
 120
 121         super.afterStep();
 122     }
 123
 124     /**
 125      * Collects the "disappearing potential" associated with vertices that have
 126      * no outgoing edges.  Vertices that have no outgoing edges do not directly
 127      * contribute to the scores of other vertices.  These values are collected
 128      * at each step and then distributed across all vertices
 129      * as a part of the normalization process.
 130     */
 131     @Override
 132     protected void collectDisappearingPotential(V v)
 133     {
 134         if (graph.outDegree(v) == 0)
 135         {
 136             if (isDisconnectedGraphOK())
 137                 disappearing_potential += getCurrentValue(v);
 138             else
 139                 throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
 140         }
 141     }
 142 }