Package it.unimi.dsi.law.rank

Class PageRankParallelPowerSeries

java.lang.Object

it.unimi.dsi.law.rank.SpectralRanking

it.unimi.dsi.law.rank.PageRank

it.unimi.dsi.law.rank.PageRankParallelPowerSeries

public class PageRankParallelPowerSeries
extends PageRank

Computes PageRank using a parallel (multicore) implementation of the power-series method, which runs the power method starting from the preference vector, thus evaluating the truncated PageRank power series (see PageRankPowerSeries).

Note that the step() method is not available: due to the need for some synchronization logic, only stepUntil(StoppingCriterion) is available.

This class exists for debugging and comparison purposes only. The class of choice for computing PageRank is PageRankParallelGaussSeidel.

Warning: Since we need to enumerate the predecessors a node, you must pass to the constructor the transpose of the graph.

Author:

Sebastiano Vigna

See Also:

PageRankPowerSeries, 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
double[]	previousRank	The rank vector after the last iteration (only meaningful after at least one step).

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

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

Methods inherited from class java.lang.Object

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

Field Details

previousRank

public double[] previousRank

The rank vector after the last iteration (only meaningful after at least one step).

Constructor Details

PageRankParallelPowerSeries

public PageRankParallelPowerSeries(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().

PageRankParallelPowerSeries

public PageRankParallelPowerSeries(ImmutableGraph transpose)

Creates a new instance.

Parameters:

transpose - the transpose of the graph on which to compute PageRank.

Method Details

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()

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 class SpectralRanking

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