Package it.unimi.dsi.law.rank

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 MM^T. 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

Nested Class Summary

Nested classes/interfaces inherited from class it.unimi.dsi.law.rank.SpectralRanking

SpectralRanking.IterationNumberStoppingCriterion, SpectralRanking.NormStoppingCriterion, SpectralRanking.StoppingCriterion

Field Summary

Fields

Modifier and Type	Field	Description
double[]	intermediateRank	The rank vector obtained after the first half of a round.
Norm	norm	The norm.
double[]	previousRank	The rank vector at the end of the last round.
boolean	salsa	Compute the SALSA score (only for historical and testing reasons: please use the Salsa class instead).
double	shift	A shift.

Fields inherited from class it.unimi.dsi.law.rank.SpectralRanking

DEFAULT_MAX_ITER, DEFAULT_NORM, DEFAULT_THRESHOLD, graph, iteration, logger, n, rank, STOCHASTIC_TOLERANCE

Constructor Summary

Constructors

Constructor	Description
LeftSingularVectorParallelPowerMethod(ImmutableGraph graph, ImmutableGraph transpose)	Creates a new instance.
LeftSingularVectorParallelPowerMethod(ImmutableGraph graph, ImmutableGraph transpose, int requestedThreads)	Creates a new instance.
LeftSingularVectorParallelPowerMethod(ImmutableGraph graph, ImmutableGraph transpose, int requestedThreads, Logger logger)	Creates a new instance.
LeftSingularVectorParallelPowerMethod(ImmutableGraph graph, ImmutableGraph transpose, Logger logger)	Creates a new instance.

Method Summary

Modifier and Type	Method	Description
Properties	buildProperties(String graphBasename)	Returns a Properties object that contains all the parameters used by the computation.
void	clear()	Clears all data and releases resources by nulling SpectralRanking.rank (i.e., results we no longer be available).
void	init()	Initializes the rank vector, zeroes SpectralRanking.iteration and logs basic data.
static void	main(String[] arg)
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.
void	step()	Performs one computation step.
void	stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion)	Calls SpectralRanking.init() and steps until a given stopping criterion is met.

Methods inherited from class it.unimi.dsi.law.rank.SpectralRanking

and, approximateNormVector, isStochastic, or

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

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.

clear

public void clear()

Description copied from class: SpectralRanking

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

Overrides:

clear in class SpectralRanking

buildProperties

public Properties buildProperties(String graphBasename)

Returns a Properties object that contains all the parameters used by the computation.

Overrides:

buildProperties in class SpectralRanking

Parameters:

graphBasename - file name of the graph

Returns:

a properties object that represent all the parameters used to calculate the rank.

main

public static void main(String[] arg)
                 throws IOException,
JSAPException,
ConfigurationException

Throws:

IOException

JSAPException

ConfigurationException