+++ /dev/null
-/**
- * Copyright (c) 2008, 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.
- * Created on Aug 22, 2008
- *
- */
-package edu.uci.ics.jung.algorithms.scoring;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.algorithms.scoring.util.ScoringUtils;
-import edu.uci.ics.jung.graph.Hypergraph;
-
-/**
- * A special case of {@code PageRankWithPriors} in which the final scores
- * represent a probability distribution over position assuming a random (Markovian)
- * walk of exactly k steps, based on the initial distribution specified by the priors.
- *
- * <p><b>NOTE</b>: The version of {@code KStepMarkov} in {@code algorithms.importance}
- * (and in JUNG 1.x) is believed to be incorrect: rather than returning
- * a score which represents a probability distribution over position assuming
- * a k-step random walk, it returns a score which represents the sum over all steps
- * of the probability for each step. If you want that behavior, set the
- * 'cumulative' flag as follows <i>before calling {@code evaluate()}</i>:
- * <pre>
- * KStepMarkov ksm = new KStepMarkov(...);
- * ksm.setCumulative(true);
- * ksm.evaluate();
- * </pre>
- *
- * By default, the 'cumulative' flag is set to false.
- *
- * NOTE: THIS CLASS IS NOT YET COMPLETE. USE AT YOUR OWN RISK. (The original behavior
- * is captured by the version still available in {@code algorithms.importance}.)
- *
- * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
- * @see PageRank
- * @see PageRankWithPriors
- */
-public class KStepMarkov<V,E> extends PageRankWithPriors<V,E>
-{
- private boolean cumulative;
-
- /**
- * Creates an instance based on the specified graph, edge weights, vertex
- * priors (initial scores), and number of steps to take.
- * @param graph the input graph
- * @param edge_weights the edge weights (transition probabilities)
- * @param vertex_priors the initial probability distribution (score assignment)
- * @param steps the number of times that {@code step()} will be called by {@code evaluate}
- */
- public KStepMarkov(Hypergraph<V,E> graph, Transformer<E, ? extends Number> edge_weights,
- Transformer<V, Double> vertex_priors, int steps)
- {
- super(graph, edge_weights, vertex_priors, 0);
- initialize(steps);
- }
-
- /**
- * Creates an instance based on the specified graph, vertex
- * priors (initial scores), and number of steps to take. The edge
- * weights (transition probabilities) are set to default values (a uniform
- * distribution over all outgoing edges).
- * @param graph the input graph
- * @param vertex_priors the initial probability distribution (score assignment)
- * @param steps the number of times that {@code step()} will be called by {@code evaluate}
- */
- public KStepMarkov(Hypergraph<V,E> graph, Transformer<V, Double> vertex_priors, int steps)
- {
- super(graph, vertex_priors, 0);
- initialize(steps);
- }
-
- /**
- * Creates an instance based on the specified graph and number of steps to
- * take. The edge weights (transition probabilities) and vertex initial scores
- * (prior probabilities) are set to default values (a uniform
- * distribution over all outgoing edges, and a uniform distribution over
- * all vertices, respectively).
- * @param graph the input graph
- * @param steps the number of times that {@code step()} will be called by {@code evaluate}
- */
- public KStepMarkov(Hypergraph<V,E> graph, int steps)
- {
- super(graph, ScoringUtils.getUniformRootPrior(graph.getVertices()), 0);
- initialize(steps);
- }
-
- private void initialize(int steps)
- {
- this.acceptDisconnectedGraph(false);
-
- if (steps <= 0)
- throw new IllegalArgumentException("Number of steps must be > 0");
-
- this.max_iterations = steps;
- this.tolerance = -1.0;
-
- this.cumulative = false;
- }
-
- /**
- * Specifies whether this instance should assign a score to each vertex
- * based on the
- * @param cumulative
- */
- public void setCumulative(boolean cumulative)
- {
- this.cumulative = cumulative;
- }
-
- /**
- * Updates the value for this vertex. Called by <code>step()</code>.
- */
- @Override
- public double update(V v)
- {
- if (!cumulative)
- return super.update(v);
-
- collectDisappearingPotential(v);
-
- double v_input = 0;
- for (E e : graph.getInEdges(v))
- {
- // For graphs, the code below is equivalent to
-// V w = graph.getOpposite(v, e);
-// total_input += (getCurrentValue(w) * getEdgeWeight(w,e).doubleValue());
- // For hypergraphs, this divides the potential coming from w
- // by the number of vertices in the connecting edge e.
- int incident_count = getAdjustedIncidentCount(e);
- for (V w : graph.getIncidentVertices(e))
- {
- if (!w.equals(v) || hyperedges_are_self_loops)
- v_input += (getCurrentValue(w) *
- getEdgeWeight(w,e).doubleValue() / incident_count);
- }
- }
-
- // modify total_input according to alpha
- double new_value = alpha > 0 ?
- v_input * (1 - alpha) + getVertexPrior(v) * alpha :
- v_input;
- setOutputValue(v, new_value + getCurrentValue(v));
-
- // FIXME: DO WE NEED TO CHANGE HOW DISAPPEARING IS COUNTED? NORMALIZE?
-
- return Math.abs(getCurrentValue(v) - new_value);
- }
-
-}
Code Review / controller.git / blobdiff