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

java.lang.Object
  edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer<V,E,S>
      edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors<V,E,Double>
          edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
              edu.uci.ics.jung.algorithms.scoring.PageRank<V,E>

All Implemented Interfaces:

VertexScorer<V,Double>, IterativeContext

Direct Known Subclasses:

EigenvectorCentrality

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

Assigns scores to each vertex according to the PageRank algorithm.

PageRank is an eigenvector-based algorithm. The score for a given vertex may be thought of as the fraction of time spent 'visiting' that vertex (measured over all time) in a random walk over the vertices (following outgoing edges from each vertex). PageRank modifies this random walk by adding to the model a probability (specified as 'alpha' in the constructor) of jumping to any vertex. If alpha is 0, this is equivalent to the eigenvector centrality algorithm; if alpha is 1, all vertices will receive the same score (1/|V|). Thus, alpha acts as a sort of score smoothing parameter.

The original algorithm assumed that, for a given vertex, the probability of following any outgoing edge was the same; this is the default if edge weights are not specified. This implementation generalizes the original by permitting the user to specify edge weights; in order to maintain the original semantics, however, the weights on the outgoing edges for a given vertex must represent transition probabilities; that is, they must sum to 1.

If a vertex has no outgoing edges, then the probability of taking a random jump from that vertex is (by default) effectively 1. If the user wishes to instead throw an exception when this happens, call acceptDisconnectedGraph(false) on this instance.

Typical values for alpha (according to the original paper) are in the range [0.1, 0.2] but may be any value between 0 and 1 inclusive.

See Also:

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

Field Summary

Fields inherited from class edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors

disappearing_potential

Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors

alpha, vertex_priors

Fields inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer

edge_weights, graph, hyperedges_are_self_loops, max_delta, max_iterations, output_reversed, tolerance, total_iterations

Constructor Summary

PageRank(Hypergraph<V,E> graph, double alpha)
Creates an instance for the specified graph and random jump probability; the probability of following any outgoing edge from a given vertex is the same.

PageRank(Hypergraph<V,E> graph, org.apache.commons.collections15.Transformer<E,? extends Number> edge_weight, double alpha)
Creates an instance for the specified graph, edge weights, and random jump probability.

Method Summary

Methods inherited from class edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors

afterStep, collectDisappearingPotential, update

Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorerWithPriors

getAlpha, getVertexPrior, getVertexPriors, initialize

Methods inherited from class edu.uci.ics.jung.algorithms.scoring.AbstractIterativeScorer

acceptDisconnectedGraph, done, evaluate, getAdjustedIncidentCount, getCurrentValue, getEdgeWeight, getEdgeWeights, getIterations, getMaxIterations, getOutputValue, getTolerance, getVertexScore, isDisconnectedGraphOK, setCurrentValue, setEdgeWeights, setHyperedgesAreSelfLoops, setMaxIterations, setOutputValue, setTolerance, step, swapOutputForCurrent, updateMaxDelta

Methods inherited from class java.lang.Object

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

Methods inherited from interface edu.uci.ics.jung.algorithms.scoring.VertexScorer

getVertexScore

Constructor Detail

PageRank

public PageRank(Hypergraph<V,E> graph,
                org.apache.commons.collections15.Transformer<E,? extends Number> edge_weight,
                double alpha)

Creates an instance for the specified graph, edge weights, and random jump probability.

Parameters:

graph - the input graph

edge_weight - the edge weights (transition probabilities)

alpha - the probability of taking a random jump to an arbitrary vertex

PageRank

public PageRank(Hypergraph<V,E> graph,
                double alpha)

Creates an instance for the specified graph and random jump probability; the probability of following any outgoing edge from a given vertex is the same.

Parameters:

graph - the input graph

alpha - the probability of taking a random jump to an arbitrary vertex