arXiv (Cornell University) · 2018 · 15 citations · 25 references
Social SciencesCommunicationComputer ScienceAlgorithmsMass CommunicationOptimizationApproximation AlgorithmsCombinatorial OptimizationGreedy AlgorithmsInformation SpreadNetwork OptimizationSocial MediaApproximation GuaranteesDiversity OptimizationGreedy HeuristicsHeuristicsInformation DisseminationKnapsack ApproximationKnapsack ProblemsUpper Bounds
Social media have a great potential to improve information dissemination in\nour society, yet, they have been held accountable for a number of undesirable\neffects, such as polarization and filter bubbles. It is thus important to\nunderstand these negative phenomena and develop methods to combat them. In this\npaper we propose a novel approach to address the problem of breaking filter\nbubbles in social media. We do so by aiming to maximize the diversity of the\ninformation exposed to connected social-media users. We formulate the problem\nof maximizing the diversity of exposure as a quadratic-knapsack problem. We\nshow that the proposed diversity-maximization problem is inapproximable, and\nthus, we resort to polynomial non-approximable algorithms, inspired by\nsolutions developed for the quadratic-knapsack problem, as well as scalable\ngreedy heuristics. We complement our algorithms with instance-specific upper\nbounds, which are used to provide empirical approximation guarantees for the\ngiven problem instances. Our experimental evaluation shows that a proposed\ngreedy algorithm followed by randomized local search is the algorithm of choice\ngiven its quality-vs.-efficiency trade-off.\n
25
Semidefinite Relaxation of Quadratic Optimization Problems
Zhi‐Quan Luo, Wing‐Kin Ma, Anthony Man–Cho So et al. · IEEE Signal Processing Magazine · 2010 · 3.6K citations
On the Shannon capacity of a graph
László Lovász · IEEE Transactions on Information Theory · 1979 · 1.7K citations
News use across social media platforms 2016
Jeffrey A. Gottfried, Elisa Shearer · 2016 · 1.2K citations