Package it.unimi.dsi.law.rank

Class DominantEigenvectorParallelPowerMethod

java.lang.Object

it.unimi.dsi.law.rank.SpectralRanking

it.unimi.dsi.law.rank.DominantEigenvectorParallelPowerMethod

public class DominantEigenvectorParallelPowerMethod
extends SpectralRanking

Computes the left dominant eigenvalue and eigenvector of a graph using a parallel implementation of the power method. At the end of the computation, lambda will contain an approximation of the dominant eigenvalue.

• If the Markovian flag has been set, the rows of the adjacency matrix will be ℓ₁-normalized.
• normDelta() returns the difference in norm between the previous approximation of the dominant eigenvector and the product of the previous approximation by the graph, divided by the current estimate of the dominant eigenvalue obtained by Rayleigh quotients.
• The step() method is not available: due to the need for some synchronization logic, only stepUntil(StoppingCriterion) is available.
• The computed eigenvector will be a unit vector in the specified norm. In particular, in the Markovian case if you use a norm different from Norm.L_1 the dominant eigenvector will need to be ℓ₁-normalized to be a distribution.
• 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

See Also:

SpectralRanking

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
static Norm	DEFAULT_DOMINANT_EIGENVECTOR_NORM	The default norm (Norm.L_2).
double	lambda	The dominant eigenvalue.
boolean	markovian	if true, the matrix will be stocasticized.
Norm	norm	The norm.
double[]	previousRank	The rank vector after the last iteration (only meaningful after at least one step).
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
DominantEigenvectorParallelPowerMethod(ImmutableGraph transpose)	Creates a new instance.
DominantEigenvectorParallelPowerMethod(ImmutableGraph transpose, int requestedThreads, Logger logger)	Creates a new instance.
DominantEigenvectorParallelPowerMethod(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

DEFAULT_DOMINANT_EIGENVECTOR_NORM

public static final Norm DEFAULT_DOMINANT_EIGENVECTOR_NORM

The default norm (Norm.L_2). Works well with Rayleigh-quotient estimation of the dominant eigenvalue.

previousRank

public double[] previousRank

The rank vector after the last iteration (only meaningful after at least one step).

markovian

public boolean markovian

if true, the matrix will be stocasticized.

shift

public double shift

A shift.

lambda

public double lambda

The dominant eigenvalue.

norm

public Norm norm

The norm.

Constructor Details

DominantEigenvectorParallelPowerMethod

public DominantEigenvectorParallelPowerMethod(ImmutableGraph transpose,
int requestedThreads,
Logger logger)

Creates a new instance.

Parameters:

transpose - the transpose of the graph.

requestedThreads - the requested number of threads (0 for Runtime.availableProcessors()).

logger - a logger that will be passed to super().

DominantEigenvectorParallelPowerMethod

public DominantEigenvectorParallelPowerMethod(ImmutableGraph transpose,
Logger logger)

Creates a new instance.

Parameters:

transpose - the transpose of the graph.

logger - a logger that will be passed to super().

DominantEigenvectorParallelPowerMethod

public DominantEigenvectorParallelPowerMethod(ImmutableGraph transpose)

Creates a new instance.

Parameters:

transpose - the transpose of the graph.

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 - the basename 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