Package it.unimi.dsi.law.rank

Class KatzParallelGaussSeidel

java.lang.Object
it.unimi.dsi.law.rank.SpectralRanking
it.unimi.dsi.law.rank.KatzParallelGaussSeidel
public class KatzParallelGaussSeidel
extends SpectralRanking
Computes Katz's index using a parallel implementation of the Gauß–Seidel method; this is the implementation of choice to be used when computing Katz's index. It uses less memory (just one vector of doubles) and, experimentally, converges faster than any other implementation. Moreover, it scales linearly with the number of cores.

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

This class approximates the infinite summation

v ∑k ≥ 0 (αG)k = v(1 − αG)-1
by solving iteratively the linear system
x (1 − αG) = v,
where v is a preference vector that defaults to 1, and G is the graph adjacency matrix. Note that the step() method is not available: due to the need for some synchronization logic, only stepUntil(StoppingCriterion) is available.

Technically, the iteration performed by this class is a step-asynchronous Gauß–Seidel iteration: we simply start a number of threads, and each thread updates a value using a Gauß–Seidel-like rule. As a result, each update uses some old and some new values: in other words, the regular splitting

M − N = 1 − αG
of the matrix associated to each update is always different (in a Gauß–Seidel iteration, M is upper triangular, and N is strictly lower triangular). Nonetheless, it is easy to check that M is still (up to permutation) upper triangular and invertible, independently of the specific update sequence.

normDelta() returns the following values:

  • if a suitable norm vector has been set, an upper bound on the error (the ℓ∞ distance from the rank to be computed);
  • otherwise, an estimate of the ℓ∞ norm of the residual obtained by multiplying the ℓ∞ norm of the difference between the last two approximations by the ℓ∞ norm of αG (i.e., the maximum indegree multiplied by α).

To be able to set a norm vector, you need to use PowerSeries to compute a suitable vector. To do so, you must provide an α and use the PowerSeries.MAX_RATIO_STOPPING_CRITERION. If the computation terminates without errors with maximum ratio σ, the resulting vector can be used with this class for all α < 1 / σ (strictness is essential). Note that this is the only way to obtain a bound on the error (unless your graph is so small that you can evaluate the ℓ∞ norm of (1 − αG)-1 and use it to bound the error using the residual). Details about the method are described by Sebastiano Vigna in “Supremum-Norm Convergence for Step-Asynchronous Successive Overrelaxation on M-matrices“, 2014.

Author:
Sebastiano Vigna
See Also:
PageRank, SpectralRanking, PowerSeries

  • Field Details

    • alpha

      public double alpha
      The attenuation factor. Must be smaller than the reciprocal of the dominant eigenvalue.

    • preference

      public DoubleList preference
      The preference vector to be used (or null if the uniform preference vector should be used).

  • Constructor Details

    • KatzParallelGaussSeidel

      public KatzParallelGaussSeidel​(ImmutableGraph transpose, int requestedThreads, Logger logger)
      Creates a new instance.
      Parameters:
      transpose - the transpose of the graph on which to compute Katz's index.
      requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).
      logger - a logger that will be passed to super().

    • KatzParallelGaussSeidel

      public KatzParallelGaussSeidel​(ImmutableGraph transpose)
      Creates a new instance.
      Parameters:
      transpose - the transpose of the graph on which to compute Katz's index.

  • Method Details

    • normVector

      public void normVector​(String normVectorFilename, double sigma) throws IOException
      Sets the norm vector.
      Parameters:
      normVectorFilename - a file containing a norm vector as a list of doubles in DataInput format, or null for no norm vector.
      sigma - the value for which the provided norm vector is suitable.
      Throws:
      IOException

    • normVector

      public void normVector​(double[] normVector, double sigma)
      Sets the norm vector.
      Parameters:
      normVector - the new norm vector.
      sigma - the value for which the provided norm vector is suitable.

    • init

      public void init() throws IOException
      Description copied from class: SpectralRanking
      Initializes the rank vector, zeroes SpectralRanking.iteration and logs basic data. Please extend this method to handle additional attributes.
      Overrides:
      init in class SpectralRanking
      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.

    • buildProperties

      public Properties buildProperties​(String graphBasename, String preferenceFilename)
      Returns a Properties object that contains all the parameters used by the computation.
      Parameters:
      graphBasename - file name of the graph
      preferenceFilename - file name of preference vector. It can be null.
      Returns:
      a properties object that represent all the parameters used to calculate the rank.

    • main

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