Paper: Improving Diversity in Ranking using Absorbing Random Walks

ACL ID N07-1013
Title Improving Diversity in Ranking using Absorbing Random Walks
Venue Human Language Technologies
Session Main Conference
Year 2007
Authors

We introduce a novel ranking algorithm called GRASSHOPPER, which ranks items with an emphasis on diversity. That is, the top items should be different from each other in order to have a broad coverage of the whole item set. Many natural lan- guage processing tasks can benefit from such diversity ranking. Our algorithm is based on random walks in an absorbing Markov chain. We turn ranked items into absorbing states, which effectively pre- vents redundant items from receiving a high rank. We demonstrate GRASSHOP- PER’s effectiveness on extractive text sum- marization: our algorithm ranks between the 1st and 2nd systems on DUC 2004 Task 2; and on a social network analy- sis task that identifies movie stars of the world.