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

   1 /*
   2  * Created on Jul 14, 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 import org.apache.commons.collections15.functors.ConstantTransformer;
  16
  17 import edu.uci.ics.jung.graph.Hypergraph;
  18
  19 /**
  20  * A generalization of HITS 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' (hub or authority score)
  23  * that is assigned to that vertex out of the portion that is assigned according
  24  * to random jumps.
  25  *
  26  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
  27  */
  28 public class HITSWithPriors<V, E>
  29         extends AbstractIterativeScorerWithPriors<V,E,HITS.Scores>
  30 {
  31     /**
  32      * The sum of the potential, at each step, associated with vertices with no outedges (authority)
  33      * or no inedges (hub).
  34      */
  35     protected HITS.Scores disappearing_potential;
  36
  37     /**
  38      * Creates an instance for the specified graph, edge weights, vertex prior probabilities,
  39      * and random jump probability (alpha).
  40      * @param g the input graph
  41      * @param edge_weights the edge weights
  42      * @param vertex_priors the prior probability for each vertex
  43      * @param alpha the probability of a random jump at each step
  44      */
  45     public HITSWithPriors(Hypergraph<V,E> g,
  46             Transformer<E, ? extends Number> edge_weights,
  47             Transformer<V, HITS.Scores> vertex_priors, double alpha)
  48     {
  49         super(g, edge_weights, vertex_priors, alpha);
  50         disappearing_potential = new HITS.Scores(0,0);
  51     }
  52
  53     /**
  54      * Creates an instance for the specified graph, vertex priors, and random
  55      * jump probability (alpha).  The edge weights default to 1.0.
  56      * @param g the input graph
  57      * @param vertex_priors the prior probability for each vertex
  58      * @param alpha the probability of a random jump at each step
  59      */
  60     @SuppressWarnings("unchecked")
  61     public HITSWithPriors(Hypergraph<V,E> g,
  62           Transformer<V, HITS.Scores> vertex_priors, double alpha)
  63     {
  64         super(g, new ConstantTransformer(1.0), vertex_priors, alpha);
  65         disappearing_potential = new HITS.Scores(0,0);
  66     }
  67
  68     /**
  69      * Updates the value for this vertex.
  70      */
  71     @Override
  72     protected double update(V v)
  73     {
  74         collectDisappearingPotential(v);
  75
  76         double v_auth = 0;
  77         for (E e : graph.getInEdges(v))
  78         {
  79                 int incident_count = getAdjustedIncidentCount(e);
  80                 for (V w : graph.getIncidentVertices(e))
  81                 {
  82                         if (!w.equals(v) || hyperedges_are_self_loops)
  83                                 v_auth += (getCurrentValue(w).hub *
  84                                                 getEdgeWeight(w,e).doubleValue() / incident_count);
  85                 }
  86 //            V w = graph.getOpposite(v, e);
  87 //            auth += (getCurrentValue(w).hub * getEdgeWeight(w, e).doubleValue());
  88         }
  89
  90         double v_hub = 0;
  91         for (E e : graph.getOutEdges(v))
  92         {
  93                 int incident_count = getAdjustedIncidentCount(e);
  94                 for (V w : graph.getIncidentVertices(e))
  95                 {
  96                         if (!w.equals(v) || hyperedges_are_self_loops)
  97                                 v_hub += (getCurrentValue(w).authority *
  98                                                 getEdgeWeight(w,e).doubleValue() / incident_count);
  99                 }
 100 //            V x = graph.getOpposite(v,e);
 101 //            hub += (getCurrentValue(x).authority * getEdgeWeight(x, e).doubleValue());
 102         }
 103
 104         // modify total_input according to alpha
 105         if (alpha > 0)
 106         {
 107                 v_auth = v_auth * (1 - alpha) + getVertexPrior(v).authority * alpha;
 108                 v_hub = v_hub * (1 - alpha) + getVertexPrior(v).hub * alpha;
 109         }
 110         setOutputValue(v, new HITS.Scores(v_hub, v_auth));
 111
 112         return Math.max(Math.abs(getCurrentValue(v).hub - v_hub),
 113                         Math.abs(getCurrentValue(v).authority - v_auth));
 114     }
 115
 116     /**
 117      * Code which is executed after each step.  In this case, deals with the
 118      * 'disappearing potential', normalizes the scores, and then calls
 119      * <code>super.afterStep()</code>.
 120      * @see #collectDisappearingPotential(Object)
 121      */
 122     @Override
 123     protected void afterStep()
 124     {
 125         if (disappearing_potential.hub > 0 || disappearing_potential.authority > 0)
 126         {
 127             for (V v : graph.getVertices())
 128             {
 129                 double new_hub = getOutputValue(v).hub +
 130                     (1 - alpha) * (disappearing_potential.hub * getVertexPrior(v).hub);
 131                 double new_auth = getOutputValue(v).authority +
 132                     (1 - alpha) * (disappearing_potential.authority * getVertexPrior(v).authority);
 133                 setOutputValue(v, new HITS.Scores(new_hub, new_auth));
 134             }
 135             disappearing_potential.hub = 0;
 136             disappearing_potential.authority = 0;
 137         }
 138
 139         normalizeScores();
 140
 141         super.afterStep();
 142     }
 143
 144         /**
 145          * Normalizes scores so that sum of their squares = 1.
 146          * This method may be overridden so as to yield different
 147          * normalizations.
 148          */
 149         protected void normalizeScores() {
 150         double hub_ssum = 0;
 151         double auth_ssum = 0;
 152         for (V v : graph.getVertices())
 153         {
 154                 double hub_val = getOutputValue(v).hub;
 155                 double auth_val = getOutputValue(v).authority;
 156                 hub_ssum += (hub_val * hub_val);
 157                 auth_ssum += (auth_val * auth_val);
 158         }
 159
 160         hub_ssum = Math.sqrt(hub_ssum);
 161         auth_ssum = Math.sqrt(auth_ssum);
 162
 163         for (V v : graph.getVertices())
 164         {
 165                 HITS.Scores values = getOutputValue(v);
 166                 setOutputValue(v, new HITS.Scores(
 167                                 values.hub / hub_ssum,
 168                                 values.authority / auth_ssum));
 169         }
 170         }
 171
 172         /**
 173          * Collects the "disappearing potential" associated with vertices that have either
 174          * no incoming edges, no outgoing edges, or both.  Vertices that have no incoming edges
 175          * do not directly contribute to the hub scores of other vertices; similarly, vertices
 176          * that have no outgoing edges do not directly contribute to the authority scores of
 177          * other vertices.  These values are collected at each step and then distributed across all vertices
 178          * as a part of the normalization process.  (This process is not required for, and does
 179          * not affect, the 'sum-of-squares'-style normalization.)
 180          */
 181     @Override
 182     protected void collectDisappearingPotential(V v)
 183     {
 184         if (graph.outDegree(v) == 0)
 185         {
 186             if (isDisconnectedGraphOK())
 187                 disappearing_potential.hub += getCurrentValue(v).authority;
 188             else
 189                 throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
 190         }
 191         if (graph.inDegree(v) == 0)
 192         {
 193             if (isDisconnectedGraphOK())
 194                 disappearing_potential.authority += getCurrentValue(v).hub;
 195             else
 196                 throw new IllegalArgumentException("Indegree of " + v + " must be > 0");
 197         }
 198     }
 199
 200 }