2 * Created on Jul 14, 2007
4 * Copyright (c) 2007, the JUNG Project and the Regents of the University
8 * This software is open-source under the BSD license; see either
10 * http://jung.sourceforge.net/license.txt for a description.
12 package edu.uci.ics.jung.algorithms.scoring;
14 import org.apache.commons.collections15.Transformer;
15 import org.apache.commons.collections15.functors.ConstantTransformer;
17 import edu.uci.ics.jung.graph.Hypergraph;
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
26 * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
28 public class HITSWithPriors<V, E>
29 extends AbstractIterativeScorerWithPriors<V,E,HITS.Scores>
32 * The sum of the potential, at each step, associated with vertices with no outedges (authority)
33 * or no inedges (hub).
35 protected HITS.Scores disappearing_potential;
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
45 public HITSWithPriors(Hypergraph<V,E> g,
46 Transformer<E, ? extends Number> edge_weights,
47 Transformer<V, HITS.Scores> vertex_priors, double alpha)
49 super(g, edge_weights, vertex_priors, alpha);
50 disappearing_potential = new HITS.Scores(0,0);
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
60 @SuppressWarnings("unchecked")
61 public HITSWithPriors(Hypergraph<V,E> g,
62 Transformer<V, HITS.Scores> vertex_priors, double alpha)
64 super(g, new ConstantTransformer(1.0), vertex_priors, alpha);
65 disappearing_potential = new HITS.Scores(0,0);
69 * Updates the value for this vertex.
72 protected double update(V v)
74 collectDisappearingPotential(v);
77 for (E e : graph.getInEdges(v))
79 int incident_count = getAdjustedIncidentCount(e);
80 for (V w : graph.getIncidentVertices(e))
82 if (!w.equals(v) || hyperedges_are_self_loops)
83 v_auth += (getCurrentValue(w).hub *
84 getEdgeWeight(w,e).doubleValue() / incident_count);
86 // V w = graph.getOpposite(v, e);
87 // auth += (getCurrentValue(w).hub * getEdgeWeight(w, e).doubleValue());
91 for (E e : graph.getOutEdges(v))
93 int incident_count = getAdjustedIncidentCount(e);
94 for (V w : graph.getIncidentVertices(e))
96 if (!w.equals(v) || hyperedges_are_self_loops)
97 v_hub += (getCurrentValue(w).authority *
98 getEdgeWeight(w,e).doubleValue() / incident_count);
100 // V x = graph.getOpposite(v,e);
101 // hub += (getCurrentValue(x).authority * getEdgeWeight(x, e).doubleValue());
104 // modify total_input according to alpha
107 v_auth = v_auth * (1 - alpha) + getVertexPrior(v).authority * alpha;
108 v_hub = v_hub * (1 - alpha) + getVertexPrior(v).hub * alpha;
110 setOutputValue(v, new HITS.Scores(v_hub, v_auth));
112 return Math.max(Math.abs(getCurrentValue(v).hub - v_hub),
113 Math.abs(getCurrentValue(v).authority - v_auth));
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)
123 protected void afterStep()
125 if (disappearing_potential.hub > 0 || disappearing_potential.authority > 0)
127 for (V v : graph.getVertices())
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));
135 disappearing_potential.hub = 0;
136 disappearing_potential.authority = 0;
145 * Normalizes scores so that sum of their squares = 1.
146 * This method may be overridden so as to yield different
149 protected void normalizeScores() {
151 double auth_ssum = 0;
152 for (V v : graph.getVertices())
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);
160 hub_ssum = Math.sqrt(hub_ssum);
161 auth_ssum = Math.sqrt(auth_ssum);
163 for (V v : graph.getVertices())
165 HITS.Scores values = getOutputValue(v);
166 setOutputValue(v, new HITS.Scores(
167 values.hub / hub_ssum,
168 values.authority / auth_ssum));
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.)
182 protected void collectDisappearingPotential(V v)
184 if (graph.outDegree(v) == 0)
186 if (isDisconnectedGraphOK())
187 disappearing_potential.hub += getCurrentValue(v).authority;
189 throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
191 if (graph.inDegree(v) == 0)
193 if (isDisconnectedGraphOK())
194 disappearing_potential.authority += getCurrentValue(v).hub;
196 throw new IllegalArgumentException("Indegree of " + v + " must be > 0");