edu.uci.ics.jung.algorithms.importance

Class PageRank

java.lang.Object

edu.uci.ics.jung.algorithms.IterativeProcess

edu.uci.ics.jung.algorithms.importance.AbstractRanker

edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker

edu.uci.ics.jung.algorithms.importance.PageRank

Direct Known Subclasses:

PageRankWithPriors

public class PageRank
extends RelativeAuthorityRanker

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

Fields

Modifier and Type	Field and Description
static java.lang.String	KEY

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

PRIOR_KEY

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

DEFAULT_EDGE_WEIGHT_KEY

Constructor Summary

Constructors

Modifier	Constructor and Description
	PageRank(DirectedGraph graph, double bias) Basic constructor which initializes the algorithm
	PageRank(DirectedGraph graph, double bias, java.lang.String edgeWeightKeyName) Specialized constructor that allows the user to specify an edge key if edges already have user-defined weights assigned to them.
protected	PageRank(DirectedGraph graph, double bias, java.lang.String edgeWeightKeyName, Pair reachables)

Method Summary

Methods

Modifier and Type	Method and Description
protected double	evaluateIteration() Evaluate the result of the current interation.
java.lang.String	getRankScoreKey() The user datum key used to store the rank scores.
protected void	initialize(DirectedGraph graph, double bias, java.lang.String edgeWeightKeyName)
protected void	initializeRankings(java.util.Set reachableVertices, java.util.Set unreachableVertices)
protected void	reinitialize()
protected void	updateRankings()

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

finalizeIterations, getPriorRankScore, getPriorRankScoreKey, getPriors, setPriorRankScore, setPriors

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

assignDefaultEdgeTransitionWeights, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScore, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, onFinalize, printRankings, setEdgeWeight, setNormalizeRankings, setRankScore, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey

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

evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations

Methods inherited from class java.lang.Object

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

Field Detail

KEY

public static final java.lang.String KEY

See Also:

Constant Field Values

Constructor Detail

PageRank

public PageRank(DirectedGraph graph,
        double bias)

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 graph,
        double bias,
        java.lang.String edgeWeightKeyName)

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.

edgeWeightKeyName - 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 graph,
        double bias,
        java.lang.String edgeWeightKeyName,
        Pair reachables)

Method Detail

initialize

protected void initialize(DirectedGraph graph,
              double bias,
              java.lang.String edgeWeightKeyName)

initializeRankings

protected void initializeRankings(java.util.Set reachableVertices,
                      java.util.Set unreachableVertices)

reinitialize

protected void reinitialize()

Overrides:

reinitialize in class AbstractRanker

updateRankings

protected void updateRankings()

evaluateIteration

protected double evaluateIteration()

Description copied from class: IterativeProcess

Evaluate the result of the current interation.

Specified by:

evaluateIteration in class IterativeProcess

Returns:

the estimated precision of the result.

getRankScoreKey

public java.lang.String getRankScoreKey()

The user datum key used to store the rank scores.

Specified by:

getRankScoreKey in class AbstractRanker

Returns:

the key