+++ /dev/null
-/*
- * Created on Jul 14, 2007
- *
- * Copyright (c) 2007, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.scoring;
-
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.functors.ConstantTransformer;
-
-import edu.uci.ics.jung.graph.Hypergraph;
-
-/**
- * A generalization of HITS that permits non-uniformly-distributed random jumps.
- * The 'vertex_priors' (that is, prior probabilities for each vertex) may be
- * thought of as the fraction of the total 'potential' (hub or authority score)
- * that is assigned to that vertex out of the portion that is assigned according
- * to random jumps.
- *
- * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
- */
-public class HITSWithPriors<V, E>
- extends AbstractIterativeScorerWithPriors<V,E,HITS.Scores>
-{
- /**
- * The sum of the potential, at each step, associated with vertices with no outedges (authority)
- * or no inedges (hub).
- */
- protected HITS.Scores disappearing_potential;
-
- /**
- * Creates an instance for the specified graph, edge weights, vertex prior probabilities,
- * and random jump probability (alpha).
- * @param g the input graph
- * @param edge_weights the edge weights
- * @param vertex_priors the prior probability for each vertex
- * @param alpha the probability of a random jump at each step
- */
- public HITSWithPriors(Hypergraph<V,E> g,
- Transformer<E, ? extends Number> edge_weights,
- Transformer<V, HITS.Scores> vertex_priors, double alpha)
- {
- super(g, edge_weights, vertex_priors, alpha);
- disappearing_potential = new HITS.Scores(0,0);
- }
-
- /**
- * Creates an instance for the specified graph, vertex priors, and random
- * jump probability (alpha). The edge weights default to 1.0.
- * @param g the input graph
- * @param vertex_priors the prior probability for each vertex
- * @param alpha the probability of a random jump at each step
- */
- @SuppressWarnings("unchecked")
- public HITSWithPriors(Hypergraph<V,E> g,
- Transformer<V, HITS.Scores> vertex_priors, double alpha)
- {
- super(g, new ConstantTransformer(1.0), vertex_priors, alpha);
- disappearing_potential = new HITS.Scores(0,0);
- }
-
- /**
- * Updates the value for this vertex.
- */
- @Override
- protected double update(V v)
- {
- collectDisappearingPotential(v);
-
- double v_auth = 0;
- for (E e : graph.getInEdges(v))
- {
- int incident_count = getAdjustedIncidentCount(e);
- for (V w : graph.getIncidentVertices(e))
- {
- if (!w.equals(v) || hyperedges_are_self_loops)
- v_auth += (getCurrentValue(w).hub *
- getEdgeWeight(w,e).doubleValue() / incident_count);
- }
-// V w = graph.getOpposite(v, e);
-// auth += (getCurrentValue(w).hub * getEdgeWeight(w, e).doubleValue());
- }
-
- double v_hub = 0;
- for (E e : graph.getOutEdges(v))
- {
- int incident_count = getAdjustedIncidentCount(e);
- for (V w : graph.getIncidentVertices(e))
- {
- if (!w.equals(v) || hyperedges_are_self_loops)
- v_hub += (getCurrentValue(w).authority *
- getEdgeWeight(w,e).doubleValue() / incident_count);
- }
-// V x = graph.getOpposite(v,e);
-// hub += (getCurrentValue(x).authority * getEdgeWeight(x, e).doubleValue());
- }
-
- // modify total_input according to alpha
- if (alpha > 0)
- {
- v_auth = v_auth * (1 - alpha) + getVertexPrior(v).authority * alpha;
- v_hub = v_hub * (1 - alpha) + getVertexPrior(v).hub * alpha;
- }
- setOutputValue(v, new HITS.Scores(v_hub, v_auth));
-
- return Math.max(Math.abs(getCurrentValue(v).hub - v_hub),
- Math.abs(getCurrentValue(v).authority - v_auth));
- }
-
- /**
- * Code which is executed after each step. In this case, deals with the
- * 'disappearing potential', normalizes the scores, and then calls
- * <code>super.afterStep()</code>.
- * @see #collectDisappearingPotential(Object)
- */
- @Override
- protected void afterStep()
- {
- if (disappearing_potential.hub > 0 || disappearing_potential.authority > 0)
- {
- for (V v : graph.getVertices())
- {
- double new_hub = getOutputValue(v).hub +
- (1 - alpha) * (disappearing_potential.hub * getVertexPrior(v).hub);
- double new_auth = getOutputValue(v).authority +
- (1 - alpha) * (disappearing_potential.authority * getVertexPrior(v).authority);
- setOutputValue(v, new HITS.Scores(new_hub, new_auth));
- }
- disappearing_potential.hub = 0;
- disappearing_potential.authority = 0;
- }
-
- normalizeScores();
-
- super.afterStep();
- }
-
- /**
- * Normalizes scores so that sum of their squares = 1.
- * This method may be overridden so as to yield different
- * normalizations.
- */
- protected void normalizeScores() {
- double hub_ssum = 0;
- double auth_ssum = 0;
- for (V v : graph.getVertices())
- {
- double hub_val = getOutputValue(v).hub;
- double auth_val = getOutputValue(v).authority;
- hub_ssum += (hub_val * hub_val);
- auth_ssum += (auth_val * auth_val);
- }
-
- hub_ssum = Math.sqrt(hub_ssum);
- auth_ssum = Math.sqrt(auth_ssum);
-
- for (V v : graph.getVertices())
- {
- HITS.Scores values = getOutputValue(v);
- setOutputValue(v, new HITS.Scores(
- values.hub / hub_ssum,
- values.authority / auth_ssum));
- }
- }
-
- /**
- * Collects the "disappearing potential" associated with vertices that have either
- * no incoming edges, no outgoing edges, or both. Vertices that have no incoming edges
- * do not directly contribute to the hub scores of other vertices; similarly, vertices
- * that have no outgoing edges do not directly contribute to the authority scores of
- * other vertices. These values are collected at each step and then distributed across all vertices
- * as a part of the normalization process. (This process is not required for, and does
- * not affect, the 'sum-of-squares'-style normalization.)
- */
- @Override
- protected void collectDisappearingPotential(V v)
- {
- if (graph.outDegree(v) == 0)
- {
- if (isDisconnectedGraphOK())
- disappearing_potential.hub += getCurrentValue(v).authority;
- else
- throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
- }
- if (graph.inDegree(v) == 0)
- {
- if (isDisconnectedGraphOK())
- disappearing_potential.authority += getCurrentValue(v).hub;
- else
- throw new IllegalArgumentException("Indegree of " + v + " must be > 0");
- }
- }
-
-}