Package it.unimi.dsi.law.big.rank

Class SpectralRanking

java.lang.Object
it.unimi.dsi.law.big.rank.SpectralRanking
Direct Known Subclasses:
PageRank
public abstract class SpectralRanking
extends Object
A big version of SpectralRanking.
Author:
Sebastiano Vigna
See Also:
SpectralRanking

  • Field Details

    • DEFAULT_THRESHOLD

      public static final double DEFAULT_THRESHOLD
      Default threshold (note that this value is used as a default by main methods).
      See Also:
      Constant Field Values

    • DEFAULT_MAX_ITER

      public static final int DEFAULT_MAX_ITER
      Default maximum number of iterations (note that this value is used as a default by main methods).
      See Also:
      Constant Field Values

    • DEFAULT_NORM

      public static final Norm DEFAULT_NORM
      The default norm (Norm.L_INFINITY).

    • STOCHASTIC_TOLERANCE

      protected static final double STOCHASTIC_TOLERANCE
      The admitted tolerance in the verification that a vector is a stochastic one. A stochastic vector is nonnegative and has ℓ1 norm equal to 1 ± STOCHASTIC_TOLERANCE.
      See Also:
      Constant Field Values

    • graph

      public final ImmutableGraph graph
      The graph.

    • n

      public final long n
      The number of nodes of graph, cached.

    • logger

      public final Logger logger
      A logger defined by the implementing subclasses.

    • rank

      public double[][] rank
      The current rank vector.

    • iteration

      public int iteration
      The current step (0 after initialization).

  • Constructor Details

    • SpectralRanking

      public SpectralRanking​(ImmutableGraph graph, Logger logger)
      Creates a new instance.
      Parameters:
      graph - the graph.
      logger - a logger.

  • Method Details

    • and

      public static SpectralRanking.StoppingCriterion and​(SpectralRanking.StoppingCriterion stop1, SpectralRanking.StoppingCriterion stop2)
      Composes two stopping criteria, producing a single stopping criterion (the computation stops iff both conditions become true; lazy boolean evaluation is applied).
      Parameters:
      stop1 - a stopping criterion.
      stop2 - a stopping criterion.
      Returns:
      a criterion that decides to stop as soon as both criteria are satisfied.

    • or

      public static SpectralRanking.StoppingCriterion or​(SpectralRanking.StoppingCriterion stop1, SpectralRanking.StoppingCriterion stop2)
      Composes two stopping criteria, producing a single stopping criterion (the computation stops iff either condition becomes true; lazy boolean evaluation is applied).
      Parameters:
      stop1 - a stopping criterion.
      stop2 - a stopping criterion.
      Returns:
      a criterion that decides to stop as soon as one of the two criteria is satisfied.

    • isStochastic

      protected static boolean isStochastic​(DoubleBigList v)
      Commodity method checking whether a vector is stochastic (nonnegative entries summing up to one within STOCHASTIC_TOLERANCE).

      This method uses Kahan's summation algorithm.

      Parameters:
      v - the vector to check.
      Returns:
      true if the vector is stochastic.

    • buildProperties

      public Properties buildProperties​(String graphBasename)
      Returns a Properties object that contains all parameters used by the computation.

      Implementing subclasses should extends this method by calling super() and setting additional properties on the resulting Properties.

      Parameters:
      graphBasename - basename of the graph
      Returns:
      a properties object that represent all the parameters used to calculate the ranking.

    • init

      public void init() throws IOException
      Initializes the rank vector, zeroes iteration and logs basic data. Please extend this method to handle additional attributes.
      Throws:
      IOException

    • step

      public abstract void step() throws IOException
      Performs one computation step.
      Throws:
      IOException

    • normDelta

      public double normDelta()
      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.

      Returns:
      the norm of an estimation of the distance to the limit.
      Throws:
      IllegalStateException - if called before the first iteration.
      UnsupportedOperationException - if it is not possible to compute a norm.

    • stepUntil

      public void stepUntil​(SpectralRanking.StoppingCriterion stoppingCriterion) throws IOException
      Calls 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.
      Parameters:
      stoppingCriterion - the stopping criterion to be used.
      Throws:
      IOException

    • clear

      public void clear()
      Clears all data and releases resources by nulling rank (i.e., results we no longer be available). Please extend this method to handle additional attributes.

    • approximateNormVector

      protected byte[][] approximateNormVector​(DoubleIterator doubleIterator)
      Returns a compact logarithmic approximation of a norm vector.
      Parameters:
      doubleIterator - an iterator enumerating a norm vector.
      Returns:
      an array of bytes containing the opposite of a lower bound on the binary logarithm of the doubles returned by the iterator.