Package it.unimi.dsi.law.big.rank

Class PageRankParallelGaussSeidel

java.lang.Object

it.unimi.dsi.law.big.rank.SpectralRanking

it.unimi.dsi.law.big.rank.PageRank

it.unimi.dsi.law.big.rank.PageRankParallelGaussSeidel

public class PageRankParallelGaussSeidel
extends PageRank

A big version of PageRankParallelGaussSeidel.

Author:

Sebastiano Vigna

See Also:

PageRankParallelGaussSeidel, PageRank, SpectralRanking

Nested Class Summary

Nested classes/interfaces inherited from class it.unimi.dsi.law.big.rank.SpectralRanking

SpectralRanking.IterationNumberStoppingCriterion, SpectralRanking.NormStoppingCriterion, SpectralRanking.StoppingCriterion

Field Summary

Fields

Modifier and Type	Field	Description
long[][]	outdegree	The outdegree of each node (initialized after the first computation).
boolean	pseudoRank	If true, an everywhere zero dangling-node distribution will be simulated, resulting in the computation of a pseudorank.

Fields inherited from class it.unimi.dsi.law.big.rank.PageRank

alpha, buckets, danglingNodeDistribution, DEFAULT_ALPHA, preference, stronglyPreferential

Fields inherited from class it.unimi.dsi.law.big.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 nulling SpectralRanking.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, fill SpectralRanking.rank with the preference vector and set the dangling-node distribution depending on the value of PageRank.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)	Calls SpectralRanking.init() and steps until a given stopping criterion is met.

Methods inherited from class it.unimi.dsi.law.big.rank.PageRank

buildProperties

Methods inherited from class it.unimi.dsi.law.big.rank.SpectralRanking

and, approximateNormVector, buildProperties, isStochastic, or

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

outdegree

public long[][] outdegree

The outdegree of each node (initialized after the first computation).

pseudoRank

public boolean pseudoRank

If true, an everywhere zero dangling-node distribution will be simulated, resulting in the computation of a pseudorank.

Constructor Details

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 for Runtime.availableProcessors()).

logger - a logger that will be passed to super().

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 to super().

Method Details

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 in DataInput format, or null 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, fill SpectralRanking.rank with the preference vector and set the dangling-node distribution depending on the value of PageRank.stronglyPreferential.

Overrides:

init in class PageRank

Throws:

IOException

step

public void step()
          throws IOException

Description copied from class: SpectralRanking

Performs one computation step.

Specified by:

step in class SpectralRanking

Throws:

IOException

stepUntil

public void stepUntil(SpectralRanking.StoppingCriterion stoppingCriterion)
               throws IOException

Description copied from class: SpectralRanking

Calls 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.

Overrides:

stepUntil in class SpectralRanking

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 ℓ₁ norm of the error, obtained multiplying by α / (1 − α) the ℓ₁ norm of the difference between the last two approximations (this idea arose in discussions with David Gleich).

Overrides:

normDelta in class SpectralRanking

Returns:

an upper bound on the error.

clear

public void clear()

Description copied from class: SpectralRanking

Clears all data and releases resources by nulling SpectralRanking.rank (i.e., results we no longer be available). Please extend this method to handle additional attributes.

Overrides:

clear in class SpectralRanking

main

public static void main(String[] arg)
                 throws IOException,
JSAPException,
ClassNotFoundException,
ConfigurationException

Throws:

IOException

JSAPException

ClassNotFoundException

ConfigurationException