Class 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 + vn1α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 + v1≤nk α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

rr(k) = vnk+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,

rr(k)1 ≤ ‖r(k) − r(k−1)1 ‖∑n≥1αn(P + dTu)n1 ≤ ‖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)= α∑ji 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 α.

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.