Package it.unimi.dsi.law.rank

Class PowerSeries

java.lang.Object
it.unimi.dsi.law.rank.SpectralRanking
it.unimi.dsi.law.rank.PowerSeries
public class PowerSeries
extends SpectralRanking
Computes a power series on a graph using a parallel implementation.

This class is a generic power series approximator. It computes iteratively finite truncations of power series of the form

v ∑k ≥ 0 (αM)k.
where v is a preference vector that defaults to 1, and M is the graph adjacency matrix, possibly with stochasticised rows if markovian is true. Note that the step() method is not available: due to the need for some synchronization logic, only stepUntil(StoppingCriterion) is available.

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

This class can be run using two different stopping criteria:

  • MAX_RATIO_STOPPING_CRITERION stops when the maximum ratio between a component of the vector given by the previous approximation multiplied by M and the respective component in the previous approximation is smaller than the reciprocal of α;
  • SpectralRanking.NormStoppingCriterion stops when normDelta(), which returns the ℓ∞ norm of the difference between the two last approximations, is below a specified threshold.

In the first case, this class computes suitable vectors that can be used to control the error of Gauß–Seidel's method applied to Katz's index or PageRank. Details about the method are described by Sebastiano Vigna in “Supremum-Norm Convergence for Step-Asynchronous Successive Overrelaxation on M-matrices“, 2014.

In the second case, we compute Katz's index, or a pseudorank divided by 1 − α (in both cases, the computation converges more slowly than using KatzParallelGaussSeidel or even PageRankParallelPowerSeries, so this feature is of marginal interest).

At the end of the computation, scale contains the scaling that has been applied to the result so that it is normalized in ℓ∞ norm. It is possible to obtain the unscaled result dividing all components of the results by scale. Note that when using the MAX_RATIO_STOPPING_CRITERION if the parameter alpha is not smaller than the reciprocal of the dominant eigenvalue the computation will stop with an error either because a lower bound proves this fact, or because the scale will go below MIN_SCALE (the latter event might also be due to a very bad non-normal transient behaviour, but this shouldn't happen with real, non-pathological data).

During the computation, the maximum and minimum ratios between a component of the vector given by the previous approximation multiplied by M and the respective component in the previous approximation are printed; they provide upper and lower bounds to the dominant eigenvalue by Collatz's theorem. At the end of the computation, the current bounds can be found in maxRatio and minRatio.

Warning: if the computation stops because of the MAX_RATIO_STOPPING_CRITERION, the vector suitable for maxRatio is stored in previousRank, not in rank, as the maximum ratio was evaluated for previousRank while rank was computed. Moreover, if you provided a preference vector with some zero component, you must check manually that the suitable vector obtained contains no zero entries.

Author:
Sebastiano Vigna
See Also:
SpectralRanking

  • Field Details

    • MIN_SCALE

      public static final double MIN_SCALE
      Below this scale, we stop the iterative process.
      See Also:
      Constant Field Values

    • MAX_RATIO_STOPPING_CRITERION

      public static SpectralRanking.StoppingCriterion MAX_RATIO_STOPPING_CRITERION
      A stopping criterion that stops when maxRatio is smaller than the reciprocal of alpha.

      Note that this criterion can be applied to instances of PowerSeries only.

    • maxRatio

      public double maxRatio
      The maximum ratio between components.

    • minRatio

      public double minRatio
      The minimum ratio between components.

    • alpha

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

    • markovian

      public boolean markovian
      If true, the matrix adjacency graph will be stochasticised, thus computing a pseudorank.

    • scale

      public double scale
      The overall scaling that has been applied to the current approximation.

    • preference

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

    • previousRank

      public double[] previousRank
      The approximation obtained after the last iteration (only meaningful after at least one step).

  • Constructor Details

    • PowerSeries

      public PowerSeries​(ImmutableGraph transpose, int requestedThreads, Logger logger)
      Creates a new instance.
      Parameters:
      transpose - the tranpose of the graph on which the power series must be computed.
      requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).
      logger - a logger that will be passed to super().

    • PowerSeries

      public PowerSeries​(ImmutableGraph transpose, int requestedThreads)
      Creates a new instance.
      Parameters:
      transpose - the tranpose of the graph on which the power series must be computed.
      requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).

    • PowerSeries

      public PowerSeries​(ImmutableGraph transpose, Logger logger)
      Creates a new instance.
      Parameters:
      transpose - the tranpose of the graph on which the power series must be computed.
      logger - a logger that will be passed to super().

    • PowerSeries

      public PowerSeries​(ImmutableGraph transpose)
      Creates a new instance.
      Parameters:
      transpose - the tranpose of the graph on which the power series must be computed.

  • Method Details