Class PageRank

  • Direct Known Subclasses:
    PageRankGaussSeidel, PageRankParallelGaussSeidel, PageRankParallelPowerSeries, PageRankPowerSeries, PageRankPush

    public abstract class PageRank
    extends SpectralRanking
    An abstract class defining methods and attributes supporting PageRank computations. Provides settable damping factor, preference vector and starting vector.

    Formulae and preferences

    There are two main formulae for PageRank in the literature. The first one, which we shall call weakly preferential, patches all dangling nodes by adding a uniform transition towards all other nodes. The second one, which we shall call strongly preferential, patches all dangling nodes adding transitions weighted following the preference vector v. We can consider the two formulae together, letting u be a vector that is uniform in the weak case and coincides with v in the strong case.

    If we denote with P the normalised adjacency matrix of the graph, with d the characteristic vector of dangling nodes, and with α the damping factor, the generic equation is

    x = xP + α dTu + (1 − α) 1T v),
    which, distributing over the sum, makes it possible to express PageRank as
    (1 − α) v( P + dTu )-1,
    or even
    (1 − α) v Σk ≥ 0 αk ( P + dTu )k.

    By default, weakly preferential PageRank is computed; strongly preferential PageRank computation is enforced by setting stronglyPreferential to true.

    See Also:
    SpectralRanking
    • Field Detail

      • DEFAULT_ALPHA

        public static final double DEFAULT_ALPHA
        The default damping factor.
        See Also:
        Constant Field Values
      • alpha

        public double alpha
        The damping factor. In the random surfer interpretation, this is the probability that the surfer will follow a link in the current page.
      • preference

        public DoubleList preference
        The preference vector to be used (or null if the uniform preference vector should be used).
      • danglingNodeDistribution

        public DoubleList danglingNodeDistribution
        The vector used used to patch null rows of the adjacency matrix (u in the general formula). It coincides with the preference vector if stronglyPreferential is true. If null, the uniform distribution will be used.
      • stronglyPreferential

        public boolean stronglyPreferential
        Decides whether we use the strongly or weakly (the default) preferential algorithm.
    • Constructor Detail

      • PageRank

        public PageRank​(ImmutableGraph g,
                        Logger logger)
        Creates a new instance.
        Parameters:
        g - the graph.
        logger - a logger.
    • Method Detail

      • buildProperties

        public Properties buildProperties​(String graphBasename,
                                          String preferenceFilename,
                                          String danglingFilename)
        Returns a Properties object that contains all the parameters used by the computation.
        Parameters:
        graphBasename - the basename of the graph.
        preferenceFilename - the filename of preference vector. It can be null.
        danglingFilename - the filename of dangling-node distribution. It can be null.
        Returns:
        a properties object that represent all the parameters used to calculate the rank.