Class PowerSeries
public class PowerSeries extends SpectralRanking
This class is a generic power series approximator. It computes iteratively finite truncations of power series of the form
markovian
is true.
Note that the step()
method is not available: due to the need for some synchronization logic, only stepUntil(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 even PageRankParallelPowerSeries
, 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 by scale
. Note that when using the MAX_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 below MIN_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
and minRatio
.
Warning: if the computation stops because of the MAX_RATIO_STOPPING_CRITERION
,
the vector suitable for maxRatio
is stored in previousRank
, not in rank
, as the maximum ratio was evaluated
for previousRank
while rank
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 Details

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

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 maxRatioThe maximum ratio between components. 
minRatio
public double minRatioThe minimum ratio between components. 
alpha
public double alphaThe attenuation factor. Must be smaller than the reciprocal of the dominant eigenvalue. 
markovian
public boolean markovianIf true, the matrix adjacency graph will be stochasticised, thus computing a pseudorank. 
scale
public double scaleThe overall scaling that has been applied to the current approximation. 
preference
The preference vector to be used (ornull
if the uniform preference vector should be used). 
previousRank
public double[] previousRankThe approximation obtained after the last iteration (only meaningful after at least one step).


Constructor Details

PowerSeries
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
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
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
Creates a new instance. Parameters:
transpose
 the tranpose of the graph on which the power series must be computed.


Method Details

init
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
Description copied from class:SpectralRanking
Performs one computation step. Specified by:
step
in classSpectralRanking
 Throws:
IOException

stepUntil
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
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, ClassNotFoundException, ConfigurationException
