Inferring the strength of social ties: A community-driven approach
dc.contributor | Aalto-yliopisto | fi |
dc.contributor | Aalto University | en |
dc.contributor.author | Rozenshtein, Polina | en_US |
dc.contributor.author | Tatti, Nikolaj | en_US |
dc.contributor.author | Gionis, Aristides | en_US |
dc.contributor.department | Department of Computer Science | en |
dc.contributor.groupauthor | Adj. Prof. Gionis Aris group | en |
dc.contributor.groupauthor | Helsinki Institute for Information Technology (HIIT) | en |
dc.contributor.groupauthor | Myllymäki Petri group (HIIT) | en |
dc.date.accessioned | 2018-09-06T10:16:07Z | |
dc.date.available | 2018-09-06T10:16:07Z | |
dc.date.issued | 2017-08-13 | en_US |
dc.description | | openaire: EC/H2020/654024/EU//SoBigData | |
dc.description.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. | en |
dc.description.version | Peer reviewed | en |
dc.format.extent | 9 | |
dc.format.extent | 1017-1025 | |
dc.format.mimetype | application/pdf | en_US |
dc.identifier.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 | en |
dc.identifier.doi | 10.1145/3097983.3098199 | en_US |
dc.identifier.isbn | 9781450348874 | |
dc.identifier.other | PURE UUID: 3ddd2e68-6999-4641-95bb-82d63e069da5 | en_US |
dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/3ddd2e68-6999-4641-95bb-82d63e069da5 | en_US |
dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85029082118&partnerID=8YFLogxK | en_US |
dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/26625687/strong_backbone.pdf | en_US |
dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/33850 | |
dc.identifier.urn | URN:NBN:fi:aalto-201809064961 | |
dc.language.iso | en | en |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigData | en_US |
dc.relation.ispartof | ACM SIGKDD International Conference on Knowledge Discovery and Data Mining | en |
dc.relation.ispartofseries | KDD 2017 - Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining | en |
dc.relation.ispartofseries | Volume Part F129685 | en |
dc.rights | openAccess | en |
dc.subject.keyword | Approximation algorithms | en_US |
dc.subject.keyword | Network inference | en_US |
dc.subject.keyword | Social network analysis | en_US |
dc.subject.keyword | Strong triadic closure | en_US |
dc.title | Inferring the strength of social ties: A community-driven approach | en |
dc.type | A4 Artikkeli konferenssijulkaisussa | fi |
dc.type.version | acceptedVersion |