No.8018 Simplified PageRank
タグ : / 解いたユーザー数 26
作問者 :
horiesiniti
/ テスター :
37zigen
Problem Statement
Google's PageRank, recently discontinued, is an important technique that is still used in a variety of fields.
This time, let's implement a simplified version of PageRank.
(It is not required, but looking up PageRank before answering may deepen your understanding.
Explanations of PageRank can be found on Wikipedia and elsewhere. Wikipedia: PageRank)
Here, we will run a simple simulation of how people move between web pages.
Following Google's PageRank, the calculation starts from a state in which every page is initially being viewed by 10.0 people. The pages are numbered from 0 to n-1. We view this as a graph, with pages as vertices and one-way links as arrows. Fractional values are allowed in the calculation, such as 0.274481 people being at a vertex.
The calculation proceeds in turns. In each calculation step, people choose one of the one or more links on the page they are currently staying on and move to the link's destination. Since this is a simplified calculation, nobody stays at a vertex or quits, and everyone always moves to the next link destination in each calculation step. Compute the number of people on each page after 100 calculation steps. The data gives the pages and the proportions of people who follow the one-way links on each page to go to other pages. Simulate the movement of people based on these proportions.
(The sample inputs are explained with figures at the bottom of the page, so refer to them if this is hard to understand.)
Input
$n$ $m$ $a_1$ $b_1$ $c_1$ $\dots$ $a_m$ $b_m$ $c_m$
$1< n \le 1000$
$1< m \le 10000$
$0 \le a_i < n$
$0 \le b_i < n$
$a_i \ne b_i$
$0 \lt c_i \le 10$
the first line contains the number of pages $n$.
You may assume that the pages are numbered from $0~n-1$.
The second line contains the number of one-way links between pages $m$.
Each of the following $m$ lines gives a one-way link and the proportion of people who click that link, as integers:
$a_i$ $b_i$ $c_i$
The proportion of people going from page $ai$ to page $bi$ is $ci$.
Here is a calculation example for the case where page 1 has one-way links to pages 2, 5, 7 with proportions 3 2 4 respectively (the value of ci on each line).
Suppose that, in terms of data, extracting the link data going out of page 1 gives the following.
1 2 3
1 5 2
1 7 4
That is the data.
The number of people going from page 1 to page 2 is
$\frac{n1*3.0}{3+2+4}$
The number of people going from page 1 to page 5 is
$\frac{n1*2.0}{3+2+4}$
The number of people going from page 1 to page 7 is
$\frac{n1*4.0}{3+2+4}$
These are calculated in this way, and nobody stays on page 1.
If there are pages linking to page 1, people arrive at page 1 from them by the same calculation.
One calculation step consists of everyone at every vertex moving one link ahead in this way.
After 100 calculation steps have been performed, output the number of people at each vertex as a real number $Ui$, one per line, from page 0 to page n-1.
An error of up to 0.1 is allowed.
You may assume that every page has at least one link destination.
The number of people on a page that is not linked from anywhere is calculated as 0.
Perform the calculation using the double type.
That was a long explanation, but now give it a try.
Output
$U_0$
$\dots$
$U_{n-1}$
Print a newline at the end.
Sample
Sample 1
Input
5 9 0 1 3 0 2 2 1 0 3 1 2 1 2 3 2 2 4 2 3 1 4 4 3 5 4 0 7
Output
14.087019 15.121255 9.415121 6.669044 4.707561
Let us explain using the figure. For example, in the first calculation step,
the number of people going from page a1 to page a0 is $\frac{10人*3}{1+3}$
the number of people going from page a1 to page a2 is $\frac{10人*1}{1+3}$
as shown above.The number of people arriving at page a1 is
from page a3: $\frac{10人*4}{4}=10人$
from page a0: $\frac{10人*3}{3+2}=6人$
Therefore, the number of people on page a1 at the end of the first calculation step is 16 in total. In reality, pages have no labels such as a, and are given integer numbers (0 to n-1). Labels such as a were added only to make the figure easier to understand.
For reference, the number of people at each vertex at the end of the first calculation step is
page 0 13.333333
page 1 16.000000
page 2 6.500000
page 3 9.166667
page 4 5.000000
You may find this useful as a reference.
Sample 2
Input
5 6 0 1 3 0 3 4 1 2 1 2 1 2 3 4 2 4 3 1
Output
0.000000 10.000000 14.285714 10.000000 15.714286
Page 0 is not linked from anywhere. After just one calculation step, the number of people on page 0 becomes 0. The label a on the pages is omitted here. If you are interested, try comparing the calculation results of the 99th and 100th steps. You will see that a difference of one calculation step changes the evaluation of each page significantly. This shows that the common claim that PageRank converges by repeatedly applying a large-scale matrix should not be taken as simply as it sounds.
Sample 3
Input
13 16 0 1 2 1 0 7 2 0 5 2 3 3 3 2 6 4 0 3 5 4 4 6 1 2 7 1 4 7 8 5 8 7 3 8 9 6 9 7 5 10 11 1 11 12 3 12 10 2
Output
55.625000 44.375000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 10.000000 10.000000 10.000000
The network may be split into two parts. One part is centralized, and pages 0 and 1 take everything. The numbers of people on pages 2 and 7 become almost 0 after the calculation and they are judged to have no value, but although 2 and 7 cannot be given a high value, they are linked from other pages and so should have some value. The world turns out not to be simple, and we can see that the simplified calculation has problems. In practice, you will have to agonize over what to calculate, to what extent, and how. Furthermore, it would be even better to look up how the real PageRank handles the case where people pile up on pages that link nowhere. I will also add that calculations in the field become unreliable in precision unless logs are used. However, since the purpose of this problem is to experience this in a simplified way, perform the calculation as specified.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。