Class PowerSeries
 java.lang.Object

 it.unimi.dsi.law.rank.SpectralRanking

 it.unimi.dsi.law.rank.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 ≥ 0} (αM)^{k}.where v is a preference vector that defaults to 1, and M is the graph adjacency matrix, possibly with stochasticised rows ifmarkovian
is true. Note that thestep()
method is not available: due to the need for some synchronization logic, onlystepUntil(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 whennormDelta()
, 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 “SupremumNorm Convergence for StepAsynchronous Successive Overrelaxation on Mmatrices“, 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 evenPageRankParallelPowerSeries
, 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 byscale
. Note that when using theMAX_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 belowMIN_SCALE
(the latter event might also be due to a very bad nonnormal transient behaviour, but this shouldn't happen with real, nonpathological 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
andminRatio
.Warning: if the computation stops because of the
MAX_RATIO_STOPPING_CRITERION
, the vector suitable formaxRatio
is stored inpreviousRank
, not inrank
, as the maximum ratio was evaluated forpreviousRank
whilerank
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


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
alpha
The attenuation factor.boolean
markovian
If true, the matrix adjacency graph will be stochasticised, thus computing a pseudorank.static SpectralRanking.StoppingCriterion
MAX_RATIO_STOPPING_CRITERION
double
maxRatio
The maximum ratio between components.static double
MIN_SCALE
Below this scale, we stop the iterative process.double
minRatio
The minimum ratio between components.DoubleList
preference
The preference vector to be used (ornull
if the uniform preference vector should be used).double[]
previousRank
The approximation obtained after the last iteration (only meaningful after at least one step).double
scale
The overall scaling that has been applied to the current approximation.
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 PowerSeries(ImmutableGraph transpose)
Creates a new instance.PowerSeries(ImmutableGraph transpose, int requestedThreads)
Creates a new instance.PowerSeries(ImmutableGraph transpose, int requestedThreads, Logger logger)
Creates a new instance.PowerSeries(ImmutableGraph transpose, Logger logger)
Creates a new instance.

Method Summary
Modifier and Type Method Description Properties
buildProperties(String graphBasename, String preferenceFilename)
Returns a Properties object that contains all the parameters used by the computation.void
clear()
Clears all data and releases resources by nullingSpectralRanking.rank
(i.e., results we no longer be available).void
init()
Initializes the rank vector, zeroesSpectralRanking.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)
CallsSpectralRanking.init()
and steps until a given stopping criterion is met.
Methods inherited from class it.unimi.dsi.law.rank.SpectralRanking
and, approximateNormVector, buildProperties, isStochastic, or




Field Detail

MIN_SCALE
public static final double MIN_SCALE
Below this scale, we stop the iterative process. See Also:
 Constant Field Values

MAX_RATIO_STOPPING_CRITERION
public static SpectralRanking.StoppingCriterion MAX_RATIO_STOPPING_CRITERION
A stopping criterion that stops whenmaxRatio
is smaller than the reciprocal ofalpha
.Note that this criterion can be applied to instances of
PowerSeries
only.

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 (ornull
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 forRuntime.availableProcessors()
).logger
 a logger that will be passed tosuper()
.

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 forRuntime.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 tosuper()
.

PowerSeries
public PowerSeries(ImmutableGraph transpose)
Creates a new instance. Parameters:
transpose
 the tranpose of the graph on which the power series must be computed.


Method Detail

init
public void init() throws IOException
Description copied from class:SpectralRanking
Initializes the rank vector, zeroesSpectralRanking.iteration
and logs basic data. Please extend this method to handle additional attributes. Overrides:
init
in classSpectralRanking
 Throws:
IOException

step
public void step() throws IOException
Description copied from class:SpectralRanking
Performs one computation step. Specified by:
step
in classSpectralRanking
 Throws:
IOException

stepUntil
public void stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion) throws IOException
Description copied from class:SpectralRanking
CallsSpectralRanking.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 classSpectralRanking
 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 classSpectralRanking
 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 nullingSpectralRanking.rank
(i.e., results we no longer be available). Please extend this method to handle additional attributes. Overrides:
clear
in classSpectralRanking

buildProperties
public Properties buildProperties(String graphBasename, String preferenceFilename)
Returns a Properties object that contains all the parameters used by the computation. Parameters:
graphBasename
 file name of the graphpreferenceFilename
 file name of preference vector. It can benull
. Returns:
 a properties object that represent all the parameters used to calculate the rank.

main
public static void main(String[] arg) throws IOException, JSAPException, org.apache.commons.configuration.ConfigurationException, ClassNotFoundException
 Throws:
IOException
JSAPException
org.apache.commons.configuration.ConfigurationException
ClassNotFoundException

