Package 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,​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

    • 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

      All Methods Instance Methods Concrete Methods 
      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 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> 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 Detail

      • getScores

        public java.util.Map<V,​java.lang.Double> getScores()
        Get a map with the scores of all vertices
        Specified by:
        getScores in interface VertexScoringAlgorithm<V,​E>
        Returns:
        a map with all scores

      • getVertexScore

        public java.lang.Double getVertexScore​(V v)
        Get a vertex score
        Specified by:
        getVertexScore in interface VertexScoringAlgorithm<V,​E>
        Parameters:
        v - the vertex
        Returns:
        the score