Class PageRank

Inheritance Relationships

Base Type

Class Documentation

class PageRank : public NetworKit::Centrality

Compute PageRank as node centrality measure. In the default mode this computation is in line with the original paper “The PageRank citation ranking: Bringing order to the web.” by L. Brin et al (1999). In later publications (“PageRank revisited.” by M. Brinkmeyer et al. (2005) amongst others) sink-node handling was added for directed graphs in order to comply with the theoretical assumptions by the underlying Markov chain model. This can be activated by setting the matching parameter to true. By default this is disabled, since it is an addition to the original definition.

Page-Rank values can also be normalized by post-processed according to “Comparing Apples and

Oranges: Normalized PageRank for Evolving Graphs” by Berberich et al. (2007). This decouples the

PageRank values from the size of the input graph. To enable this, set the matching parameter to true. Note that sink-node handling is automatically activated if normalization is used.

NOTE: There is an inconsistency in the definition in Newman’s book (Ch. 7) regarding directed graphs; we follow the verbal description, which requires to sum over the incoming edges (as opposed to outgoing ones).

Public Types

enum Norm

Values:

enumerator L1_NORM
enumerator L2_NORM
enumerator L1Norm
enumerator L2Norm
enum SinkHandling

Values:

enumerator NO_SINK_HANDLING
enumerator DISTRIBUTE_SINKS

Public Functions

PageRank(const Graph &G, double damp = 0.85, double tol = 1e-8, bool normalized = false, SinkHandling distributeSinks = SinkHandling::NO_SINK_HANDLING)

Constructs the PageRank class for the Graph G

Parameters:
  • G[in] Graph to be processed.

  • damp[in] Damping factor of the PageRank algorithm.

  • tol[in] Error tolerance for PageRank iteration.

  • distributeSinks[in] Set to distribute PageRank values for sink nodes. (default = false)

  • normalized[in] Set to normalize Page-Rank values in order to decouple it from the network size. (default = false)

virtual void run() override

Computes page rank on the graph passed in constructor.

virtual double maximum() override

Returns the maximum PageRank score

inline count numberOfIterations() const

Return the number of iterations performed by the algorithm.

Returns:

Number of iterations performed by the algorithm.

Public Members

count maxIterations = std::numeric_limits<count>::max()
Norm norm = Norm::L2_NORM