Inferring the strength of social ties: A community-driven approach

Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis

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

13 Citations (Scopus)
143 Downloads (Pure)


Online social networks are growing and becoming denser. The social connections of a given person may have very high variability: from close friends and relatives to acquaintances to people who hardly know. Inferring the strength of social ties is an important ingredient for modeling the interaction of users in a network and understanding their behavior. Furthermore, the problem has applications in computational social science, viral marketing, and people recommendation. In this paper we study the problem of inferring the strength of social ties in a given network. Our work is motivated by a recent approach [27], which leverages the strong triadic closure (STC) principle, a hypothesis rooted in social psychology [13]. To guide our inference process, in addition to the network structure, we also consider as input a collection of tight communities. Those are sets of vertices that we expect to be connected via strong ties. Such communities appear in different situations, e.g., when being part of a community implies a strong connection to one of the existing members. We consider two related problem formalizations that reflect the assumptions of our setting: small number of STC violations and strong-tie connectivity in the input communities. We show that both problem formulations are NP-hard. We also show that one problem formulation is hard to approximate, while for the second we develop an algorithm with approximation guarantee. We validate the proposed method on real-world datasets by comparing with baselines that optimize STC violations and community connectivity separately.

Original languageEnglish
Title of host publicationKDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Number of pages9
VolumePart F129685
ISBN (Electronic)9781450348874
Publication statusPublished - 13 Aug 2017
MoE publication typeA4 Article in a conference publication
EventACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Halifax, Canada
Duration: 13 Aug 201717 Aug 2017
Conference number: 23


ConferenceACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Abbreviated titleKDD


  • Approximation algorithms
  • Network inference
  • Social network analysis
  • Strong triadic closure

Fingerprint Dive into the research topics of 'Inferring the strength of social ties: A community-driven approach'. Together they form a unique fingerprint.

Cite this