{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T19:28:45Z","timestamp":1778354925593,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T00:00:00Z","timestamp":1579219200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T00:00:00Z","timestamp":1579219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["615517"],"award-info":[{"award-number":["615517"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["G091017N"],"award-info":[{"award-number":["G091017N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["654024"],"award-info":[{"award-number":["654024"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the<jats:italic>strength<\/jats:italic>of social ties, access to such information may be restricted or impractical to obtain. Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the<jats:italic>Strong Triadic Closure<\/jats:italic>(STC) property. The STC property states that if person<jats:italic>A<\/jats:italic>has strong social ties with persons<jats:italic>B<\/jats:italic>and<jats:italic>C<\/jats:italic>,<jats:italic>B<\/jats:italic>and<jats:italic>C<\/jats:italic>must be connected to each other as well (whether with a weak or strong tie). They exploited this property to formulate the inference of the strength of social ties as a NP-hard maximization problem, and proposed two approximation algorithms. We refine and improve this line of work, by developing a sequence of linear relaxations of the problem, which can be solved exactly in polynomial time. Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak), which also allows one to avoid making arbitrary strong\/weak strength assignments when the network topology provides inconclusive evidence. Moreover, these relaxations allow us to easily change the objective function to more sensible alternatives, instead of simply maximizing the number of strong edges. An extensive theoretical analysis leads to two efficient algorithmic approaches. Finally, our experimental results elucidate the strengths of the proposed approach, while at the same time questioning the validity of leveraging the STC property for edge strength inference in practice.<\/jats:p>","DOI":"10.1007\/s10618-020-00673-0","type":"journal-article","created":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T06:03:02Z","timestamp":1579240982000},"page":"611-651","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Relaxing the strong triadic closure problem for edge strength inference"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7820-6883","authenticated-orcid":false,"given":"Florian","family":"Adriaens","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tijl","family":"De Bie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jefrey","family":"Lijffijt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonis","family":"Matakos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Polina","family":"Rozenshtein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,17]]},"reference":[{"key":"673_CR1","doi-asserted-by":"publisher","unstructured":"Ahmed N, Neville J, Rossi R, Duffield N (2015) Efficient graphlet counting for large networks, pp 1\u201310. https:\/\/doi.org\/10.1109\/ICDM.2015.141","DOI":"10.1109\/ICDM.2015.141"},{"key":"673_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-319-57454-7_23","volume-title":"Advances in knowledge discovery and data mining","author":"NK Ahmed","year":"2017","unstructured":"Ahmed NK, Rossi RA, Willke TL, Zhou R (2017) Edge role discovery via higher-order structures. In: Kim J, Shim K, Cao L, Lee JG, Lin X, Moon YS (eds) Advances in knowledge discovery and data mining. Springer, Cham, pp 291\u2013303"},{"key":"673_CR3","unstructured":"ApS M (2015) The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28). http:\/\/docs.mosek.com\/7.1\/toolbox\/index.html"},{"key":"673_CR4","doi-asserted-by":"crossref","unstructured":"Backstrom L, Kleinberg J (2014) Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on Facebook. In: Proceedings of the 17th ACM conference on computer supported cooperative work & social computing. ACM, pp 831\u2013841","DOI":"10.1145\/2531602.2531642"},{"key":"673_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge"},{"key":"673_CR6","unstructured":"Chen Y, Dwivedi R, Wainwright MJ, Yu B (2017) Fast mcmc sampling algorithms on polytopes. arXiv:1710.08165"},{"issue":"11","key":"673_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629438","volume":"57","author":"P De Meo","year":"2014","unstructured":"De Meo P, Ferrara E, Fiumara G, Provetti A (2014) On facebook, most ties are weak. Commun ACM 57(11):78\u201384. https:\/\/doi.org\/10.1145\/2629438","journal-title":"Commun ACM"},{"key":"673_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, crowds, and markets: reasoning about a highly connected world","author":"D Easley","year":"2010","unstructured":"Easley D, Kleinberg J (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New York"},{"issue":"2","key":"673_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0304-3975(89)90133-3","volume":"66","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner H, Rote G, Welzl E (1989) Testing the necklace condition for shortest tours and optimal factors in the plane. Theor Comput Sci 66(2):157\u2013180","journal-title":"Theor Comput Sci"},{"key":"673_CR10","doi-asserted-by":"publisher","unstructured":"Fire M, Tenenboim L, Lesser O, Puzis R, Rokach L, Elovici Y (2011) Link prediction in social networks using computationally efficient topological features. In: 2011 IEEE third international conference on privacy, security, risk and trust and 2011 IEEE third international conference on social computing, pp 73\u201380. https:\/\/doi.org\/10.1109\/PASSAT\/SocialCom.2011.20","DOI":"10.1109\/PASSAT\/SocialCom.2011.20"},{"key":"673_CR11","doi-asserted-by":"crossref","unstructured":"Gilbert E, Karahalios K (2009) Predicting tie strength with social media. In: Proceedings of the SIGCHI conference on human factors in computing systems. ACM, pp 211\u2013220","DOI":"10.1145\/1518701.1518736"},{"key":"673_CR12","doi-asserted-by":"crossref","unstructured":"Granovetter MS (1977) The strength of weak ties. In: Social networks. Elsevier, pp 347\u2013367","DOI":"10.1016\/B978-0-12-442450-0.50025-0"},{"key":"673_CR13","unstructured":"Grant M, Boyd S (2014) CVX: Matlab software for disciplined convex programming, version 2.1. http:\/\/cvxr.com\/cvx"},{"key":"673_CR14","doi-asserted-by":"publisher","unstructured":"Grover A, Leskovec J (2016) Node2vec: scalable feature learning for networks. In: Proceedings of the 22Nd ACM SIGKDD international conference on knowledge discovery and data mining, ACM, New York, NY, USA, KDD\u201916, pp 855\u2013864. https:\/\/doi.org\/10.1145\/2939672.2939754","DOI":"10.1145\/2939672.2939754"},{"key":"673_CR15","doi-asserted-by":"publisher","unstructured":"Gupte M, Eliassi-Rad T (2011) Measuring tie strength in implicit social networks. In: Proceedings of the 3rd annual ACM web science conference, WebSci\u201912. https:\/\/doi.org\/10.1145\/2380718.2380734","DOI":"10.1145\/2380718.2380734"},{"key":"673_CR16","first-page":"52","volume":"40","author":"WL Hamilton","year":"2017","unstructured":"Hamilton WL, Ying R, Leskovec J (2017) Representation learning on graphs: methods and applications. IEEE Data Eng Bull 40:52\u201374","journal-title":"IEEE Data Eng Bull"},{"key":"673_CR17","volume-title":"Social network data analytics","author":"MA Hasan","year":"2011","unstructured":"Hasan MA, Zaki MJ (2011) A survey of link prediction in social networks. In: Aggarwal C (ed) Social network data analytics. Springer, Boston"},{"issue":"1","key":"673_CR18","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J (1999) Clique is hard to approximate within $$n^{1-\\varepsilon }$$. Acta Math 182(1):105\u2013142","journal-title":"Acta Math"},{"key":"673_CR19","doi-asserted-by":"publisher","unstructured":"Henderson K, Gallagher B, Eliassi-Rad T, Tong H, Basu S, Akoglu L, Koutra D, Faloutsos C, Li L (2012) Rolx: structural role extraction & mining in large graphs. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining. https:\/\/doi.org\/10.1145\/2339530.2339723","DOI":"10.1145\/2339530.2339723"},{"issue":"3","key":"673_CR20","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J Comput"},{"issue":"3","key":"673_CR21","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum DS (1983) Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl Math 6(3):243\u2013254","journal-title":"Discrete Appl Math"},{"issue":"6","key":"673_CR22","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"DS Hochbaum","year":"1994","unstructured":"Hochbaum DS, Naor J (1994) Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J Comput 23(6):1179\u20131192","journal-title":"SIAM J Comput"},{"issue":"1","key":"673_CR23","doi-asserted-by":"publisher","first-page":"e52168","DOI":"10.1371\/journal.pone.0052168","volume":"8","author":"JJ Jones","year":"2013","unstructured":"Jones JJ, Settle JE, Bond RM, Fariss CJ, Marlow C, Fowler JH (2013) Inferring tie strength from online directed behavior. PLoS ONE 8(1):e52168","journal-title":"PLoS ONE"},{"key":"673_CR24","unstructured":"Kang B, Lijffijt J, De\u00a0Bie T (2019) Conditional network embeddings. In: International conference on learning representations. https:\/\/openreview.net\/forum?id=ryepUj0qtX"},{"key":"673_CR25","unstructured":"Kendall MGMG, Dickinson GJ (1990) Rank correlation methods, 5th edn. E. Arnold, London; Oxford University Press, New York. \u201cA Charles Griffin title\u201d. http:\/\/www.zentralblatt-math.org\/zmath\/en\/search\/?an=0732.62057"},{"key":"673_CR26","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"673_CR27","doi-asserted-by":"publisher","unstructured":"Lu L, Zhou T (2010) Link prediction in weighted networks: the role of weak ties. https:\/\/doi.org\/10.1209\/0295-5075\/89\/18001","DOI":"10.1209\/0295-5075\/89\/18001"},{"issue":"1","key":"673_CR28","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/BF01585180","volume":"62","author":"S Mehrotra","year":"1993","unstructured":"Mehrotra S, Ye Y (1993) Finding an interior point in the optimal face of linear programs. Math Program 62(1):497\u2013515","journal-title":"Math Program"},{"issue":"1","key":"673_CR29","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser GL, Trotter LE (1975) Vertex packings: structural properties and algorithms. Math Program 8(1):232\u2013248","journal-title":"Math Program"},{"issue":"1","key":"673_CR30","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2877200","volume":"41","author":"H Pham","year":"2016","unstructured":"Pham H, Shahabi C, Liu Y (2016) Inferring social strength from spatiotemporal data. ACM Trans Database Syst 41(1):7","journal-title":"ACM Trans Database Syst"},{"key":"673_CR31","doi-asserted-by":"publisher","unstructured":"Rademacher LA (2007) Approximating the centroid is hard. In: Proceedings of the twenty-third annual symposium on computational geometry, ACM, New York, NY, USA, SCG\u201907, pp 302\u2013305. https:\/\/doi.org\/10.1145\/1247069.1247123","DOI":"10.1145\/1247069.1247123"},{"key":"673_CR32","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2349913","author":"R Rossi","year":"2014","unstructured":"Rossi R, Ahmed N (2014) Role discovery in networks. IEEE Trans Knowl Data Eng. https:\/\/doi.org\/10.1109\/TKDE.2014.2349913","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"673_CR33","first-page":"363","volume":"45","author":"RA Rossi","year":"2012","unstructured":"Rossi RA, McDowell LK, Aha DW, Neville J (2012) Transforming graph data for statistical relational learning. J Artif Int Res 45(1):363\u2013441","journal-title":"J Artif Int Res"},{"key":"673_CR34","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Inferring the strength of social ties: a community-driven approach. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1017\u20131025","DOI":"10.1145\/3097983.3098199"},{"key":"673_CR35","volume-title":"Soziologie Untersuchungen \u00fcber die Formen der Vergesellschaftung","author":"G Simmel","year":"1908","unstructured":"Simmel G (1908) Soziologie Untersuchungen \u00fcber die Formen der Vergesellschaftung. Duncker & Humblot, Berlin"},{"key":"673_CR36","doi-asserted-by":"crossref","unstructured":"Sintos S, Tsaparas P (2014) Using strong triadic closure to characterize ties in social networks. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1466\u20131475","DOI":"10.1145\/2623330.2623664"},{"issue":"3","key":"673_CR37","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J ACM 51(3):385\u2013463","journal-title":"J ACM"},{"key":"673_CR38","doi-asserted-by":"crossref","unstructured":"Tang W, Zhuang H, Tang J (2011) Learning to infer social ties in large networks. In: Joint European conference on machine learning and knowledge discovery in databases. Springer, pp 381\u2013397","DOI":"10.1007\/978-3-642-23808-6_25"},{"key":"673_CR39","doi-asserted-by":"crossref","unstructured":"Tang J, Lou T, Kleinberg J (2012) Inferring social ties across heterogenous networks. In: Proceedings of the fifth ACM international conference on Web search and data mining. ACM, pp 743\u2013752","DOI":"10.1145\/2124295.2124382"},{"issue":"2","key":"673_CR40","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2746230","volume":"34","author":"J Tang","year":"2016","unstructured":"Tang J, Lou T, Kleinberg J, Wu S (2016) Transfer learning to infer social ties across heterogeneous networks. ACM Trans Inf Syst 34(2):7","journal-title":"ACM Trans Inf Syst"},{"key":"673_CR41","doi-asserted-by":"crossref","unstructured":"Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in Facebook. In: Proceedings of the 2nd ACM SIGCOMM workshop on social networks (WOSN\u201909)","DOI":"10.1145\/1592665.1592675"},{"key":"673_CR42","doi-asserted-by":"crossref","unstructured":"Xiang R, Neville J, Rogati M (2010) Modeling relationship strength in online social networks. In: Proceedings of the 19th international conference on world wide web. ACM, pp 981\u2013990","DOI":"10.1145\/1772690.1772790"},{"key":"673_CR43","doi-asserted-by":"crossref","unstructured":"Zhou L, Yang Y, Ren X, Wu F, Zhuang Y (2018) Dynamic network embedding by modeling triadic closure process. In: AAAI Conference on Artificial Intelligence. https:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI18\/paper\/view\/16572","DOI":"10.1609\/aaai.v32i1.11257"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-020-00673-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10618-020-00673-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-020-00673-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T19:16:17Z","timestamp":1665515777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10618-020-00673-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,17]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["673"],"URL":"https:\/\/doi.org\/10.1007\/s10618-020-00673-0","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,17]]},"assertion":[{"value":"29 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}