edu.uci.ics.jung.algorithms.scoring
Class PageRankWithPriors<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,S>
edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,Double>
edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
- All Implemented Interfaces:
- VertexScorer<V,Double>, IterativeContext
- Direct Known Subclasses:
- KStepMarkov, PageRank
public class PageRankWithPriors<V,E>
- extends AbstractIterativeScorerWithPriors<V,E,Double>
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 Also:
- "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003",
PageRank
Field Summary |
protected double |
disappearing_potential
Maintains the amount of potential associated with vertices with no out-edges. |
Constructor Summary |
PageRankWithPriors(Hypergraph<V,E> graph,
org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
double alpha)
Creates an instance with the specified graph, edge weights, vertex priors, and
'random jump' probability (alpha). |
PageRankWithPriors(Hypergraph<V,E> graph,
org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
double alpha)
Creates an instance with the specified graph, vertex priors, and
'random jump' probability (alpha). |
Method Summary |
protected void |
afterStep()
Cleans up after each step. |
protected void |
collectDisappearingPotential(V v)
Collects the "disappearing potential" associated with vertices that have
no outgoing edges. |
double |
update(V v)
Updates the value for this vertex. |
Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer |
acceptDisconnectedGraph, done, evaluate, getAdjustedIncidentCount, getCurrentValue, getEdgeWeight, getEdgeWeights, getIterations, getMaxIterations, getOutputValue, getTolerance, getVertexScore, isDisconnectedGraphOK, setCurrentValue, setEdgeWeights, setHyperedgesAreSelfLoops, setMaxIterations, setOutputValue, setTolerance, step, swapOutputForCurrent, updateMaxDelta |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
disappearing_potential
protected double disappearing_potential
- Maintains the amount of potential associated with vertices with no out-edges.
PageRankWithPriors
public PageRankWithPriors(Hypergraph<V,E> graph,
org.apache.commons.collections15.Transformer<E,? extends Number> edge_weights,
org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
double alpha)
- Creates an instance with the specified graph, edge weights, vertex priors, and
'random jump' probability (alpha).
- Parameters:
graph
- the input graphedge_weights
- the edge weights, denoting transition probabilities from source to destinationvertex_priors
- the prior probabilities for each vertexalpha
- the probability of executing a 'random jump' at each step
PageRankWithPriors
public PageRankWithPriors(Hypergraph<V,E> graph,
org.apache.commons.collections15.Transformer<V,Double> vertex_priors,
double 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.
- Parameters:
graph
- the input graphvertex_priors
- the prior probabilities for each vertexalpha
- the probability of executing a 'random jump' at each step
update
public double update(V v)
- Updates the value for this vertex. Called by
step()
.
- Specified by:
update
in class AbstractIterativeScorer<V,E,Double>
- Parameters:
v
- the vertex whose value is to be updated
- Returns:
afterStep
protected void afterStep()
- 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
.
- Overrides:
afterStep
in class AbstractIterativeScorer<V,E,Double>
collectDisappearingPotential
protected void collectDisappearingPotential(V v)
- 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.
- Overrides:
collectDisappearingPotential
in class AbstractIterativeScorer<V,E,Double>
Copyright © 2009. All Rights Reserved.