edu.uci.ics.jung.algorithms.importance
Class PageRank<V,E>

java.lang.Object
  edu.uci.ics.jung.algorithms.util.IterativeProcess
      edu.uci.ics.jung.algorithms.importance.AbstractRanker<V,E>
          edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker<V,E>
              edu.uci.ics.jung.algorithms.importance.PageRank<V,E>

All Implemented Interfaces:

IterativeContext

Direct Known Subclasses:

PageRankWithPriors

Deprecated. As of JUNG 2.0 beta, replaced with PageRank.

public class PageRank<V,E>
extends RelativeAuthorityRanker<V,E>

This algorithm measures the importance of a node in terms of the fraction of time spent at that node relative to all other nodes. This fraction is measured by first transforming the graph into a first-order Markov chain where the transition probability of going from node u to node v is equal to (1-alpha)*[1/outdegree(u)] + alpha*(1/|V|) where |V| is the # of vertices in the graph and alpha is a parameter typically set to be between 0.1 and 0.2 (according to the authors). If u has no out-edges in the original graph then 0 is used instead of 1/outdegree(v). Once the markov chain is created, the stationary probability of being at each node (state) is computed using an iterative update method that is guaranteed to converge if the markov chain is ergodic.

A simple example of usage is:

 PageRank ranker = new PageRank(someGraph,0.15);
 ranker.evaluate();
 ranker.printRankings();
 

Running time: O(|E|*I) where |E| is the number of edges and I is the number of iterations until convergence

Author:

Scott White

See Also:

"The Anatomy of a Large-Scale Hypertextual Web Search Engine by L. Page and S. Brin, 1999"

Field Summary

static String

KEY Deprecated.

Fields inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker

priorRankScoreMap

Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker

edgeRankScores, vertexRankScores

Constructor Summary

	PageRank(DirectedGraph<V,E> graph, double bias) Deprecated. Basic constructor which initializes the algorithm
	PageRank(DirectedGraph<V,E> graph, double bias, Map<E,Number> edgeWeights) Deprecated. Specialized constructor that allows the user to specify an edge key if edges already have user-defined weights assigned to them.
protected	PageRank(DirectedGraph<V,E> graph, double bias, Map<E,Number> edgeWeights, Pair<Set<V>> reachables) Deprecated.

Method Summary

String	getRankScoreKey() Deprecated. The user datum key used to store the rank scores.
protected void	initialize(DirectedGraph<V,E> graph, double bias, Map<E,Number> edgeWeights) Deprecated.
protected void	initializeRankings(Collection<V> reachableVertices, Collection<V> unreachableVertices) Deprecated.
void	reset() Deprecated.
void	step() Deprecated. Evaluate the result of the current iteration.
protected void	updateRankings() Deprecated.

Methods inherited from class edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker

finalizeIterations, getPriorRankScore, getPriors, setPriorRankScore, setPriors

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker

assignDefaultEdgeTransitionWeights, getEdgeRankScore, getEdgeRankScore, getEdgeRankScores, getEdgeRankScores, getEdgeWeight, getEdgeWeights, getGraph, getRankings, getRankScores, getVertexCount, getVertexRankScore, getVertexRankScore, getVertexRankScores, getVertexRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, onFinalize, printRankings, removeEdgeRankScore, removeEdgeRankScore, removeVertexRankScore, removeVertexRankScore, setEdgeRankScore, setEdgeRankScore, setEdgeWeight, setEdgeWeights, setNormalizeRankings, setRemoveRankScoresOnFinalize, setVertexRankScore, setVertexRankScore

Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess

done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, getStatus, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

KEY

public static final String KEY

Deprecated.

See Also:

Constant Field Values

Constructor Detail

PageRank

public PageRank(DirectedGraph<V,E> graph,
                double bias)

Deprecated.

Basic constructor which initializes the algorithm

Parameters:

graph - the graph whose nodes are to be ranked

bias - the value (between 0 and 1) that indicates how much to dampen the underlying markov chain with underlying uniform transitions over all nodes. Generally, values between 0.0-0.3 are used.

PageRank

public PageRank(DirectedGraph<V,E> graph,
                double bias,
                Map<E,Number> edgeWeights)

Deprecated.

Specialized constructor that allows the user to specify an edge key if edges already have user-defined weights assigned to them.

Parameters:

graph - the graph whose nodes are to be ranked

bias - the value (between 0 and 1) that indicates how much to dampen the underlying markov chain with underlying uniform transitions over all nodes. Generally, values between 0.0-0.3 are used.

edgeWeights - if non-null, uses the user-defined weights to compute the transition probabilities; if null then default transition probabilities (1/outdegree(u)) are used

PageRank

protected PageRank(DirectedGraph<V,E> graph,
                   double bias,
                   Map<E,Number> edgeWeights,
                   Pair<Set<V>> reachables)

Deprecated.

Method Detail

initialize

protected void initialize(DirectedGraph<V,E> graph,
                          double bias,
                          Map<E,Number> edgeWeights)

Deprecated.

initializeRankings

protected void initializeRankings(Collection<V> reachableVertices,
                                  Collection<V> unreachableVertices)

Deprecated.

reset

public void reset()

Deprecated.

Overrides:

reset in class AbstractRanker<V,E>

updateRankings

protected void updateRankings()

Deprecated.

step

public void step()

Deprecated.

Description copied from class: IterativeProcess

Evaluate the result of the current iteration.

Specified by:

step in interface IterativeContext

Specified by:

step in class IterativeProcess

getRankScoreKey

public String getRankScoreKey()

Deprecated.

The user datum key used to store the rank scores.

Specified by:

getRankScoreKey in class AbstractRanker<V,E>

Returns:

the key