document: Diversified ranking on large graphs : an optimization viewpoint Diversified ranking on graphs is a fundamental mining task and has a variety of high-impact applications . There are two important open questions here . The first challenge is the measure - how to quantify the goodness of a given top-k ranking list that captures both the relevance and the diversity ? The second challenge lies in the algorithmic aspect - how to find an optimal , or near-optimal , top-k ranking list that maximizes the measure we defined in a scalable way ? In this paper , we address these challenges from an optimization point of view . Firstly , we propose a goodness measure for a given top-k ranking list . The proposed goodness measure intuitively captures both ( a ) the relevance between each individual node in the ranking list and the query ; and ( b ) the diversity among different nodes in the ranking list . Moreover , we propose a scalable algorithm ( linear wrt the size of the graph ) that generates a provably near-optimal solution . The experimental evaluations on real graphs demonstrate its effectiveness and efficiency .
doc_bio_tags: O B O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O B O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O B O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O