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,java.lang.Double>
-
- edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors<V,E>
-
- edu.uci.ics.jung.algorithms.scoring.PageRank<V,E>
-
- All Implemented Interfaces:
VertexScorer<V,java.lang.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
Constructors Constructor Description 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, com.google.common.base.Function<E,? extends java.lang.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, com.google.common.base.Function<E,? extends java.lang.Number> edge_weight, double alpha)
Creates an instance for the specified graph, edge weights, and random jump probability.- Parameters:
graph
- the input graphedge_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 graphalpha
- the probability of taking a random jump to an arbitrary vertex
-
-