What to read next
A reader of the site has marked a few favourite pages, and the site wants to suggest what to read next. The model is this. The reader wanders along links: on each page, with probability d = 0.85 they follow one of its links, chosen at random with equal probability, and with probability 1 − d they get bored and open one of their favourite pages, also at random with equal probability. From a page with no links at all they always open one of the favourites. If they wander like this for a very long time, the share of time on each page stops changing; that is its importance for this reader. Suggest the ten most important pages, not counting the favourites.
Two tests are the link graph of this site’s three textbooks: the CS course, “Mathematics, the Queen of the Sciences” and the algorithms catalogue.
Input
The first line holds n and m (2 ≤ n ≤ 10,000, 1 ≤ m ≤ 50,000), the number of pages and links. Then m lines a b: a link from page a to page b (a ≠ b, no duplicate links). The last line holds k (1 ≤ k < n) and k distinct numbers of favourite pages.
Output
The numbers of pages other than the favourites in decreasing order of importance, one per line: ten, or all if there are fewer than ten pages besides the favourites. The tests are chosen so that the importances of the first eleven pages differ by more than 10⁻⁷.
Examples
Example 1
6 8 1 2 1 3 2 3 3 4 4 5 5 2 4 6 2 6 1 1
3 2 4 6 5
Example 2
7 8 1 2 2 3 2 4 4 5 5 6 6 4 3 7 1 7 2 1 3
7 4 2 5 6
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is PageRank, but the jumps go not to any page but only to the favourites. How does the formula of one step of the power method change?
2Hint 2
Where should the importance of a page without links go? Read the statement again: from there the reader always jumps.
3The idea
Personalised PageRank. The jump vector v is 1/k on the favourite pages and zero on the rest. A step: each page with links gives the share d of its importance equally along its links; everything else, the share 1 − d of everyone and all the importance of pages without links times d, goes to the favourite pages by the vector v. Repeat until the total change is below 10⁻¹¹, and sort.
4Walkthrough
Why it converges. A step is a linear map that preserves the sum of importances and contracts the difference of two distributions at least d times: the jumps are the same for both, and only the part going along links changes. So the error after t steps is at most dt of the initial one, and for an accuracy of 10⁻¹¹ a couple of hundred steps are enough, fewer in practice. Each step is O(n + m).
A curious detail. If the importance of pages without links is simply lost, the numbers come out different, but the order of the pages is the same: such a solution differs from the correct one by multiplying the whole vector by one number. This holds precisely because what is lost here comes back by the same vector v as the bored reader’s jumps. But ordinary PageRank with jumps to any page gives a different answer: on the real site graph it suggests chapters of “Mathematics, the Queen of the Sciences” that everyone links to a lot, rather than articles next to what was read. For a reader who liked the articles on breadth-first and depth-first search, Dijkstra, topological sorting and spanning trees, the correct answer first suggests A*, the binary heap, the course chapter “Six handshakes” and strongly connected components.
4+Solution
5Complexity
O((n + m) · T), where T is the number of steps, at most log(10⁻¹¹) / log d ≈ 156 at d = 0.85; plus sorting, O(n log n).
6Common mistakes
- Ordinary PageRank. Jumps to any page give a different ranking, as the very first example shows.
- Too few steps. A fixed ten or twenty steps do not always make it: the bound only guarantees that the error decreases at least 1/d ≈ 1.18 times per step.
- Forgetting to exclude the favourites. They are more important than anyone by themselves.