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.

• Publication year

  2011

• Venue

  Knowledge Discovery and Data Mining

• Publication date

  2011-08-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2020408.2020573
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Social Network Effects on Performance and Layoffs: Evidence from the Adoption of a Social Networking Tool

  2011cited by this paper
• New perspectives and methods in link prediction

  2010cited by this paper
• Supervised random walks: predicting and recommending links in social networks

  2010cited by this paper
• Generalized Probabilistic Matrix Factorizations for Collaborative Filtering

  2010cited by this paper
• An energy-efficient mobile recommender system

  2010cited by this paper
• Sampling community structure

  2010cited by this paper
• DivRank: the interplay of prestige and diversity in information networks

  2010influential reference
• Neighbor query friendly compression of social networks

  2010cited by this paper
• Fast nearest-neighbor search in disk-resident graphs

  2010cited by this paper
• Fast Single-Pair SimRank Computation

  2010cited by this paper
• Social action tracking via noise tolerant time-varying factor graphs

  2010cited by this paper
• BBM: bayesian browsing model from petabyte-scale data

  2009cited by this paper
• Ranking objects based on relationships and fixed associations

  2009cited by this paper
• Redundancy, diversity and interdependent document relevance

  2009cited by this paper
• Turning down the noise in the blogosphere

  2009cited by this paper
• Enhancing diversity, coverage and balance for summarization through structure learning

  2009cited by this paper
• Collaborative filtering with temporal dynamics

  2009cited by this paper
• PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations

  2009cited by this paper
• Finding a team of experts in social networks

  2009cited by this paper
• Evaluating Statistical Tests for Within-Network Classifiers of Relational Data

  2009cited by this paper
• Scalable graph clustering using stochastic flows: applications to community discovery

  2009cited by this paper
• PEGASUS: A Peta-Scale Graph Mining System

  2009cited by this paper
• Predicting diverse subsets using structural SVMs

  2008cited by this paper
• Cost-effective outbreak detection in networks

  2007cited by this paper
• Estimating rates of rare events at multiple resolutions

  2007cited by this paper
• Improving Diversity in Ranking using Absorbing Random Walks

  2007influential reference
• Fast Random Walk with Restart and Its Applications

  2006cited by this paper
• Measuring and extracting proximity in networks

  2006cited by this paper
• Mining Compressed Frequent-Pattern Sets

  2005cited by this paper
• Improving recommendation lists through topic diversification

  2005cited by this paper
• Cross-relational clustering with user's guidance

  2005cited by this paper
• Relational link-based ranking

  2004cited by this paper
• Optimal oblivious routing in polynomial time

  2003cited by this paper
• Graph-based anomaly detection

  2003cited by this paper
• Topic-sensitive PageRank

  2002influential reference
• Dependency Networks for Collaborative Filtering and Data Visualization

  2000cited by this paper
• Multilevel k-way hypergraph partitioning

  1999cited by this paper
• Authoritative sources in a hyperlinked environment

  1999cited by this paper
• The PageRank Citation Ranking : Bringing Order to the Web

  1999cited by this paper
• The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries

  1998cited by this paper
• Vertex-reinforced random walk

  1992cited by this paper
• Matrix Perturbation Theory

  1991cited by this paper
• Matrix Perturbation Theory

  1990cited by this paper

• Provable randomized rounding for minimum-similarity diversification

  2022cites this paper
• Serendipity-based Points-of-Interest Navigation

  2020cites this paper
• Web Image Search Re-ranking Dependent on Diversity

  2020cites this paper
• PrefDiv: Efficient Algorithms for Effective Top-k Result Diversification

  2020cites this paper
• Testing the Impact of Semantics and Structure on Recommendation Accuracy and Diversity

  2020cites this paper
• Semi-supervised Classification-based Local Vertex Ranking via Dual Generative Adversarial Nets

  2019cites this paper
• Does Diversity Affect User Satisfaction in Image Search

  2019cites this paper
• Diversifying Seeds and Audience in Social Influence Maximization

  2019cites this paper
• Online Social Media Recommendation Over Streams

  2019cites this paper
• CrowdTravel: Leveraging Cross-Modal CrowdSourced Data for Fine-Grained and Context-Based Travel Route Recommendation

  2019cites this paper
• Search and Aggregation in Big Graphs

  2019cites this paper
• Dissimilarity-constrained node attribute coverage diversification for novelty-enhanced top-k search in large attributed networks

  2018cites this paper
• Fusing Diversity in Recommendations in Heterogeneous Information Networks

  2018cites this paper
• Diversified recommendation method combining topic model and random walk

  2018influential citation
• Diversity in Machine Learning

  2018influential citation
• Search result diversification on attributed networks via nonnegative matrix factorization

  2018cites this paper
