PageRankはあなたが発明できたかもしれない

想像してみてください、時は1996年。あなたはAltaVistaのような当時の検索エンジンに不満を感じています。これらのエンジンは主にコンテンツベースの検索を行っており、「Hotels」と検索すると「Hotels for Chickens」の記事が出てくるようなものでした。もっと良い方法があるはずだ、そう思いませんか？ hindsight（後知恵）で言えば、もちろんありました。Sergey BrinとLarry Pageは、まさにこのPageRankというアルゴリズムを考案しました。これはGoogleを家庭の名前（広く知られる存在）にし、彼らに莫大な富をもたらした主要なアルゴリズムの一つでした。SergeyとLarryは二人ともスタンフォードの大学院生だったので、このような素晴らしいアルゴリズムを考案したことは驚くにはあたらないでしょう。しかし、問題は、あなたも偶然同じものにたどり着けたかということです。私はそう思います。PageRankは、その核心において、これらの基本的な特性を象徴しています。すべてのページには「ランク」または評判があります。ページは、別のページにリンクすることでその「ランク」を共有し、一種の承認の印を与えます。ページの総ランク/評判は、その近隣（リンクしているすべてのページ）から得られる評判の合計に、ある最小値が加算されたものです。それだけです。具体的な例でこれを固めましょう。あるページ（例えばBBC News）が50の評判を持っており、5つの異なるページにリンクしていると想像してください。その評判の80%（40）をリンク先のページに分配すると仮定します（残りはすべてのページに均等に分配されます）。すると、各リンク先ページは、BBCから合計40/5 = 8ポイントを得ます。これは非常に小さく（そして驚くほど読みやすい）Pythonプログラムで次のように実現できます。 ```python # incoming[n] は n に向かうすべてのノードを保持 # outgoing[n] は n から出るすべてのノードを保持 # ページは評判の damping% を近隣に分配します。 # (1-damping)% はすべてのページに均等に分配されます。 def pagerank(incoming, outgoing, damping=.85, tolerance=1e-10): n = len(incoming) # 総ページ数 rank = [1 / n] * n # 開始ランク。すべて均等。 minimum_rank = (1 - damping) / n # 各ページは、ランダムジャンプにより、 # 他のすべてのページから少なくともこの値を得ます。 while True: old = rank.copy() for page, neighbors in enumerate(incoming): # あなたは、リンク元のページからこれを得ます（リンク元は # そのランクをリンク先のすべてに均等に分配しています） acquired = sum( old[neighbor] / len(outgoing[neighbor]) for neighbor in neighbors ) rank[page] = minimum_rank + damping * acquired # アルゴリズムが収束するまで if max(abs(a - b) for a, b in zip(rank, old)) < tolerance: return rank ``` そして、それがすべてです。これらの更新を数回実行すると、最終的に各ページのランクが得られ、それは基本的にそれらがどれほど重要かを示します。もちろん、いくつかの仮定がなされています（ダングリングノードがないなど）が、それらは単なる帳簿上の処理であり、あなたはアルゴリズムの要点を理解しました。もし1996年にいる自分を見つけたら、億万長者になるために何をすべきか知っていることになります！