Class LeftSingularVectorParallelPowerMethod

java.lang.Object
it.unimi.dsi.law.rank.SpectralRanking
it.unimi.dsi.law.rank.LeftSingularVectorParallelPowerMethod

public class LeftSingularVectorParallelPowerMethod
extends SpectralRanking
Computes the left singular vector of a graph using a parallel implementation of the power method.

This class computes iteratively and in parallel an approximation of the left singular vector of a graph with adjacency matrix M, that is, the dominant eigenvector of MMT. Note that the step() method is not available: due to the need for some synchronization logic, only stepUntil(StoppingCriterion) is available.

This class can be run using SpectralRanking.NormStoppingCriterion that stops, as usual, when normDelta(), which returns the norm of the difference between the two last approximations, is below a specified threshold.

It is strongly suggested that you apply a shift (e.g., -1). A negative shift guarantees convergence even in the presence of eigenvalues of maximum modulus that are not real positive (see a numerical linear algebra textbook for details).

Author:
Sebastiano Vigna
  • Field Details

    • norm

      public Norm norm
      The norm.
    • salsa

      public boolean salsa
      Compute the SALSA score (only for historical and testing reasons: please use the Salsa class instead).
    • shift

      public double shift
      A shift.
    • intermediateRank

      public double[] intermediateRank
      The rank vector obtained after the first half of a round.
    • previousRank

      public double[] previousRank
      The rank vector at the end of the last round.
  • Constructor Details

    • LeftSingularVectorParallelPowerMethod

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

      public LeftSingularVectorParallelPowerMethod​(ImmutableGraph graph, ImmutableGraph transpose, Logger logger)
      Creates a new instance.
      Parameters:
      graph - the graph on which the computation must be performed.
      transpose - the tranpose of the graph on which the computation must be performed.
      logger - a logger that will be passed to super().
    • LeftSingularVectorParallelPowerMethod

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

      public LeftSingularVectorParallelPowerMethod​(ImmutableGraph graph, ImmutableGraph transpose)
      Creates a new instance.
      Parameters:
      graph - the graph on which the computation must be performed.
      transpose - the tranpose of the graph on which the computation must be performed.
  • Method Details