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 − α) vk ≥ 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:
  • Field Details


      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.
    • buckets

      public BitSet buckets
      If not null, the set of buckets of SpectralRanking.graph.
    • stronglyPreferential

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

    • PageRank

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

    • buildProperties

      public Properties buildProperties​(String graphBasename, String preferenceFilename, String danglingFilename)
      Returns a Properties object that contains all the parameters used by the computation.
      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.
      a properties object that represent all the parameters used to calculate the rank.
    • init

      public void init() throws IOException
      Basic initialization: we log the damping factor, check that the preference vector is correctly sized and stochastic, fill SpectralRanking.rank with the preference vector and set the dangling-node distribution depending on the value of stronglyPreferential.
      init in class SpectralRanking