Package it.unimi.dsi.law.rank

Class PageRank

java.lang.Object

it.unimi.dsi.law.rank.SpectralRanking

it.unimi.dsi.law.rank.PageRank

Direct Known Subclasses:

PageRankGaussSeidel, PageRankParallelGaussSeidel, PageRankParallelPowerSeries, PageRankPowerSeries, PageRankPush

public abstract class PageRank
extends SpectralRanking

An abstract class defining methods and attributes supporting PageRank computations. Provides settable damping factor, preference vector and starting vector.

Formulae and preferences

There are two main formulae for PageRank in the literature. The first one, which we shall call weakly preferential, patches all dangling nodes by adding a uniform transition towards all other nodes. The second one, which we shall call strongly preferential, patches all dangling nodes adding transitions weighted following the preference vector v. We can consider the two formulae together, letting u be a vector that is uniform in the weak case and coincides with v in the strong case.

If we denote with P the normalised adjacency matrix of the graph, with d the characteristic vector of dangling nodes, and with α the damping factor, the generic equation is

x = x (α P + α d^Tu + (1 − α) 1^T v),

which, distributing over the sum, makes it possible to express PageRank as

(1 − α) v( P + d^Tu )^-1,

or even

(1 − α) v ∑_{k ≥ 0} α^k ( P + d^Tu )^k.

By default, weakly preferential PageRank is computed; strongly preferential PageRank computation is enforced by setting stronglyPreferential to true.

See Also:

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	alpha	The damping factor.
BitSet	buckets	If not null, the set of buckets of SpectralRanking.graph.
DoubleList	danglingNodeDistribution	The vector used used to patch null rows of the adjacency matrix (u in the general formula).
static double	DEFAULT_ALPHA	The default damping factor.
DoubleList	preference	The preference vector to be used (or null if the uniform preference vector should be used).
boolean	stronglyPreferential	Decides whether we use the strongly or weakly (the default) preferential algorithm.

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
PageRank(ImmutableGraph g, Logger logger)	Creates a new instance.

Method Summary

Modifier and Type	Method	Description
Properties	buildProperties(String graphBasename, String preferenceFilename, String danglingFilename)	Returns a Properties object that contains all the parameters used by the computation.
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 stronglyPreferential.

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

and, approximateNormVector, buildProperties, clear, isStochastic, normDelta, or, step, stepUntil

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_ALPHA

public static final double DEFAULT_ALPHA

The default damping factor.

See Also:

Constant Field Values

alpha

public double alpha

The damping factor. In the random surfer interpretation, this is the probability that the surfer will follow a link in the current page.

preference

public DoubleList preference

The preference vector to be used (or null if the uniform preference vector should be used).

danglingNodeDistribution

public DoubleList danglingNodeDistribution

The vector used used to patch null rows of the adjacency matrix (u in the general formula). It coincides with the preference vector if stronglyPreferential is true. If null, the uniform distribution will be used.

buckets

public BitSet buckets

If not null, the set of buckets of SpectralRanking.graph.

stronglyPreferential

public boolean stronglyPreferential

Decides whether we use the strongly or weakly (the default) preferential algorithm.

Constructor Details

PageRank

public PageRank(ImmutableGraph g,
Logger logger)

Creates a new instance.

Parameters:

g - the graph.

logger - a logger.

Method Details

buildProperties

public Properties buildProperties(String graphBasename,
String preferenceFilename,
String danglingFilename)

Returns a Properties object that contains all the parameters used by the computation.

Parameters:

graphBasename - the basename of the graph.

preferenceFilename - the filename of preference vector. It can be null.

danglingFilename - the filename of dangling-node distribution. It can be null.

Returns:

a properties object that represent all the parameters used to calculate the rank.

init

public void init()
          throws IOException

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

Overrides:

init in class SpectralRanking

Throws:

IOException