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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

11 Citations (Scopus)


Social media have a great potential to improve information dissemination in our society, yet, they have been held accountable for a number of undesirable effects, such as polarization and filter bubbles. It is thus important to understand these negative phenomena and develop methods to combat them. In this paper we propose a novel approach to address the problem of breaking filter bubbles in social media. We do so by aiming to maximize the diversity of the information exposed to connected social-media users. We formulate the problem of maximizing the diversity of exposure as a quadratic-knapsack problem. We show that the proposed diversity-maximization problem is inapproximable, and thus, we resort to polynomial non-approximable algorithms, inspired by solutions developed for the quadratic knapsack problem, as well as scalable greedy heuristics. We complement our algorithms with instance-specific upper bounds, which are used to provide empirical approximation guarantees for the given problem instances. Our experimental evaluation shows that a proposed greedy algorithm followed by randomized local search is the algorithm of choice given its quality-vs.-efficiency trade-off.
Original languageEnglish
Title of host publication2018 IEEE International Conference on Data Mining, ICDM 2018
Number of pages10
ISBN (Electronic)9781538691588
ISBN (Print)9781538691601
Publication statusPublished - 2018
MoE publication typeA4 Conference publication
EventIEEE International Conference on Data Mining - Singapore, Singapore
Duration: 17 Nov 201820 Nov 2018

Publication series

NameIEEE International Conference on Data Mining (ICDM)
ISSN (Print)1550-4786
ISSN (Electronic)2374-8486


ConferenceIEEE International Conference on Data Mining
Abbreviated titleICDM


  • Diversity maximization
  • Filter bubble
  • Quadratic knapsack


Dive into the research topics of 'Tell me something my friends do not know: Diversity maximization in social networks'. Together they form a unique fingerprint.

Cite this