# 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`

## Nested classes/interfaces inherited from class it.unimi.dsi.law.rank.SpectralRanking

`SpectralRanking.IterationNumberStoppingCriterion, SpectralRanking.NormStoppingCriterion, SpectralRanking.StoppingCriterion`
• ## Field Summary

Fields
Modifier and Type Field Description
`String` `coeffBasename`
If not `null`, the basename for coefficents.
`double[][]` `derivative`
The value of derivatives (only for the subset of nodes specified in `subset`, if not `null`).
`int[]` `order`
The order of the derivatives.
`double[]` `previousRank`
The rank vector after the last iteration (only meaningful after at least one step).
`int[]` `subset`
If not `null`, the subset of nodes over which the derivatives should be computed.

### Fields inherited from class it.unimi.dsi.law.rank.PageRank

`alpha, buckets, danglingNodeDistribution, DEFAULT_ALPHA, preference, stronglyPreferential`

### Fields inherited from class it.unimi.dsi.law.rank.SpectralRanking

`DEFAULT_MAX_ITER, DEFAULT_NORM, DEFAULT_THRESHOLD, graph, iteration, logger, n, rank, STOCHASTIC_TOLERANCE`
• ## Constructor Summary

Constructors
Constructor Description
`PageRankPowerSeries​(ImmutableGraph graph)`
Creates a new instance.
```PageRankPowerSeries​(ImmutableGraph graph, Logger logger)```
Creates a new instance.
• ## Method Summary

Modifier and Type Method Description
`void` `clear()`
Clears all data and releases resources by nulling `SpectralRanking.rank` (i.e., results we no longer be available).
`void` `init()`
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 `PageRank.stronglyPreferential`.
`static void` `main​(String[] arg)`
`double` `normDelta()`
Returns the norm of an estimation of the distance to the limit of the iterative process: depending on the implementation, this can be an actual bound or, for example, just the difference between the last two approximations.
`void` `step()`
Performs one computation step.
`void` `stepUntil​(SpectralRanking.StoppingCriterion stoppingCriterion)`
Calls `SpectralRanking.init()` and steps until a given stopping criterion is met.

### Methods inherited from class it.unimi.dsi.law.rank.PageRank

`buildProperties`

### Methods inherited from class it.unimi.dsi.law.rank.SpectralRanking

`and, approximateNormVector, buildProperties, isStochastic, or`

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ## 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

• ### init

public void init() throws IOException
Description copied from class: `PageRank`
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 `PageRank.stronglyPreferential`.
Overrides:
`init` in class `PageRank`
Throws:
`IOException`
• ### step

public void step() throws IOException
Description copied from class: `SpectralRanking`
Performs one computation step.
Specified by:
`step` in class `SpectralRanking`
Throws:
`IOException`
• ### stepUntil

public void stepUntil​(SpectralRanking.StoppingCriterion stoppingCriterion) throws IOException
Description copied from class: `SpectralRanking`
Calls `SpectralRanking.init()` and steps until a given stopping criterion is met. The criterion is checked a posteriori (i.e., after each step); this means that at least one step is performed.
Overrides:
`stepUntil` in class `SpectralRanking`
Parameters:
`stoppingCriterion` - the stopping criterion to be used.
Throws:
`IOException`
• ### normDelta

public double normDelta()
Description copied from class: `SpectralRanking`
Returns the norm of an estimation of the distance to the limit of the iterative process: depending on the implementation, this can be an actual bound or, for example, just the difference between the last two approximations.

This method must be implemented by concrete subclasses if you want to use `SpectralRanking.NormStoppingCriterion`.

Overrides:
`normDelta` in class `SpectralRanking`
Returns:
the norm of an estimation of the distance to the limit.
• ### clear

public void clear()
Description copied from class: `SpectralRanking`
Clears all data and releases resources by nulling `SpectralRanking.rank` (i.e., results we no longer be available). Please extend this method to handle additional attributes.
Overrides:
`clear` in class `SpectralRanking`
• ### main

public static void main​(String[] arg) throws
Throws:
`IOException`
`JSAPException`
`ClassNotFoundException`
`ConfigurationException`