Project: PageRank Algorithm · PageRank Algorithm

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Programming problem.

Implement a program for the following task. Given a directed graph with \(n\) nodes and \(m\) edges. Compute the PageRank vector for this graph. Use a damping factor of \(0.85\).

  • Input format.  The first line contains integers \(1 \le n \le 10^{3}\), \(n \le m \le 10^{5}\) and \(m \le \binom{n}{2}\). Each of the following \(m\) lines specifies an edge \((u,v)\) of the graph by two integers \(1 \le u \neq v \le n\) (the nodes are indexed by \(1,\dotsc,n\)).

  • Constraints.  The graph contains no self-loops or parallel edges, every vertex has at least one outgoing edge.

  • Output format.  Print the PageRank values of all pages in ascending order of their indices (from \(1\) to \(n\)). The Euclidean norm of the difference between your result and the exact PageRank vector must not exceed \(10^{-3}\).

Hint:
You do not need to determine in advance how many steps of the random walk are required to reach a desired level of accuracy. It is sufficient to compare the Euclidean distance between the current and previous distributions and continue the iterations while the distance is still large.

5 points
Public samples
Public sample 1
Input
5 13
1 2
1 3
1 5
2 1
2 3
2 4
2 5
3 1
3 4
3 5
4 2
4 5
5 4
Expected output
0.10082425052044935 0.19873016937047616 0.10082425052044935 0.33006690969770014 0.2695544198909255