Link-based ranking of web pages

Link-based ranking scores a page by the pages that link to it. A page that many pages link to, especially important ones, ranks higher.

The idea is that rank flows along links, and you repeat the flow until the numbers settle. By the end you will run it on a small web and read the result.

Word scores such as tf-idf only look at the words on a page. Anyone can write a page with the right words. A link is a vote from another page, and it is harder to fake.

So a page with many in-links is likely to be useful. And a link from a well-linked page counts for more than one from a page nobody links to.

Start by giving every page the same rank: with four pages, 0.25 each. Then, in each round, every page splits its rank equally among the pages it links to, and sends one share down each link.

A page's new rank is what it receives. C has three in-links, so it collects the most.

A page with no in-links would fall to 0, and a loop of pages could keep all the rank. To stop this, each round a share of rank is spread evenly instead of following links. This is called damping.

With a damping of 0.85, a page gets 0.15 divided by the number of pages for free. It then adds 0.85 times what the links bring.

links = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": ["C"]}
damping = 0.85
n = len(links)
ranks = {}
for page in links:
    ranks[page] = 1 / n

new = {}
for page in links:
    new[page] = (1 - damping) / n
for page in links:
    share = ranks[page] / len(links[page])
    for target in links[page]:
        new[target] = new[target] + damping * share
for page in new:
    print(page, round(new[page], 3))
# Make D link to A as well as C. Whose rank changes?

docker exec jupyter python3 -c "links={'A':['B','C'],'B':['C'],'C':['A'],'D':['C']}; r={p:0.25 for p in links}; print({p:round((1-0.85)/4+0.85*sum(r[q]/len(links[q]) for q in links if p in links[q]),3) for p in links})"

docker exec jupyter python3 -c "print(round((1-0.85)/4 + 0.85 * (0.25/2 + 0.25/1 + 0.25/1), 3))"

After one round, C is far ahead. But C sends its rank to A, so A rises in round 2, and then A feeds B and C again. Each page's rank depends on the others, which depend on it.

So repeat the round. The changes shrink, and after about 30 rounds the ranks stop moving to three places. That is the answer.

links = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": ["C"]}
damping = 0.85
n = len(links)
ranks = {}
for page in links:
    ranks[page] = 1 / n

for turn in range(1, 31):
    new = {}
    for page in links:
        new[page] = (1 - damping) / n
    for page in links:
        share = ranks[page] / len(links[page])
        for target in links[page]:
            new[target] = new[target] + damping * share
    ranks = new
    if turn in [1, 2, 3, 30]:
        print(turn, round(ranks["A"], 3), round(ranks["B"], 3), round(ranks["C"], 3), round(ranks["D"], 3))
# Print the total of the four ranks after turn 30. What do you expect?

A search system combines a link score with word scores such as tf-idf, and many other signals. A page can be popular but about the wrong thing, so the words still matter.

Because a link is a vote, people try to fake them. Real systems watch for that, which is why a link score is never used alone.

Draw a web of five pages of your own, such as course pages of your college. Link each to one or two others. Guess which page will rank highest, then run the code on it.

Then give one page a link to itself and see whether that helps it. Say why a real system would ignore such a link.