+++ /dev/null
-/*
- * Created on Jul 15, 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 edu.uci.ics.jung.algorithms.scoring.util.ScoringUtils;
-import edu.uci.ics.jung.graph.Graph;
-
-import org.apache.commons.collections15.Transformer;
-
-/**
- * Assigns hub and authority scores to each vertex depending on the topology of
- * the network. The essential idea is that a vertex is a hub to the extent
- * that it links to authoritative vertices, and is an authority to the extent
- * that it links to 'hub' vertices.
- *
- * <p>The classic HITS algorithm essentially proceeds as follows:
- * <pre>
- * assign equal initial hub and authority values to each vertex
- * repeat
- * for each vertex w:
- * w.hub = sum over successors x of x.authority
- * w.authority = sum over predecessors v of v.hub
- * normalize hub and authority scores so that the sum of the squares of each = 1
- * until scores converge
- * </pre>
- *
- * HITS is somewhat different from random walk/eigenvector-based algorithms
- * such as PageRank in that:
- * <ul>
- * <li/>there are two mutually recursive scores being calculated, rather than
- * a single value
- * <li/>the edge weights are effectively all 1, i.e., they can't be interpreted
- * as transition probabilities. This means that the more inlinks and outlinks
- * that a vertex has, the better, since adding an inlink (or outlink) does
- * not dilute the influence of the other inlinks (or outlinks) as in
- * random walk-based algorithms.
- * <li/>the scores cannot be interpreted as posterior probabilities (due to the different
- * normalization)
- * </ul>
- *
- * This implementation has the classic behavior by default. However, it has
- * been generalized somewhat so that it can act in a more "PageRank-like" fashion:
- * <ul>
- * <li/>this implementation has an optional 'random jump probability' parameter analogous
- * to the 'alpha' parameter used by PageRank. Varying this value between 0 and 1
- * allows the user to vary between the classic HITS behavior and one in which the
- * scores are smoothed to a uniform distribution.
- * The default value for this parameter is 0 (no random jumps possible).
- * <li/>the edge weights can be set to anything the user likes, and in
- * particular they can be set up (e.g. using <code>UniformDegreeWeight</code>)
- * so that the weights of the relevant edges incident to a vertex sum to 1.
- * <li/>The vertex score normalization has been factored into its own method
- * so that it can be overridden by a subclass. Thus, for example,
- * since the vertices' values are set to sum to 1 initially, if the weights of the
- * relevant edges incident to a vertex sum to 1, then the vertices' values
- * will continue to sum to 1 if the "sum-of-squares" normalization code
- * is overridden to a no-op. (Other normalization methods may also be employed.)
- * </ul>
- *
- * @param <V> the vertex type
- * @param <E> the edge type
- *
- * @see "'Authoritative sources in a hyperlinked environment' by Jon Kleinberg, 1997"
- */
-public class HITS<V,E> extends HITSWithPriors<V,E>
-{
-
- /**
- * Creates an instance for the specified graph, edge weights, and alpha
- * (random jump probability) parameter.
- * @param g the input graph
- * @param edge_weights the weights to use for each edge
- * @param alpha the probability of a hub giving some authority to all vertices,
- * and of an authority increasing the score of all hubs (not just those connected
- * via links)
- */
- public HITS(Graph<V,E> g, Transformer<E, Double> edge_weights, double alpha)
- {
- super(g, edge_weights, ScoringUtils.getHITSUniformRootPrior(g.getVertices()), alpha);
- }
-
- /**
- * Creates an instance for the specified graph and alpha (random jump probability)
- * parameter. The edge weights are all set to 1.
- * @param g the input graph
- * @param alpha the probability of a hub giving some authority to all vertices,
- * and of an authority increasing the score of all hubs (not just those connected
- * via links)
- */
- public HITS(Graph<V,E> g, double alpha)
- {
- super(g, ScoringUtils.getHITSUniformRootPrior(g.getVertices()), alpha);
- }
-
- /**
- * Creates an instance for the specified graph. The edge weights are all set to 1
- * and alpha is set to 0.
- * @param g the input graph
- */
- public HITS(Graph<V,E> g)
- {
- this(g, 0.0);
- }
-
-
- /**
- * Maintains hub and authority score information for a vertex.
- */
- public static class Scores
- {
- /**
- * The hub score for a vertex.
- */
- public double hub;
-
- /**
- * The authority score for a vertex.
- */
- public double authority;
-
- /**
- * Creates an instance with the specified hub and authority score.
- */
- public Scores(double hub, double authority)
- {
- this.hub = hub;
- this.authority = authority;
- }
-
- @Override
- public String toString()
- {
- return String.format("[h:%.4f,a:%.4f]", this.hub, this.authority);
- }
- }
-}
Code Review / controller.git / blobdiff