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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker
          extended by edu.uci.ics.jung.algorithms.importance.RelativeAuthorityRanker
              extended by 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
static 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
  PageRank(DirectedGraph graph, double bias)
          Basic constructor which initializes the algorithm
  PageRank(DirectedGraph graph, double bias, 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, String edgeWeightKeyName, Pair reachables)
           
 
Method Summary
protected  double evaluateIteration()
          Evaluate the result of the current interation.
 String getRankScoreKey()
          The user datum key used to store the rank scores.
protected  void initialize(DirectedGraph graph, double bias, String edgeWeightKeyName)
           
protected  void initializeRankings(Set reachableVertices, 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 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,
                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,
                   String edgeWeightKeyName,
                   Pair reachables)
Method Detail

initialize

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

initializeRankings

protected void initializeRankings(Set reachableVertices,
                                  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 String getRankScoreKey()
The user datum key used to store the rank scores.

Specified by:
getRankScoreKey in class AbstractRanker
Returns:
the key