/*
* Created on Jul 6, 2007
*
* Copyright (c) 2007, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.scoring;
import com.google.common.base.Function;
import edu.uci.ics.jung.algorithms.scoring.util.UniformDegreeWeight;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* A generalization of PageRank 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' that is assigned to that
* vertex at each step out of the portion that is assigned according
* to random jumps (this portion is specified by 'alpha').
*
* @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
* @see PageRank
*/
public class PageRankWithPriors
extends AbstractIterativeScorerWithPriors
{
/**
* Maintains the amount of potential associated with vertices with no out-edges.
*/
protected double disappearing_potential = 0.0;
/**
* Creates an instance with the specified graph, edge weights, vertex priors, and
* 'random jump' probability (alpha).
* @param graph the input graph
* @param edge_weights the edge weights, denoting transition probabilities from source to destination
* @param vertex_priors the prior probabilities for each vertex
* @param alpha the probability of executing a 'random jump' at each step
*/
public PageRankWithPriors(Hypergraph graph,
Function edge_weights,
Function vertex_priors, double alpha)
{
super(graph, edge_weights, vertex_priors, alpha);
}
/**
* Creates an instance with the specified graph, vertex priors, and
* 'random jump' probability (alpha). The outgoing edge weights for each
* vertex will be equal and sum to 1.
* @param graph the input graph
* @param vertex_priors the prior probabilities for each vertex
* @param alpha the probability of executing a 'random jump' at each step
*/
public PageRankWithPriors(Hypergraph graph,
Function vertex_priors, double alpha)
{
super(graph, vertex_priors, alpha);
this.edge_weights = new UniformDegreeWeight(graph);
}
/**
* Updates the value for this vertex. Called by step().
*/
@Override
public double update(V 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);
return Math.abs(getCurrentValue(v) - new_value);
}
/**
* Cleans up after each step. In this case that involves allocating the disappearing
* potential (thus maintaining normalization of the scores) according to the vertex
* probability priors, and then calling
* super.afterStep.
*/
@Override
protected void afterStep()
{
// distribute disappearing potential according to priors
if (disappearing_potential > 0)
{
for (V v : graph.getVertices())
{
setOutputValue(v, getOutputValue(v) +
(1 - alpha) * (disappearing_potential * getVertexPrior(v)));
}
disappearing_potential = 0;
}
super.afterStep();
}
/**
* Collects the "disappearing potential" associated with vertices that have
* no outgoing edges. Vertices that have no outgoing edges do not directly
* contribute to the scores of other vertices. These values are collected
* at each step and then distributed across all vertices
* as a part of the normalization process.
*/
@Override
protected void collectDisappearingPotential(V v)
{
if (graph.outDegree(v) == 0)
{
if (isDisconnectedGraphOK())
disappearing_potential += getCurrentValue(v);
else
throw new IllegalArgumentException("Outdegree of " + v + " must be > 0");
}
}
}
Ads help maintain this website.