kenju's blog

About Programming, Mathematics, Security and Blockchain

各社サービスのランキングアルゴリズムロジックの検討

tl;dr

  • HN, Reddit, Stack Overflow, Qiitaのランキングアルゴリズムを調査した
  • ただし、必ずしも最新のロジックが以下の記事に基づいているとは限らない

Hacker News

medium.com

シンプルにUpvoteに対して1時間単位での時間減衰があるアルゴリズムとなっている。

  • 基本は「ポイント」(各ユーザーがupvoteできる)数
  • 時間減衰(単位はHour)・重み付けあり
Score = (P-1) / (T+2)^G

where,
P = points of an item (and -1 is to negate submitters vote)
T = time since submission (in hours)
G = Gravity, defaults to 1.8 in news.arc

なお、本記事に対するHacker News自身のスレッド にて、記事内で紹介されたアルゴリズムの議論がなされている。幾つか抜粋すると、

  • 上記アルゴリズムの欠点として、「Wall-clock hours(人間が起きている時間帯)を考慮していないため、深夜に投稿された記事と日中に投稿された記事のスコアが異なる」
  • Hacker Newsのランキングは非常にシンプル。最近自分のランキングアルゴリズムであらゆる要素を考慮に入れようとしたら、関係ない要素に時間を費やして間違った方向に進んでしまった
  • それぞれのVoteに対してタイムスタンプを付与する方向もありでは

Reddit | Hot Ranking

medium.com

情報の「フレッシュさ」が大きなウェイトを占めるアルゴリズムとなっている。

  • 10を底、「Upvote マイナス Downvote」を真数とした対数に、エポック時間を足し引きしたもの
    • エポック時間は、Upvote > Downvote なら正に、Upvote < Downvote なら負に働く
  • Upvote > Downvote かつ、投稿時間が最近のものほどランクが上に来る
    • Hacker Newsでは時間減衰だが、RedditのHot Rankingでは減衰というより、新鮮な投稿に対してスコアが優位になる方式

hot ranking algorithms

Reddit | Best Comments

How Not To Sort By Average Rating – Evan Miller

Wilson Scoreを用いているとのこと。詳細は理解できていないが、ざっくりいうと、

  • 実際のVote数を標本として全ユーザーからVoteされた場合のスコアを推定しているため、「Upvote 1件, Downvote 0件」を「Upvote 500件、Downvote 20件」のような場合において前者をより上位にスコアリングするような結果を避けることができる

アルゴリズムと思われる。

Stack Overflow

meta.stackexchange.com

Meta.StackExchange は、Stack Overflow本体のサービスの方向性などについて、ユーザー同士で議論するコミュニティ。このスレッドでは、Stack Overflowにおけるランキングの是非について議論されている。

Update…に書いてある記述内容によると、Stack Overflowのhotタブアルゴリズム

Update: Note that this formula is what is used on the hot tab linked from the homepage of each site.

  • ざっくり言うと、「閲覧数、質問の回答数x質問のスコア、回答のスコア合計」を、「hour単位の時間数(と質問の編集時間の差)を利用して時間減退」させたもの
  • 他のサービスとの特徴は、「質問」と「回答」それぞれにスコアがついているということ、かつ微妙に重みは調整されているということ
  • 質問のスコアとそれに対する回答数、回答のスコア合計が比較的スコアに響きやすいことから、質問・回答のやり取りとそれらに対して一定時間内についたスコアが「Hotらしさ」と定義されている、とみてとれる
(log(Qviews)*4) + ((Qanswers * Qscore)/5) + sum(Ascores)
--------------------------------------------------------
((QageInHours+1) - ((QageInHours - Qupdated)/2)) ^ 1.5

Stack Exchange

meta.stackexchange.com

Stack ExchangeのTOP画面 の「hot」タブのアルゴリズム

  • 質問の時間減衰あり。Stack Overflowの「hot」タブと異なり、編集時間を母数の計算から除外している
  • この公式には現れていないが、Stack Overflowで埋め尽くされてしまわないよう、他のサービスと重み付けは調整されている
(MIN(AnswerCount, 10) * QScore) / 5 + AnswerScore
-------------------------------------------------
         MAX(QAgeInHours + 1, 6) ^ 1.4

※ Beta版当時の議論の模様。現在で言う以下リンクのこと => http://stackoverflow.com/?tab=hot

Qiita | Contribution

QiitaのContribution算出基準を変更し、ユーザーページの表示も新しくしました - Qiita Blog Qiitaの新しいContribution算定ロジックを解読してみた - Qiita

いいね、ストック、編集リクエストなど、Contributionに寄与しうる複数の要素が存在し、それぞれの重みを調整して独自性を出すアルゴリズムとなっている。上記記事にもある通り、「Qiitaのユーザコミュニティへの貢献」を表すことが目的らしい。

  • 時間減衰なし
  • 重み付け有り。大体以下のような感じ
    • 記事へのいいね = 1
    • コメントへの「いいね」 = 0.5
    • 編集リクエストを送った記事へのいいね = 0.1(上限あり)
    • ストック数 = 0