Package it.unimi.dsi.law.rank

Class PageRankGaussSeidel

java.lang.Object
it.unimi.dsi.law.rank.SpectralRanking
it.unimi.dsi.law.rank.PageRank
it.unimi.dsi.law.rank.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 j → i 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 j → i, with j ≠ i, σ += 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 j → i, with j ≠ i, σ += pji xj
      • σ += (A + B − di xi) ui
      • σ = ( (1 − α) vi + ασ ) ⁄ (1 − αpii − αdi ui)
      • if i is dangling
        • B += σ
        • A −= xi
      • xi = σ
Author:
Sebastiano Vigna
See Also:
PageRank, SpectralRanking

  • Field Details

    • pseudoRank

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

  • Constructor Details

    • 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 Details