org.jgrapht.alg.scoring

Class PageRank<V,E>

java.lang.Object

org.jgrapht.alg.scoring.PageRank<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexScoringAlgorithm<V,Double>

public final class PageRank<V,E>
extends Object
implements VertexScoringAlgorithm<V,Double>

PageRank implementation.

The wikipedia article contains a nice description of PageRank. The method can be found on the article: Sergey Brin and Larry Page: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the 7th World-Wide Web Conference, Brisbane, Australia, April 1998. See also the following page.

This is a simple iterative implementation of PageRank which stops after a given number of iterations or if the PageRank values between two iterations do not change more than a predefined value. The implementation uses the variant which divides by the number of nodes, thus forming a probability distribution over graph nodes.

Each iteration of the algorithm runs in linear time $O(n+m)$ when $n$ is the number of nodes and $m$ the number of edges of the graph. The maximum number of iterations can be adjusted by the caller. The default value is MAX_ITERATIONS_DEFAULT.

If the graph is a weighted graph, a weighted variant is used where the probability of following an edge e out of node $v$ is equal to the weight of $e$ over the sum of weights of all outgoing edges of $v$.

Author:

Dimitrios Michail

Field Summary

Fields

Modifier and Type	Field and Description
static double	DAMPING_FACTOR_DEFAULT Damping factor default value.
static int	MAX_ITERATIONS_DEFAULT Default number of maximum iterations.
static double	TOLERANCE_DEFAULT Default value for the tolerance.

Constructor Summary

Constructors

Constructor and Description
PageRank(Graph<V,E> g) Create and execute an instance of PageRank.
PageRank(Graph<V,E> g, double dampingFactor) Create and execute an instance of PageRank.
PageRank(Graph<V,E> g, double dampingFactor, int maxIterations) Create and execute an instance of PageRank.
PageRank(Graph<V,E> g, double dampingFactor, int maxIterations, double tolerance) Create and execute an instance of PageRank.

Method Summary

Modifier and Type	Method and Description
Map<V,Double>	getScores() Get a map with the scores of all vertices
Double	getVertexScore(V v) Get a vertex score

Methods inherited from class java.lang.Object

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

Field Detail

MAX_ITERATIONS_DEFAULT

public static final int MAX_ITERATIONS_DEFAULT

Default number of maximum iterations.

See Also:

Constant Field Values

TOLERANCE_DEFAULT

public static final double TOLERANCE_DEFAULT

Default value for the tolerance. The calculation will stop if the difference of PageRank values between iterations change less than this value.

See Also:

Constant Field Values

DAMPING_FACTOR_DEFAULT

public static final double DAMPING_FACTOR_DEFAULT

Damping factor default value.

See Also:

Constant Field Values

Constructor Detail

PageRank

public PageRank(Graph<V,E> g)

Create and execute an instance of PageRank.

Parameters:

g - the input graph

PageRank

public PageRank(Graph<V,E> g,
                double dampingFactor)

Create and execute an instance of PageRank.

Parameters:

g - the input graph

dampingFactor - the damping factor

PageRank

public PageRank(Graph<V,E> g,
                double dampingFactor,
                int maxIterations)

Create and execute an instance of PageRank.

Parameters:

g - the input graph

dampingFactor - the damping factor

maxIterations - the maximum number of iterations to perform

PageRank

public PageRank(Graph<V,E> g,
                double dampingFactor,
                int maxIterations,
                double tolerance)

Create and execute an instance of PageRank.

Parameters:

g - the input graph

dampingFactor - the damping factor

maxIterations - the maximum number of iterations to perform

tolerance - the calculation will stop if the difference of PageRank values between iterations change less than this value

Method Detail

getScores

public Map<V,Double> getScores()

Get a map with the scores of all vertices

Specified by:

getScores in interface VertexScoringAlgorithm<V,Double>

Returns:

a map with all scores

getVertexScore

public Double getVertexScore(V v)

Get a vertex score

Specified by:

getVertexScore in interface VertexScoringAlgorithm<V,Double>

Parameters:

v - the vertex

Returns:

the score