public abstract class SpectralRanking extends Object
The usage pattern for concrete subclasses is as follows: first create an instance specifying the graph over which the spectral ranking should be computed. Then, modify public available attributes to finetune the ranking algorithm. Finally,
init()
method, which initializes the state, and then repeatedly call the
step()
method; every call will compute the next approximation; the current approximation is contained
in the rank
attribute;
stepUntil(SpectralRanking.StoppingCriterion)
method, which calls init()
and then iterates
the step()
method until a certain stopping criterion is met; a SpectralRanking.StoppingCriterion
is a class that decides whether the iteration can be stopped.
The SpectralRanking
class provides two readytouse implementations of stopping criteria:
normDelta()
(if implemented) is smaller than a certain threshold.
Moreover, this class provides two static methods that compose stopping criteria in a conjunctive or disjunctive way.
At any time, the user may reinitialize the computation, by calling the init()
method, or call
clear()
to get rid of the large arrays that the implementing subclasses usually manage. In the latter case, the arrays
are rebuilt on the next call to init()
.
The stopping threshold used by SpectralRanking.NormStoppingCriterion
should be set so to obtain a reasonable number
of significant digits. In some cases this requires to adapt the threshold to the graph: for instance, PageRank
is a stochastic vector, so its entries tend to be very small (of order 1/n, where n is the number of
nodes in the graph). You should be wary about digits that are not significant, as they can lead to very biased results when comparing using
Kendall's τ rankings with a significant amount of ties (see “Traps and pitfalls of topicbiased PageRank”, by
Paolo Boldi, Roberto Posenato, Massimo Santini, and Sebastiano Vigna,
WAW 2006. Fourth Workshop on Algorithms and Models for the WebGraph, volume 4936 of Lecture Notes in Computer Science, pages 107−116, Springer, 2008).
Note that, depending on the implementation, normDelta()
might return a bound on the norm of the difference
between the current iterate and the target ranking (e.g., PageRankPowerSeries
and PageRankParallelPowerSeries
,
or any Gauß–Seidel implementation using a wnorm), a tentative estimate
of the same bound (e.g., DominantEigenvectorParallelPowerMethod
)
or simply the norm of the difference between two successive iterates. Precision up to the
chosen threshold is guaranteed only in the first case.
Modifier and Type  Class and Description 

static class 
SpectralRanking.IterationNumberStoppingCriterion
A stopping criterion that stops whenever the number of iterations exceeds a given bound.

static class 
SpectralRanking.NormStoppingCriterion
A stopping criterion that evaluates
normDelta() , and stops
if this value is smaller than a given threshold. 
static interface 
SpectralRanking.StoppingCriterion
A a strategy that decides when a computation should be stopped.

Modifier and Type  Field and Description 

static int 
DEFAULT_MAX_ITER
Default maximum number of iterations (note that this value is used as a default by main methods).

static Norm 
DEFAULT_NORM
The default norm (
Norm.L_INFINITY ). 
static double 
DEFAULT_THRESHOLD
Default threshold (note that this value is used as a default by main methods).

ImmutableGraph 
graph
The graph.

int 
iteration
The current step (0 after initialization).

org.slf4j.Logger 
logger
A logger defined by the implementing subclasses.

int 
n
The number of nodes of
graph , cached. 
double[] 
rank
The current rank vector.

protected static double 
STOCHASTIC_TOLERANCE
The admitted tolerance in the verification that a vector is a stochastic one.

Constructor and Description 

SpectralRanking(ImmutableGraph graph,
org.slf4j.Logger logger)
Creates a new instance.

Modifier and Type  Method and Description 

static SpectralRanking.StoppingCriterion 
and(SpectralRanking.StoppingCriterion stop1,
SpectralRanking.StoppingCriterion stop2)
Composes two stopping criteria, producing a single stopping criterion (the computation stops iff both
conditions become true; lazy boolean evaluation is applied).

protected byte[] 
approximateNormVector(DoubleIterator doubleIterator)
Returns a compact logarithmic approximation of a norm vector.

Properties 
buildProperties(String graphBasename)
Returns a
Properties object that contains all parameters used by the computation. 
void 
clear()
Clears all data and releases resources by nulling
rank (i.e., results we no longer be available). 
void 
init()
Initializes the rank vector, zeroes
iteration and logs basic data. 
protected static boolean 
isStochastic(DoubleList v)
Commodity method checking whether a vector is stochastic (nonnegative entries summing up to one within
STOCHASTIC_TOLERANCE ). 
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.

static SpectralRanking.StoppingCriterion 
or(SpectralRanking.StoppingCriterion stop1,
SpectralRanking.StoppingCriterion stop2)
Composes two stopping criteria, producing a single stopping criterion (the computation stops iff either
condition becomes true; lazy boolean evaluation is applied).

abstract void 
step()
Performs one computation step.

void 
stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion)
Calls
init() and steps until a given stopping criterion is met. 
public static final double DEFAULT_THRESHOLD
public static final int DEFAULT_MAX_ITER
public static final Norm DEFAULT_NORM
Norm.L_INFINITY
).protected static final double STOCHASTIC_TOLERANCE
STOCHASTIC_TOLERANCE
.public final ImmutableGraph graph
public final int n
graph
, cached.public final org.slf4j.Logger logger
public double[] rank
public int iteration
public SpectralRanking(ImmutableGraph graph, org.slf4j.Logger logger)
graph
 the graph.logger
 a logger.public static SpectralRanking.StoppingCriterion and(SpectralRanking.StoppingCriterion stop1, SpectralRanking.StoppingCriterion stop2)
stop1
 a stopping criterion.stop2
 a stopping criterion.public static SpectralRanking.StoppingCriterion or(SpectralRanking.StoppingCriterion stop1, SpectralRanking.StoppingCriterion stop2)
stop1
 a stopping criterion.stop2
 a stopping criterion.protected static boolean isStochastic(DoubleList v)
STOCHASTIC_TOLERANCE
).
This method uses Kahan's summation algorithm.
v
 the vector to check.public Properties buildProperties(String graphBasename)
Properties
object that contains all parameters used by the computation.
Implementing subclasses should extends this method by calling super()
and setting additional properties on the resulting Properties
.
graphBasename
 basename of the graphpublic void init() throws IOException
iteration
and logs basic data. Please extend this method to handle additional attributes.IOException
public abstract void step() throws IOException
IOException
public double normDelta()
This method must be implemented by concrete subclasses if you want to use SpectralRanking.NormStoppingCriterion
.
IllegalStateException
 if called before the first iteration.UnsupportedOperationException
 if it is not possible to compute a norm.public void stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion) throws IOException
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.stoppingCriterion
 the stopping criterion to be used.IOException
public void clear()
rank
(i.e., results we no longer be available).
Please extend this method to handle additional attributes.protected byte[] approximateNormVector(DoubleIterator doubleIterator)
doubleIterator
 an iterator enumerating a norm vector.