たくさんリンクされたページは、大事なページ
リンクに基づく順位づけとは、多くのページから、しかも大事なページからリンクされているページを、大事だとみなす考え方です。ページの中の語だけでは、同じ語を含むページが多すぎて、順位がつけられません。
そこで、ページどうしのつながりを、手がかりにします。大事さは、リンクに沿って流れ、くり返し計算すると落ち着きます。
このレッスンのゴール
メモ
ページの順位が、リンクに沿って流れ、くり返しで落ち着く様子を説明できる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| リンク | あるページから、別のページへの案内 | |
| 被リンク | 別のページから、そのページへ向かうリンク | |
| 順位の流れ | ページが、持っている順位を、リンク先に分けること | |
| 反復 | 同じ計算を、くり返し行うこと | |
| 減衰係数 | リンクをたどる割合。ここでは 0.85 | 0.85 |
学生が入力するセルは、このプレビューでは空白です。
順位は、リンクに沿って流れる
ページを、リンクでつながった点だと考えます。各ページは、持っている順位を、リンク先に等しく分けて渡します。
たくさんのページから渡されるほど、そのページの順位は上がります。渡す側が上位のページなら、渡される順位も大きくなります。
1回の計算で、順位を渡し直す
最初は、4ページすべてが 0.25 です。1回ごとに、各ページは順位を、リンク先に等しく分けて渡します。
ただし、全部を渡すのではありません。リンクをたどる割合を 0.85（減衰係数）とし、残りの 0.15 は、全ページに等しく配ります。
ページ C の1回目の順位
docker exec jupyter python3 -c "print(round(0.15 / 4 + 0.85 * (0.25 / 2 + 0.25 / 1 + 0.25 / 1), 3))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: 1回目、2回目、20回目の順位
| ページ | 最初 | 1回目 | 2回目 | 20回目 |
|---|---|---|---|---|
| A | 0.25 | 0.25 | 0.521 | 0.373 |
| B | 0.25 | 0.144 | 0.144 | 0.196 |
| C | 0.25 | 0.569 | 0.298 | 0.394 |
| D | 0.25 | 0.038 | 0.038 | 0.038 |
学生が入力するセルは、このプレビューでは空白です。
くり返すと、値が落ち着く
links = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": ["C"]}
rank = {}
for page in links:
rank[page] = 0.25
for round_number in range(1, 4):
new = {}
for page in links:
new[page] = 0.15 / 4
for page in links:
share = rank[page] / len(links[page])
for target in links[page]:
new[target] = new[target] + 0.85 * share
rank = new
print(round_number, "回目の C:", round(rank["C"], 3))
# range(1, 4) を range(1, 21) に変えて、C の値が落ち着くか見てください。
何回もくり返すと、順位は落ち着く
表のように、1回目と2回目では、順位が大きく動きます。くり返すうちに、動きは小さくなり、やがてほとんど変わらなくなります。
この落ち着いた値が、ページの順位です。数が小さいページでは、20回ほどで十分です。順位の合計は、いつも1です。
よくある間違い
注意
リンクされた数が多いページほど、順位が高いと考えがちです。表では、被リンクが1つの A が、高い順位を保ちます。リンクを出す C が上位だからです。数より、誰からかが効きます。
さらに挑戦: リンクのないページ
課題では、どのページも、1つ以上のリンクを出すと決めています。リンクを1つも出さないページがあると、len(links[page]) が 0 になり、割れません。
そのページの順位を、全ページに等しく配る方法を考えて、書いてみてください。