Schlagwort-Archive: Kommentar

„Heiße Themen“: Sortierung bei Hacker News, reddit & delicio.us

Die Sortierung von Nachrichten nach Neuigkeit oder Popularität ist trivial und ohne größeren Einsatz von Gehirnschmalz zu bewerkstelligen: etwa mit dem SQL-Statement ORDER BY date DESC bzw. ORDER BY likes DESC. Möchte man jedoch die Themen ausgeben, die momentan populär sind, kommt man mit einfachen Statements nicht mehr weiter. Im Folgenden werden drei Algorithmen von Hacker News, Reddit und delicio.us vorgestellt, die auch hier auf Englisch zusammengefasst sind.

Intuitiver Hacker News-Ansatz

Der intuitive Ansatz für die Problemstellung ist, solche Themen anzuzeigen, deren Bewertung hoch ist und deren Veröffentlichungstermin noch nicht lange her ist. Sei p die Anzahl der positiven Bewertungen (jeder Benutzer kann bei Hacker News nur eine positive Bewertung pro Thema abgeben) und t die Anzahl der Stunden, seitdem das Thema veröffentlicht wurde:

Algorithmus von Hacker News

Je länger also der Veröffentlichungszeitpunkt her ist, desto größer wird der Nenner. Da der Nenner mit der Potenz von 1,5 pro Stunde wächst, müssen die Votes ebenfalls potenziell mit der Zeit zunehmen, um f_h(p, t) auf gleichem Niveau zu halten.

Auch wenn keine Votes für das Thema eingehen, muss die Bewertungsfunktion f_h(p, t) jede Stunde neu berechnet werden. Dieses Problem hat der Reddit-Algorithmus nicht.

Reddit-Algorithmus

Anstatt die Bewertungen mit der Zeit exponentiell zu senken, bleibt bei Reddit die Bewertung über die Zeit gleich. Neue Themen erhalten stattdessen einen höheren Summanden, sodass ihre Bewertung höher ist. Der Reddit-Algorithmus ist etwas umfangreicher und passt nicht in eine einfache Formel. Zunächst definieren wir t_s als Differenz der Sekunden zwischen dem 08.12.2005 07:46:43 und dem Veröffentlichungsdatum des Themas:

t_s

Warum Reddit gerade den 08.12.2005 gewählt hat, ist nicht bekannt..

Da man bei Reddit sowohl positiv als auch negativ bewerten kann, wird x als Differenz der positiven (U) und negativen (D) Bewertungen definiert:

x

Wir definieren y als Signum- oder Vorzeichenfunktion von x. Wenn x > 0, ist y = +1. Wenn x = 0, ist y =0. Wenn x < 0, ist y = -1:

y

Und schließlich definieren wir z wie folgt

z

Ist der Betrag von x = 0, wird 1 genommen, sonst der Betrag von x.

Kommen wir zur eigentlichen Bewertungsfunktion. Mit dieser Funktion werden die Themen bewertet, sodass jene Themen mit der höchsten Bewertung die „heißen Themen“ darstellen:

Algorithmus von reddit

Funktionsgraph des Zehnerlogarithmus
Funktionsgraph des Zehnerlogarithmus (Quelle:Wikipedia)

Der erste Summand ist der „Bewertungssummand“. Wir sehen anhand des Funktionsgraph des Zehnerlogarithmus rechts, warum z so gewählt ist, dass er mindestens 1 ist. Der Summand ist somit immer 0 oder positiv sein.

Der Eintrag mit der höchsten Bewertung bei Reddit hat ein x von 21875. Der erste Summand ist bei diesem Eintrag also
Erster Summand: reddit

Der zweite Summand ist der „Zeitsummand“. y gibt aufgrund positiver/negativer/neutraler Bewertungen an, ob der Zeitsummand addiert, subtrahiert oder gar nicht berücksichtigt werden soll.

t_s ist die Zeitdifferenz in Sekunden. Schauen wir uns ein paar Beispiele an und stellen (Oh, Wunder!) fest, dass t_s mit der Zeit immer größer wird:

t_s Jetzt

t_s 2009

t_s wird noch durch 45.000 geteilt. 45.000 Sekunden sind 12,5 Stunden. Der Zeitsummand erhöht sich also alle 12,5 Stunden um 1. Das bedeutet, dass innerhalb von 12,5 Stunden der Bewertungssummand um 1 zulegen müsste, um das höhere Alter des Beitrags zu kompensieren. Der Bewertungssummand steigt um 1, wenn die Differenz zwischen positiven und negativen Bewertungen, um die Zehnerpotenz zunimmt. Von 1 auf 10 ist ja noch easy, aber es wird immer härter: von 10 auf 100, von 100 auf 1000, von 1000 auf 10.000 etc.

Ein Problem an dem Reddit-Algorithmus ist, dass die Bewertungen aufgrund des „Zeitsummands“ immer weiter steigt und man irgendwann an Grenzen von Speichergrößen stoßen wird. Wann dieser Zeitpunkt erreicht ist, habe ich nicht errechnet.. Vielleicht liefert ja ein Leser das Datum nach? ;)

HOT & delicio.us

Generell muss man sich die Frage stellen, ob die zwei genannten Algorithmen wirklich das liefern, was gerade populär ist. Auf meinem Blog beobachte ich nämlich zwei verschiedene Besucher- und Aktivitätsverläufe. Zum Einen den Blockbuster-Verlauf, sprich: gerade einen Artikel veröffentlicht und sofort Kommentare und Besucher. Und zum Anderen den Sleeper-Verlauf: der Artikel wird veröffentlicht und erst nach Monaten oder Jahren von den Besuchern entdeckt. Auch wenn der Sleeper-Verlauf seltener auftritt, bekommen „Hacker News“- und Reddit-Besucher nichts davon mit, weil das Thema, obwohl es gerade „hot“ ist, zu alt ist, um in den „heißen Themen“ zu landen.

Bei aktuellen Nachrichten ist der Sleeper-Verlauf vernachlässigbar, aber bei Bookmarks wie bei delicio.us, kann es sehr wohl relevant sein, dass ein „alter Bookmark“ gerade wieder „hot“ ist. delicio.us hat daher einen einfachen Ansatz, um heiße Bookmarks zu erkennen:

  • Welche Links wurden in der vergangenen Stunde am häufigsten gebookmarkt?

Fazit

Es gibt verschiedene Ansätze „heiße Themen“ zu erhalten.

  • Der intuitive Ansatz von Hacker News ist mit höherem Aufwand verbunden, da sich jede Stunde die Bewertung ändert und neu berechnet werden muss. Der Sleeper-Verlauf wird zudem nicht erkannt.
  • Der Reddit-Algorithmus bedeutet weniger Aufwand, allerdings erkennt er den Sleeper-Verlauf nicht.
  • Der delicio.us Ansatz erkennt zwar Blockbuster und Sleeper-Verlauf, allerdings kann nicht garantiert werden, dass auf kleinen Plattformen mit wenig User-Aktionen ausreichend Bewertungen vorhanden sind. Wenn keine oder wenig Bewertungen in dem Zeitraum abgegeben wurden, können keine „heiße Themen“ angezeigt werden.

Ungelesen (1)

In dieser Kategorie werde ich alle Webfundstücke verlinken, die absolute Must-Reads sind. Leider finde ich einfach nicht immer die Zeit, alle interessanten Links als volle Blog-Artikel zu verwurschteln. Here we go: