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

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

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.

Method Summary

java.lang.String

getRankScoreKey() The user datum key used to store the rank scores.

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

setPriorRankScore

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

getEdgeWeightKeyName, getRankings, getRankScore, getRankScores, isRankingNodes, printRankings, setNormalizeRankings, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey

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

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

Methods inherited from class java.lang.Object

equals, 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

Method Detail

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