Module org.jgrapht.core
Package 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,​java.lang.Double>
public final class PageRank<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.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 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 Description
    PageRank​(Graph<V,​E> graph)
    Create and execute an instance of PageRank.
    PageRank​(Graph<V,​E> graph, double dampingFactor)
    Create and execute an instance of PageRank.
    PageRank​(Graph<V,​E> graph, double dampingFactor, int maxIterations)
    Create and execute an instance of PageRank.
    PageRank​(Graph<V,​E> graph, double dampingFactor, int maxIterations, double tolerance)
    Create and execute an instance of PageRank.

  • Method Summary

    Modifier and Type Method Description
    java.util.Map<V,​java.lang.Double> getScores()
    Get a map with the scores of all vertices
    java.lang.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 Details

  • Constructor Details

    • PageRank

      public PageRank​(Graph<V,​E> graph)
      Create and execute an instance of PageRank.
      Parameters:
      graph - the input graph

    • PageRank

      public PageRank​(Graph<V,​E> graph, double dampingFactor)
      Create and execute an instance of PageRank.
      Parameters:
      graph - the input graph
      dampingFactor - the damping factor

    • PageRank

      public PageRank​(Graph<V,​E> graph, double dampingFactor, int maxIterations)
      Create and execute an instance of PageRank.
      Parameters:
      graph - the input graph
      dampingFactor - the damping factor
      maxIterations - the maximum number of iterations to perform

    • PageRank

      public PageRank​(Graph<V,​E> graph, double dampingFactor, int maxIterations, double tolerance)
      Create and execute an instance of PageRank.
      Parameters:
      graph - 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 Details