Class 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 ≥ 0M)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 Detail

      • MIN_SCALE

        public static final double MIN_SCALE
        Below this scale, we stop the iterative process.
        See Also:
        Constant Field Values
      • 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 Detail

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