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

   1 /**
   2  * Copyright (c) 2008, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  * Created on Aug 22, 2008
  10  *
  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.ScoringUtils;
  17 import edu.uci.ics.jung.graph.Hypergraph;
  18
  19 /**
  20  * A special case of {@code PageRankWithPriors} in which the final scores
  21  * represent a probability distribution over position assuming a random (Markovian)
  22  * walk of exactly k steps, based on the initial distribution specified by the priors.
  23  *
  24  * <p><b>NOTE</b>: The version of {@code KStepMarkov} in {@code algorithms.importance}
  25  * (and in JUNG 1.x) is believed to be incorrect: rather than returning
  26  * a score which represents a probability distribution over position assuming
  27  * a k-step random walk, it returns a score which represents the sum over all steps
  28  * of the probability for each step.  If you want that behavior, set the
  29  * 'cumulative' flag as follows <i>before calling {@code evaluate()}</i>:
  30  * <pre>
  31  *     KStepMarkov ksm = new KStepMarkov(...);
  32  *     ksm.setCumulative(true);
  33  *     ksm.evaluate();
  34  * </pre>
  35  *
  36  * By default, the 'cumulative' flag is set to false.
  37  *
  38  * NOTE: THIS CLASS IS NOT YET COMPLETE.  USE AT YOUR OWN RISK.  (The original behavior
  39  * is captured by the version still available in {@code algorithms.importance}.)
  40  *
  41  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
  42  * @see PageRank
  43  * @see PageRankWithPriors
  44  */
  45 public class KStepMarkov<V,E> extends PageRankWithPriors<V,E>
  46 {
  47         private boolean cumulative;
  48
  49         /**
  50          * Creates an instance based on the specified graph, edge weights, vertex
  51          * priors (initial scores), and number of steps to take.
  52          * @param graph the input graph
  53          * @param edge_weights the edge weights (transition probabilities)
  54          * @param vertex_priors the initial probability distribution (score assignment)
  55          * @param steps the number of times that {@code step()} will be called by {@code evaluate}
  56          */
  57         public KStepMarkov(Hypergraph<V,E> graph, Transformer<E, ? extends Number> edge_weights,
  58                                            Transformer<V, Double> vertex_priors, int steps)
  59         {
  60                 super(graph, edge_weights, vertex_priors, 0);
  61                 initialize(steps);
  62         }
  63
  64         /**
  65          * Creates an instance based on the specified graph, vertex
  66          * priors (initial scores), and number of steps to take.  The edge
  67          * weights (transition probabilities) are set to default values (a uniform
  68          * distribution over all outgoing edges).
  69          * @param graph the input graph
  70          * @param vertex_priors the initial probability distribution (score assignment)
  71          * @param steps the number of times that {@code step()} will be called by {@code evaluate}
  72          */
  73         public KStepMarkov(Hypergraph<V,E> graph, Transformer<V, Double> vertex_priors, int steps)
  74         {
  75                 super(graph, vertex_priors, 0);
  76                 initialize(steps);
  77         }
  78
  79         /**
  80          * Creates an instance based on the specified graph and number of steps to
  81          * take.  The edge weights (transition probabilities) and vertex initial scores
  82          * (prior probabilities) are set to default values (a uniform
  83          * distribution over all outgoing edges, and a uniform distribution over
  84          * all vertices, respectively).
  85          * @param graph the input graph
  86          * @param steps the number of times that {@code step()} will be called by {@code evaluate}
  87          */
  88         public KStepMarkov(Hypergraph<V,E> graph, int steps)
  89         {
  90                 super(graph, ScoringUtils.getUniformRootPrior(graph.getVertices()), 0);
  91                 initialize(steps);
  92         }
  93
  94         private void initialize(int steps)
  95         {
  96                 this.acceptDisconnectedGraph(false);
  97
  98                 if (steps <= 0)
  99                         throw new IllegalArgumentException("Number of steps must be > 0");
 100
 101                 this.max_iterations = steps;
 102                 this.tolerance = -1.0;
 103
 104                 this.cumulative = false;
 105         }
 106
 107         /**
 108          * Specifies whether this instance should assign a score to each vertex
 109          * based on the
 110          * @param cumulative
 111          */
 112         public void setCumulative(boolean cumulative)
 113         {
 114                 this.cumulative = cumulative;
 115         }
 116
 117     /**
 118      * Updates the value for this vertex.  Called by <code>step()</code>.
 119      */
 120     @Override
 121     public double update(V v)
 122     {
 123         if (!cumulative)
 124                 return super.update(v);
 125
 126         collectDisappearingPotential(v);
 127
 128         double v_input = 0;
 129         for (E e : graph.getInEdges(v))
 130         {
 131                 // For graphs, the code below is equivalent to
 132 //          V w = graph.getOpposite(v, e);
 133 //          total_input += (getCurrentValue(w) * getEdgeWeight(w,e).doubleValue());
 134                 // For hypergraphs, this divides the potential coming from w
 135                 // by the number of vertices in the connecting edge e.
 136                 int incident_count = getAdjustedIncidentCount(e);
 137                 for (V w : graph.getIncidentVertices(e))
 138                 {
 139                         if (!w.equals(v) || hyperedges_are_self_loops)
 140                                 v_input += (getCurrentValue(w) *
 141                                                 getEdgeWeight(w,e).doubleValue() / incident_count);
 142                 }
 143         }
 144
 145         // modify total_input according to alpha
 146         double new_value = alpha > 0 ?
 147                         v_input * (1 - alpha) + getVertexPrior(v) * alpha :
 148                         v_input;
 149         setOutputValue(v, new_value + getCurrentValue(v));
 150
 151         // FIXME: DO WE NEED TO CHANGE HOW DISAPPEARING IS COUNTED?  NORMALIZE?
 152
 153         return Math.abs(getCurrentValue(v) - new_value);
 154     }
 155
 156 }