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 SpectralRanking.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 when normDelta()
,
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.
SpectralRanking
SpectralRanking.IterationNumberStoppingCriterion, SpectralRanking.NormStoppingCriterion, SpectralRanking.StoppingCriterion
Modifier and Type  Field and 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 (or
null 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.

DEFAULT_MAX_ITER, DEFAULT_NORM, DEFAULT_THRESHOLD, graph, iteration, logger, n, rank, STOCHASTIC_TOLERANCE
Constructor and Description 

PowerSeries(ImmutableGraph transpose)
Creates a new instance.

PowerSeries(ImmutableGraph transpose,
int requestedThreads)
Creates a new instance.

PowerSeries(ImmutableGraph transpose,
int requestedThreads,
org.slf4j.Logger logger)
Creates a new instance.

PowerSeries(ImmutableGraph transpose,
org.slf4j.Logger logger)
Creates a new instance.

Modifier and Type  Method and 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 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. 
and, approximateNormVector, buildProperties, isStochastic, or
public static final double MIN_SCALE
public static SpectralRanking.StoppingCriterion MAX_RATIO_STOPPING_CRITERION
maxRatio
is smaller than the reciprocal of alpha
.
Note that this criterion can be applied to instances of PowerSeries
only.
public double maxRatio
public double minRatio
public double alpha
public boolean markovian
public double scale
public DoubleList preference
null
if the uniform preference vector should be used).public double[] previousRank
public PowerSeries(ImmutableGraph transpose, int requestedThreads, org.slf4j.Logger logger)
transpose
 the tranpose of the graph on which the power series must be computed.requestedThreads
 the requested number of threads (0 for Runtime.availableProcessors()
).logger
 a logger that will be passed to super()
.public PowerSeries(ImmutableGraph transpose, int requestedThreads)
transpose
 the tranpose of the graph on which the power series must be computed.requestedThreads
 the requested number of threads (0 for Runtime.availableProcessors()
).public PowerSeries(ImmutableGraph transpose, org.slf4j.Logger logger)
transpose
 the tranpose of the graph on which the power series must be computed.logger
 a logger that will be passed to super()
.public PowerSeries(ImmutableGraph transpose)
transpose
 the tranpose of the graph on which the power series must be computed.public void init() throws IOException
SpectralRanking
SpectralRanking.iteration
and logs basic data. Please extend this method to handle additional attributes.init
in class SpectralRanking
IOException
public void step() throws IOException
SpectralRanking
step
in class SpectralRanking
IOException
public void stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion) throws IOException
SpectralRanking
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.stepUntil
in class SpectralRanking
stoppingCriterion
 the stopping criterion to be used.IOException
public double normDelta()
SpectralRanking
This method must be implemented by concrete subclasses if you want to use SpectralRanking.NormStoppingCriterion
.
normDelta
in class SpectralRanking
public void clear()
SpectralRanking
SpectralRanking.rank
(i.e., results we no longer be available).
Please extend this method to handle additional attributes.clear
in class SpectralRanking
public Properties buildProperties(String graphBasename, String preferenceFilename)
graphBasename
 file name of the graphpreferenceFilename
 file name of preference vector. It can be null
.public static void main(String[] arg) throws IOException, JSAPException, org.apache.commons.configuration.ConfigurationException, ClassNotFoundException
IOException
JSAPException
org.apache.commons.configuration.ConfigurationException
ClassNotFoundException