2011 DiversifiedRankingonLargeGraphs
- (Tong et al., 2011) ⇒ Hanghang Tong, Jingrui He, Zhen Wen, Ravi Konuru, and Ching-Yung Lin. (2011). “Diversified Ranking on Large Graphs: An Optimization Viewpoint.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020573
Subject Headings:
Notes
Cited By
- http://scholar.google.com/scholar?q=%222011%22+Diversified+Ranking+on+Large+Graphs%3A+An+Optimization+Viewpoint
- http://dl.acm.org/citation.cfm?id=2020408.2020573&preflayout=flat#citedby
Quotes
Author Keywords
Abstract
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.
References
;
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2011 DiversifiedRankingonLargeGraphs | Hanghang Tong Ravi Konuru Zhen Wen Ching-Yung Lin Jingrui He | Diversified Ranking on Large Graphs: An Optimization Viewpoint | 10.1145/2020408.2020573 | 2011 |