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
    See Also:
    PageRank, SpectralRanking
    • 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.