- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexScoringAlgorithm<V,
Double>
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$.
-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final double
Damping factor default value.private final double
The damping factorThe input graphstatic final int
Default number of maximum iterations.private final int
Maximum iterations to runThe resultprivate final double
The calculation will stop if the difference of PageRank values between iterations change less than this valuestatic final double
Default value for the tolerance. -
Constructor Summary
ConstructorsConstructorDescriptionCreate and execute an instance of PageRank.Create and execute an instance of PageRank.Create and execute an instance of PageRank.Create and execute an instance of PageRank. -
Method Summary
-
Field Details
-
MAX_ITERATIONS_DEFAULT
public static final int MAX_ITERATIONS_DEFAULTDefault number of maximum iterations.- See Also:
-
TOLERANCE_DEFAULT
public static final double TOLERANCE_DEFAULTDefault value for the tolerance. The calculation will stop if the difference of PageRank values between iterations change less than this value.- See Also:
-
DAMPING_FACTOR_DEFAULT
public static final double DAMPING_FACTOR_DEFAULTDamping factor default value.- See Also:
-
graph
The input graph -
dampingFactor
private final double dampingFactorThe damping factor -
maxIterations
private final int maxIterationsMaximum iterations to run -
tolerance
private final double toleranceThe calculation will stop if the difference of PageRank values between iterations change less than this value -
scores
The result
-
-
Constructor Details
-
PageRank
Create and execute an instance of PageRank.- Parameters:
graph
- the input graph
-
PageRank
Create and execute an instance of PageRank.- Parameters:
graph
- the input graphdampingFactor
- the damping factor
-
PageRank
Create and execute an instance of PageRank.- Parameters:
graph
- the input graphdampingFactor
- the damping factormaxIterations
- the maximum number of iterations to perform
-
PageRank
Create and execute an instance of PageRank.- Parameters:
graph
- the input graphdampingFactor
- the damping factormaxIterations
- the maximum number of iterations to performtolerance
- the calculation will stop if the difference of PageRank values between iterations change less than this value
-
-
Method Details
-
getScores
Get a map with the scores of all vertices- Specified by:
getScores
in interfaceVertexScoringAlgorithm<V,
E> - Returns:
- a map with all scores
-
getVertexScore
Get a vertex score- Specified by:
getVertexScore
in interfaceVertexScoringAlgorithm<V,
E> - Parameters:
v
- the vertex- Returns:
- the score
-