/** * 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. * *
NOTE: 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 before calling {@code evaluate()}: *
* KStepMarkov ksm = new KStepMarkov(...); * ksm.setCumulative(true); * ksm.evaluate(); ** * 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
step()
.
*/
@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);
}
}