# pagerank

## #

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

Trait | Value |
---|---|

Module type | algorithm |

Implementation | C++ |

Graph direction | directed |

Edge weights | unweighted |

Parallelism | parallel |

## #

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- Step 1: Input graph
- Step 2: Cypher load commands
- Step 3: Running command
- Step 4: Results

```
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 2}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 3}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 4}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 5}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 6}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);MERGE (a:Node {id: 0}) MERGE (b:Node {id: 7}) CREATE (a)-[:RELATION]->(b);
```

`CALL pagerank.get()YIELD node, rank;`

`+-----------------+-----------------+| node | rank |+-----------------+-----------------+| (:Node {id: 1}) | 0.0546896 || (:Node {id: 0}) | 0.333607 || (:Node {id: 2}) | 0.0546896 || (:Node {id: 3}) | 0.0546896 || (:Node {id: 4}) | 0.0546896 || (:Node {id: 5}) | 0.0546896 || (:Node {id: 6}) | 0.0546896 || (:Node {id: 7}) | 0.338255 |+-----------------+-----------------+`