## Class PageRankGaussSeidel

• ```public class PageRankGaussSeidel
extends PageRank```
Computes PageRank of a graph using the Gauß–Seidel method. This class is now mainly of historical interest, as `PageRankParallelGaussSeidel` is faster and provides exact bounds via vector norms.

The general formula described in `PageRank` can be rewritten as the following linear system:

x (I − α (P + uTd)) = (1 − α)v.

The system

x M = b
can be solved using the Gauss−Seidel method, which updates in-place a single vector, using the formula
xi(t+1) = ( biΣj<i mijxj(t+1)Σj>i mijxj(t) ) mii.

The `normDelta()` method returns an upper bound to the ℓ1 norm of the error, obtained multiplying by α / (1 − α) the ℓ1 norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).

Warning: Since we need to enumerate the predecessors a node, you must pass to the constructor the transpose of the graph.

Substituting to M and to b the corresponding terms present in the first formula, we obtain the following update rule:

xi(t+1) = ( (1 − α) vi + α ( Σj<i (pji + uidj) xj(t+1) + Σj>i (pji + uidj) xj(t) ) ) (1 − αpii − αuidi)

We can rearrange the previous formula sums in two different sums: one for the nodes ji and one for the dangling nodes (nondangling nodes that are not predecessors of i give no contribution). So the Gauß–Seidel method can be implemented as follows:

• initialize x as the uniform vector;
• while some stopping criterion has not been met,
• for all i = 0,1,…, N−1
• σ = 0;
• for all ji, with ji, σ += pji xj
• for all dangling j, σ += ui xj
• xi = ( (1 − α) vi + ασ ) (1 − αpii − αdiui)

Remember that ui is 1⁄n when the weakly preferential version of the PageRank formula is considered, vi when the version is the strongly preferential one.

The second “for all” can be avoided if we keep track of the summation of all ranks of dangling nodes up to index i (exclusive) and for all dangling nodes from index i on in two variables B (before i) and A (after i):

• initialize x as the uniform vector;
• B = 0;
• for all dangling j, A += xj;
• while some stopping criterion has not been met,
• for all i = 0,1,…,N−1
• σ = 0;
• for all ji, with ji, σ += pji xj
• σ += (A + Bdi xi) ui
• σ = ( (1 − α) vi + ασ ) (1 − αpii − αdi ui)
• if i is dangling
• B += σ
• A −= xi
• xi = σ
Author:
Sebastiano Vigna
`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
`boolean` `pseudoRank`
If true, an everywhere zero dangling-node distribution will be simulated, resulting in the computation of a pseudorank.
• ### 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
Modifier Constructor Description
` ` `PageRankGaussSeidel​(ImmutableGraph transpose)`
Creates a new instance.
`protected ` ```PageRankGaussSeidel​(ImmutableGraph transpose, 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()`
Return an upper bound to the ℓ1 norm of the error, obtained multiplying by α / (1 − α) the ℓ1 norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).
`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 Detail

• #### pseudoRank

`public boolean pseudoRank`
If true, an everywhere zero dangling-node distribution will be simulated, resulting in the computation of a pseudorank.
• ### Constructor Detail

• #### PageRankGaussSeidel

```protected PageRankGaussSeidel​(ImmutableGraph transpose,
Logger logger)```
Creates a new instance.
Parameters:
`transpose` - the transpose of the graph on which to compute PageRank.
`logger` - a logger that will be passed to `super()`.
• #### PageRankGaussSeidel

`public PageRankGaussSeidel​(ImmutableGraph transpose)`
Creates a new instance.
Parameters:
`transpose` - the transpose of the graph on which to compute PageRank.
• ### Method Detail

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

`public double normDelta()`
Return an upper bound to the ℓ1 norm of the error, obtained multiplying by α / (1 − α) the ℓ1 norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).
Overrides:
`normDelta` in class `SpectralRanking`
Returns:
an upper bound to the ℓ1 norm of the error.
• #### step

`public void step()`
Description copied from class: `SpectralRanking`
Performs one computation step.
Specified by:
`step` in class `SpectralRanking`
• #### 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`
• #### main

```public static void main​(String[] arg)
throws IOException,
JSAPException,
org.apache.commons.configuration.ConfigurationException,
ClassNotFoundException```
Throws:
`IOException`
`JSAPException`
`org.apache.commons.configuration.ConfigurationException`
`ClassNotFoundException`