Package it.unimi.dsi.law.rank

Class PageRankPowerSeries

java.lang.Object
it.unimi.dsi.law.rank.SpectralRanking
it.unimi.dsi.law.rank.PageRank
it.unimi.dsi.law.rank.PageRankPowerSeries
public class PageRankPowerSeries
extends PageRank
Computes PageRank (and possibly its derivatives in the damping factor) using its power series.

PageRank has a power series expansion in α (see PageRank for definitions):

r = v + v∑n≥1αn( (P + dTu)n − (P + dTu)n−1 )

In “PageRank: Functional dependencies”, by Paolo Boldi, Massimo Santini, and Sebastiano Vigna, ACM Trans. Inf. Sys., 27(4):1−23, 2009, we show that the truncation of order k of the power series is exactly the value attained by the power method using v as starting vector. This class exploits the equivalence to compute iteratively the Maclaurin polynomials of order k:

r(k) = v ( α P + α dTu + (1−α)1T v )k = v + v∑1≤n≤k αn( (P + dTu)n − (P + dTu)n−1 ).

The remainder (i.e., the difference with PageRank) at the k-th iteration can be bounded exactly using the norm of the difference r(k) − r(k−1), as

r − r(k) = v∑n≥k+1 αn( (P + dTu)n − (P + dTu)n−1 ) = v αk( (P + dTu)k − (P + dTu)k−1 ) ∑n≥1αn(P + dTu)n = (r(k) − r(k−1)) ∑n≥1αn(P + dTu)n.

Hence,

‖r − r(k)‖1 ≤ ‖r(k) − r(k−1)‖1 ‖∑n≥1αn(P + dTu)n‖1 ≤ ‖r(k) − r(k−1)‖1 α / (1 − α),
and this is the value returned by normDelta().

It is worth remarking that a folklore justification for convergence, that is, the spectral gap between the dominant eigenvalue and the second eigenvalue, does not apply directly to PageRank, as it is applicable only to normal (i.e., diagonalizable) matrices. The inequality above, instead, makes it possible to bound in a precise manner the error in the current estimation.

Note that

r(t+1) = r(t) (α P + α dTu + (1−α)1T v) = αr(t) P + α r(t)d u + (1−α) v.

The latter formula means that

ri(t+1)= α∑j → i pjirj(t) + ακui + (1−α)vi,
where κ is the sum of rj(t) over all dangling nodes. This is the formula used in the code.

The attribute previousRank represents the ranking at the previous step.

Derivatives and coefficients of the Maclaurin polynomials

Using results from “PageRank: Functional dependencies”, by Paolo Boldi, Massimo Santini, and Sebastiano Vigna, ACM Trans. Inf. Sys., 27(4):1−23, 2009, this class is able also to approximate the derivatives of PageRank in α, and to compute, for each node, the coefficients of Maclaurin polynomials. You have to set a non-empty order array specifying the order of the derivatives desired, or a basename for the coefficients, respectively . The derivatives will be evaluated (as PageRank is) in the value set for α.

See Also:
PageRank, SpectralRanking

  • Field Details

    • previousRank

      public double[] previousRank
      The rank vector after the last iteration (only meaningful after at least one step).

    • subset

      public int[] subset
      If not null, the subset of nodes over which the derivatives should be computed.

    • derivative

      public double[][] derivative
      The value of derivatives (only for the subset of nodes specified in subset, if not null).

    • order

      public int[] order
      The order of the derivatives. Must be non-null, but it can be the empty array.

    • coeffBasename

      public String coeffBasename
      If not null, the basename for coefficents.

  • Constructor Details

    • PageRankPowerSeries

      public PageRankPowerSeries​(ImmutableGraph graph, Logger logger)
      Creates a new instance.
      Parameters:
      graph - the graph.
      logger - a logger that will be passed to super().

    • PageRankPowerSeries

      public PageRankPowerSeries​(ImmutableGraph graph)
      Creates a new instance.
      Parameters:
      graph - the graph.

  • Method Details