Tell me something my friends do not know: Diversity maximization in\n social networks

Antonis Matakos, Aristides Gionis

arXiv (Cornell University) · 2018 · 15 citations · 25 references

DOIFull text

Open access

Concepts

Abstract

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

References

25