org.jgrapht.alg.scoring

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

Since:
August 2016
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

All Methods
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.
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.
Constant Field Values
• #### DAMPING_FACTOR_DEFAULT

`public static final double DAMPING_FACTOR_DEFAULT`
Damping factor default value.
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