Skip to main content

pagerank

docs-source

Abstract#

If we present nodes as pages and directed edges between them as links the PageRank algorithm outputs a probability distribution used to represent the likelihood that a person randomly clicking on links will arrive at any particular page.

PageRank theory holds that an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue randomly clicking on links is called a damping factor, otherwise next page is chosen randomly among all pages.

PageRank is computed iteratively using following formula:

Rank(n, t + 1) = (1 - d) / number_of_nodes                + d * sum { Rank(in_neighbour_of_n, t) /                out_degree(in_neighbour_of_n)}

Where Rank(n, t) is PageRank of node n at iteration t. In the end, rank values are normalized to sum 1 to form a probability distribution.

The algorithm is implemented in such a way that all available threads are used to calculate PageRank, mostly for scalability purposes.

Default arguments are equal to default arguments in NetworkX PageRank implementation.

TraitValue
Module typealgorithm
ImplementationC++
Graph directiondirected
Edge weightsunweighted
Parallelismparallel

Procedures#

get(max_iterations, damping_factor, stop_epsilon)#

Input:#

  • max_iterations: int(100) ➡ Maximum number of iterations within PageRank algorithm.
  • damping_factor: double(0.85) ➡ PageRanks damping factor. This is the probability of continuing the random walk from a random node within the graph.
  • stop_epsilon: double(1e-5) ➡ Value used to terminate the iterations of PageRank. If change from one iteration to another is lower than stop_epsilon, execution is stopped.

Output:#

  • node ➡ Node in graph, for which PageRank is calculated.
  • rank ➡ Normalized ranking of a node. Expresses the probability that random surfer will finish in a certain node by a random walk.

Usage:#

CALL pagerank.get()YIELD node, rank;

Example#