• DivGroup: A Diversified Approach to Divide Collection of Patterns into Uniform Groups

  2018cites this paper
• Incorporating Diversity into Influential Node Mining

  2018influential citation
• SIRIF: Supervised influence ranking based on influential network

  2018cites this paper
• A novel parallel distance metric-based approach for diversified ranking on large graphs

  2018cites this paper
• Scalable Aspects Learning for Intent-Aware Diversified Search on Social Networks

  2018cites this paper
• Balancing Authority and Diversity in Influential Node Mining

  2018cites this paper
• NMFDIV: A Nonnegative Matrix Factorization Approach for Search Result Diversification on Attributed Networks

  2017cites this paper
• A survey of query result diversification

  2017cites this paper
• An Influence Propagation View of PageRank

  2017cites this paper
• In Pursuit of the Wisest: Building Cost-Effective Teams of Experts

  2017cites this paper
• A Survey on Recommendation Methods Beyond Accuracy

  2017cites this paper
• Image Re-Ranking Based on Topic Diversity

  2017cites this paper
• Optimized relativity search: node reduction in personalized page rank estimation for large graphs

  2016cites this paper
• MPG: Not So Random Exploration of a City

  2016influential citation
• A Coverage-Based Approach to Recommendation Diversity On Similarity Graph

  2016cites this paper
• Diversified Top-k Similarity Search in Large Attributed Networks

  2016cites this paper
• USTF: A Unified System of Team Formation

  2016cites this paper
• Verso folio: Diversified Ranking for Large Graphs with Context-Aware Considerations

  2016cites this paper
• Leveraging Multiple Features for Image Retrieval and Matching

  2016cites this paper
• Generating Multiple Diverse Summaries

  2016cites this paper
• Multi-relation Based Manifold Ranking Algorithm for API Recommendation

  2016cites this paper
• What Makes a Good Recommendation? - Characterization of Scientific Paper Recommendations

  2016cites this paper
• Creating Diverse Product Review Summaries: A Graph Approach

  2015cites this paper
• An Evaluation of Diversification Techniques

  2015cites this paper
• DiSCern: A diversified citation recommendation system for scientific queries

  2015cites this paper
• Improve Network Clustering via Diversified Ranking

  2015cites this paper
• Optimizing Sentence Modeling and Selection for Document Summarization

  2015cites this paper
• Diversified Ranking Algorithm Based OnFuzzy Concept For Large Graphs

  2014cites this paper
• Subgraph Search in Large Graphs with Result Diversification

  2014cites this paper
• Submodular Reranking with Multiple Feature Modalities for Image Retrieval

  2014cites this paper
• User effort minimization through adaptive diversification

  2014cites this paper
• Answering top-k representative queries on graph databases

  2014cites this paper
• Methods for Finding Interesting Nodes in Weighted Graphs

  2014cites this paper
• Next Generation of Recommender Systems: Algorithms and Applications

  2014cites this paper
• Diversified ranking on graphs from the influence maximization viewpoint

  2014cites this paper
• Measuring the impact of MVC attack in large complex networks

  2014cites this paper
• Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach

  2014cites this paper
• On improving aggregate recommendation diversity and novelty in folksonomy-based social systems

  2014cites this paper
• iHR: an online recruiting system for Xiamen Talent Service Center

  2013cites this paper
• Goal-driven collaborative filtering

  2013cites this paper
• Result Diversification on Spatial, Multidimensional, Opinion, and Bibliographic Data

  2013influential citation
• Ranking Services by Service Network Structure and Service Attributes

  2013cites this paper
• Result Diversification in Automatic Citation Recommendation

  2013cites this paper
• An Optimization Method for Proportionally Diversifying Search Results

  2013influential citation
• Max-sum diversification on image ranking with non-uniform matroid constraints

  2013influential citation
• Diversified recommendation on graphs: pitfalls, measures, and algorithms

  2013influential citation
• Towards a personalized, scalable, and exploratory academic recommendation service

  2013cites this paper
• Retrieval of Relevant and Non-redundant Nodes ∗

  2012cites this paper
• Instant Social Graph Search

  2012cites this paper
• Diversifying Citation Recommendations

  2012influential citation
• GenDeR: A Generic Diversified Ranking Algorithm

  2012cites this paper
• Querying and Mining Chemical Databases for Drug Discovery

  2012cites this paper
• Querying and mining chemical databases for drug discovery

  2012cites this paper
• Social Network Analysis in Enterprise

  2012cites this paper
• Social Network Analysis in Enterprise This paper focuses on the challenges and solutions in mining and analyzing social networks in enterprises; the authors base their study on a social network analysis tool called SmallBlue.

  2012cites this paper
• Learning to Diversify Expert Finding with Subtopics

  2012cites this paper
• Scalable Diversified Ranking on Large Graphs

  2011cites this paper