Class PageRank¶

Defined in File PageRank.hpp

Inheritance Relationships¶

Base Type¶

public NetworKit::Centrality (Class Centrality)

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 ¶