Lesson 5

Programming problem.

Implement a program for the following task. Given a directed graph with \(n\) nodes and \(m\) edges and a personalization vector \(w\). Compute the personalized 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\)). The last line contains \(n\) space-separated real numbers \(w_{1}, w_{2}, …, w_{n}\) representing the personalization vector (it is guaranteed that \(\sum_{i=1}^{n}w_{i} = 1\)).


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


• Output format.  Print the personalized 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}\).

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
0.5 0.5 0 0 0

0.15174234134317427 0.23688865645940227 0.09330078558976435 0.27943721880508254 0.23863099780257652