Inferring the strength of social ties

No Thumbnail Available
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
Date
2017-08-13
Major/Subject
Mcode
Degree programme
Language
en
Pages
9
1017-1025
Series
KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Volume Part F129685
Abstract
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.
Description
| openaire: EC/H2020/654024/EU//SoBigData
Keywords
Approximation algorithms, Network inference, Social network analysis, Strong triadic closure
Other note
Citation
Rozenshtein , P , Tatti , N & Gionis , A 2017 , Inferring the strength of social ties : A community-driven approach . in KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . vol. Part F129685 , ACM , pp. 1017-1025 , ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , Halifax , Canada , 13/08/2017 . https://doi.org/10.1145/3097983.3098199