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

Antonis Matakos*, Sijing Tu, Aristides Gionis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)
60 Downloads (Pure)


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 nonapproximable 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
Pages (from-to)3697-3726
Number of pages30
JournalKnowledge and Information Systems
Issue number9
Publication statusPublished - 1 Sep 2020
MoE publication typeA1 Journal article-refereed


  • Combinatorial optimization
  • Diversity maximization
  • Filter bubble
  • Greedy algorithms
  • 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