2016 · 104 citations · 37 references
ComputingComputer ScienceData ScienceAlgorithmsData MiningOptimizationApproximation AlgorithmsConstrained OptimizationData SummarizationDiscrete OptimizationOptimization TheoryText SummarizationConstraintsKnapsack ProblemsPersonalized SummarizationQuery ComplexitySubmodular MaximizationSubmodular OptimizationSummarizationUser Preferences
Can we summarize multi-category data based on user preferences in a scalable manner? Many utility functions used for data summarization satisfy submodularity, a natural diminishing returns property. We cast personalized data summarization as an instance of a general submodular maximization problem subject to multiple constraints. We develop the first practical and FAst coNsTrained submOdular Maximization algorithm, FANTOM, with strong theoretical guarantees. FANTOM maximizes a submodular function (not necessarily monotone) subject to the intersection of a p-system and l knapsacks constrains. It achieves a (1+e)(p+1)(2p+2l+1)/p approximation guarantee with only O(nrp log(n)/e) query complexity (n and r indicate the size of the ground set and the size of the largest feasible solution, respectively). We then show how we can use FANTOM for personalized data summarization. In particular, a p-system can model different aspects of data, such as categories or time stamps, from which the users choose. In addition, knapsacks encode users' constraints including budget or time. In our set of experiments, we consider several concrete applications: movie recommendation over 11K movies, personalized image summarization with 10K images, and revenue maximization on the YouTube social networks with 5000 communities. We observe that FANTOM constantly provides the highest utility against all the baselines.
37
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7