Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD