Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm building a system similar to Reddit, where users "like" items. "Likes" would be used to determine ranking of items. There's also an "aging" factor, where more recent "likes" count more than ancient "likes".

All in all, it's similar to the algorithm described here.

My problem is that I need to ensure diversity of the items in the result ranking. Each item belongs to a category. Certain categories may be disproportionately popular. I don't want to have all items in the front page (or 2nd page) to belong to Category A, while items from other categories are nowhere to be found.

So are there any clever algorithm that can ensure diversity of results here -- to make sure there's a nice mix of different categories in every page?

Thanks

share|improve this question
2  
Have you tried just putting a hard limit on the number of different items of the same category on a given page? –  Qiaochu Yuan Jul 14 '11 at 5:34
add comment

1 Answer

$L - $ Likes
$A - $ Age
$R - $ Rank

Following formula is used by Hacker News website:

$R \propto \frac{L}{A^\alpha}$

If you want categories to be distributed more evenly then you can use a technique called Histogram Equalization. This is used in image processing.

On X-axis you can plot categories and on Y-axis number of posts in that category. Then perform histogram equalization.

After equalization you get new histogram. Suppose total number of posts on front page are $F$. Then number of posts from $j$ th category are $F \frac{c_j}{\Sigma c_i}$ where $c_i$ is number of posts in $i$ th category.

If distribution is still uneven you can try limiting number of posts in perticular category like Qiaochu Yuan suggested.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.