Class PageRankParallelGaussSeidel
 java.lang.Object

 it.unimi.dsi.law.rank.SpectralRanking

 it.unimi.dsi.law.rank.PageRank

 it.unimi.dsi.law.rank.PageRankParallelGaussSeidel

public class PageRankParallelGaussSeidel extends PageRank
Computes PageRank using a parallel (multicore) implementation of the Gauß–Seidel method.Note: this is the implementation of choice to be used when computing PageRank. It uses less memory (one vector of doubles plus one vector of integers) and, experimentally, converges faster than any other implementation. Moreover, it scales linearly with the number of cores.
Warning: Since we need to enumerate the predecessors a node, you must pass to the constructor the transpose of the graph.
Technically, the iteration performed by this class is not a Gauß–Seidel iteration: we simply start a number of threads, and each thread updates a value using a Gauß–Seidellike rule. As a result, each update uses some old and some new values: in other words, the regular splitting
M − N = I − α (P + u^{T}d)of the matrix associated to each update is always different (in a Gauß–Seidel iteration, M is upper triangular, and N is strictly lower triangular). Nonetheless, it is easy to check that M is still (up to permutation) upper triangular and invertible, independently of the specific update sequence.Note that the
step()
method is not available: due to the need for some synchronization logic, onlystepUntil(StoppingCriterion)
is available.The
normDelta()
method returns the following values: if a suitable norm vector has been set, an upper bound on the error (the ℓ_{∞} distance from the rank to be computed);
 otherwise, an upper bound to the ℓ_{1} norm of the error, obtained multiplying by α / (1 − α) the ℓ_{1} norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).
To be able to set a norm vector, you need to set the
pseudoRank
flag and usePowerSeries
(setting the Markovian flag) to compute a suitable vector. To do so, you must provide an α and use thePowerSeries.MAX_RATIO_STOPPING_CRITERION
. If the computation terminates without errors with maximum ratio σ, the resulting vector can be used with this class to compute pseudoranks for all α < 1 / σ (strictness is essential). Note that the ℓ_{1} norm of the error bounds the ℓ_{∞}.With respect to the description of the exact algorithm in
PageRankGaussSeidel
, we operate a simplification that is essentially in obtaining a coherent update without incurring in too much synchronization: the rank associated with dangling nodes is computed at the end of each computation, and used unchanged throughout the whole iteration. This corresponds to permuting the array so that dangling nodes come out last. Author:
 Sebastiano Vigna
 See Also:
PageRankGaussSeidel
,PageRank
,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 int[]
outdegree
The outdegree of each node (initialized after the first computation).boolean
pseudoRank
If true, an everywhere zero danglingnode distribution will be simulated, resulting in the computation of a pseudorank.
Fields inherited from class it.unimi.dsi.law.rank.PageRank
alpha, buckets, danglingNodeDistribution, DEFAULT_ALPHA, preference, stronglyPreferential

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 PageRankParallelGaussSeidel(ImmutableGraph transpose)
Creates a new instance.PageRankParallelGaussSeidel(ImmutableGraph transpose, int requestedThreads, Logger logger)
Creates a new instance.PageRankParallelGaussSeidel(ImmutableGraph transpose, Logger logger)
Creates a new instance.

Method Summary
Modifier and Type Method Description void
clear()
Clears all data and releases resources by nullingSpectralRanking.rank
(i.e., results we no longer be available).void
init()
Basic initialization: we log the damping factor, check that the preference vector is correctly sized and stochastic, fillSpectralRanking.rank
with the preference vector and set the danglingnode distribution depending on the value ofPageRank.stronglyPreferential
.static void
main(String[] arg)
double
normDelta()
Return the following values: if a suitable norm vector has been set, an upper bound on the error (the ℓ_{∞} distance from the rank to be computed); otherwise, an upper bound to the ℓ_{1} norm of the error, obtained multiplying by α / (1 − α) the ℓ_{1} norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).void
normVector(double[] normVector, double sigma)
Sets the norm vector.void
normVector(String normVectorFilename, double sigma)
Sets the norm vector.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.PageRank
buildProperties

Methods inherited from class it.unimi.dsi.law.rank.SpectralRanking
and, approximateNormVector, buildProperties, isStochastic, or




Constructor Detail

PageRankParallelGaussSeidel
public PageRankParallelGaussSeidel(ImmutableGraph transpose, int requestedThreads, Logger logger)
Creates a new instance. Parameters:
transpose
 the transpose of the graph on which to compute PageRank.requestedThreads
 the requested number of threads (0 forRuntime.availableProcessors()
).logger
 a logger that will be passed tosuper()
.

PageRankParallelGaussSeidel
public PageRankParallelGaussSeidel(ImmutableGraph transpose)
Creates a new instance. Parameters:
transpose
 the transpose of the graph on which to compute PageRank.

PageRankParallelGaussSeidel
public PageRankParallelGaussSeidel(ImmutableGraph transpose, Logger logger)
Creates a new instance. Parameters:
transpose
 the transpose of the graph on which to compute PageRank.logger
 a logger that will be passed tosuper()
.


Method Detail

normVector
public void normVector(String normVectorFilename, double sigma) throws IOException
Sets the norm vector. Parameters:
normVectorFilename
 a file containing a norm vector as a list of doubles inDataInput
format, ornull
for no norm vector.sigma
 the value for which the provided norm vector is suitable. Throws:
IOException

normVector
public void normVector(double[] normVector, double sigma)
Sets the norm vector. Parameters:
normVector
 the new norm vector.sigma
 the value for which the provided norm vector is suitable.

init
public void init() throws IOException
Description copied from class:PageRank
Basic initialization: we log the damping factor, check that the preference vector is correctly sized and stochastic, fillSpectralRanking.rank
with the preference vector and set the danglingnode distribution depending on the value ofPageRank.stronglyPreferential
. Overrides:
init
in classPageRank
 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()
Return the following values: if a suitable norm vector has been set, an upper bound on the error (the ℓ_{∞} distance from the rank to be computed); otherwise, an upper bound to the ℓ_{1} norm of the error, obtained multiplying by α / (1 − α) the ℓ_{1} norm of the difference between the last two approximations (this idea arose in discussions with David Gleich). Overrides:
normDelta
in classSpectralRanking
 Returns:
 an upper bound on the error.

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

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

