Problem 608106 · medium · Level 06 Heuristics & Optimization

The Wandering Reader

Markov chain · stationary distribution · random surfer · link analysis · power iteration

A club's wiki wants to list its most important pages. The idea is a random reader who keeps clicking. On each click, the reader on page p:

  • with probability damping, follows one of the links on p, each with equal probability;
  • otherwise (probability 1 - damping) jumps to a page chosen uniformly at random from the whole wiki;
  • if p has no links at all, always jumps to a uniformly random page.

A page's importance is the probability that the reader is on it after many clicks.

Write reader_scores(links, damping, rounds). links[p] is the list of pages that page p links to (no duplicates; every linked page is a key of links). Start with the reader equally likely to be on every page, apply exactly rounds clicks, and return the resulting probabilities as a dict with an entry for every page.

The setup provides wiki_links(n, seed), which returns the links of a random wiki with n pages (a few popular pages attract most links, and some pages have none).

Examples

Input:  links = {"home": ["rules", "events"], "rules": ["home"],
                 "events": ["home", "rules", "photos"], "photos": []},
        damping = 0.85, rounds = 1
Output: {"home": 0.3739583333333333, "rules": 0.2677083333333333,
         "events": 0.196875, "photos": 0.16145833333333334}
Explanation: every page starts at 0.25. Home receives 0.85 * (0.25 from rules
+ 0.25 / 3 from events), and every page receives 0.15 * 0.25 from random jumps
plus 0.25 / 4 from the reader stuck on photos.

Input:  the same links, damping = 0.85, rounds = 50
Output: {"home": 0.3682222516616156, "rules": 0.2836306533069262,
         "events": 0.22101089868072454, "photos": 0.1271361963507336}

Constraints

  • 1 <= len(links) <= 2000, at most 2 * 10**4 links in total
  • 0 <= damping <= 1, 0 <= rounds <= 200
  • floats are compared with a tolerance of 1e-6

Goals

  • Turn a link graph into a Markov chain of a random reader
  • Handle pages without links and random jumps so that the chain is well behaved
  • Propagate the reader's distribution for a fixed number of rounds
Starting Python…