ユーザー投票に基づくランキングアルゴリズム: Delicious と Hacker News

インターネットの出現は「情報爆発」を意味します。

ユーザーが心配するのは、もはや情報量が少なすぎることではなく、情報が多すぎることです。膨大な情報の中から最も重要なコンテンツをいかに迅速かつ効果的に見つけるかが、インターネットの中心的な課題となっています。

現在、さまざまなランキング アルゴリズムが、情報をフィルタリングする主な手段の 1 つとなっています。情報をランク付けするということは、情報を重要度順に並べ、タイムリーに更新することを意味します。ランキングの基準は、情報自体の特性に基づくことも、ユーザーの投票に基づいて、どのような情報を最初にランク付けできるかをユーザーが決定できるようにすることもできます。

次回は、ユーザー投票によるランキングアルゴリズムをいくつか整理して分析します。4回に分けて連載する予定です。今日は第1回目です。

1. おいしい

最も直感的でシンプルなアルゴリズムは、単位時間あたりに受け取る投票数に応じてユーザーをランク付けすることです。最も多くの票を獲得したプロジェクトが当然ながら 1 位になります。

旧バージョンの Delicious には「人気ブックマークランキング」があり、この方法で計算されていました。

「過去60分間に保存された回数」で順位付けされます。 60 分ごとにカウントが行われます。

このアルゴリズムの利点は、比較的シンプルで導入が簡単で、コンテンツが非常に速く更新されることです。欠点は、ランキングの変化が十分にスムーズではなく、前の 1 時間にトップにランクされていたコンテンツが 2 時間目に急落することが多いことです。

2. ハッカーニュース

Hacker News は、リンクを投稿したりトピックについて話し合ったりできるオンライン コミュニティです。

各投稿の前に上向きの三角形があります。内容がよいと思ったらクリックして投票してください。投票数に基づいて、システムは人気記事のランキングを自動的に計算します。ただし、必ずしも最も多くの票を獲得した記事が 1 位になるわけではありません。時間的要素も考慮する必要があります。新しい記事は古い記事よりも良いランキングを獲得する可能性が高くなります。

Hacker News は Paul Graham が開発した Arc 言語で書かれており、ソース コードは arclanguage.org からダウンロードできます。ランキングアルゴリズムは次のように実装されています。

上記のコードを数式に変換します。

で、

P は投稿に対する投票数を表し、投稿者の投票を無視する場合は 1 を減算します。

T は投稿されてからの時間 (時間単位) を表し、最新の投稿によって分母が小さくなりすぎないように 2 が追加されます (2 を選択した理由は、元の記事が他の Web サイトに掲載されてから Hacker News に再投稿されるまでに平均 2 時間かかるためと考えられます)。

G は「重力」の略で、投稿のランキングを下げる力です。デフォルト値は 1.8 です。この値については後で詳しく説明します。

この式から、投稿のランキングを決定する要素は 3 つあります。

最初の要素は投票数Pです。

他の条件は変わらず、得票数が多いほどランキングが上がります。

上の画像からわかるように、同時に公開された 3 つの投稿があり、それぞれ 200、60、30 票 (マイナス 1 で 199、59、29) で、黄色、紫、青で表されています。どの時点でも、黄色の曲線が上にあり、青色の曲線が下にあります。

「投票数の多い投稿」と「投票数の少ない投稿」の差を大きくしたくない場合は、(P-1)^0.8 のように、投票数に 1 未満の指数を追加できます。

2 番目の要素は、投稿してからの時間 T です。

他の条件が同じであれば、投稿が最近公開されたほど、ランキングは高くなります。つまり、投稿のランキングは時間の経過とともに低下し続けます。

前の図からわかるように、24 時間後にはすべての投稿のスコアは基本的に 1 未満になり、ランキングの下位に落ち、上位のランキングは新しいコンテンツになることが確実になります。

3 番目の要因は重力係数 G です。

その値によって、時間の経過とともにランキングがどれだけ速く下がるかが決まります。

上図からわかるように、3つの曲線の他のパラメータは同じであり、Gの値はそれぞれ1.5、1.8、2.0です。 G 値が大きいほど、曲線が急峻になり、ランキングの低下が速くなります。つまり、ランキングの更新が速くなることを意味します。

アルゴリズムの構成を理解することで、独自のアプリケーションに合わせてパラメータ値を調整できます。

[参考文献]

1. Hacker Newsのランキングアルゴリズムの仕組み
2. 自慢できる人気アルゴリズムを構築する方法

原文: http://www.ruanyifeng.com/blog/2012/02/ranking_algorithm_hacker_news.html

【編集者のおすすめ】

1. 再帰アルゴリズムと最適化アルゴリズムの比較
2. マット・カッツのブログ投稿: Google のアルゴリズムの最新の変更点 10 件
3. アルゴリズム学習のための動的プログラミング戦略の紹介
4. PHP+MySQL アプリケーションで XOR 暗号化アルゴリズムを使用する
5. 過去10年間のGoogleアルゴリズムの変化