Strengthening ties towards a highly-connected world

Antonis Matakos*, Aristides Gionis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
57 Downloads (Pure)


Online social networks provide a forum where people make new connections, learn more about the world, get exposed to different points of view, and access information that were previously inaccessible. It is natural to assume that content-delivery algorithms in social networks should not only aim to maximize user engagement but also to offer opportunities for increasing connectivity and enabling social networks to achieve their full potential. Our motivation and aim is to develop methods that foster the creation of new connections, and subsequently, improve the flow of information in the network. To achieve our goal, we propose to leverage the strong triadic closure principle, and consider violations to this principle as opportunities for creating more social links. We formalize this idea as an algorithmic problem related to the densest k-subgraph problem. For this new problem, we establish hardness results and propose approximation algorithms. We identify two special cases of the problem that admit a constant-factor approximation. Finally, we experimentally evaluate our proposed algorithm on real-world social networks, and we additionally evaluate some simpler but more scalable algorithms.

Original languageEnglish
Pages (from-to)448-476
Number of pages29
JournalData Mining and Knowledge Discovery
Issue number1
Publication statusPublished - Jan 2022
MoE publication typeA1 Journal article-refereed


  • Densest subgraph discovery
  • Link recommendations
  • STC
  • Strong triadic closure


Dive into the research topics of 'Strengthening ties towards a highly-connected world'. Together they form a unique fingerprint.

Cite this