{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T17:53:07Z","timestamp":1770141187864,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T00:00:00Z","timestamp":1641254400000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["317085"],"award-info":[{"award-number":["317085"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["325117"],"award-info":[{"award-number":["325117"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["834862"],"award-info":[{"award-number":["834862"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["871042"],"award-info":[{"award-number":["871042"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","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":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>strong triadic closure<\/jats:italic> 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 <jats:italic>k<\/jats:italic>-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.<\/jats:p>","DOI":"10.1007\/s10618-021-00812-1","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T06:03:29Z","timestamp":1641276209000},"page":"448-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Strengthening ties towards a highly-connected world"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1003-7101","authenticated-orcid":false,"given":"Antonis","family":"Matakos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5211-112X","authenticated-orcid":false,"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"key":"812_CR1","unstructured":"Adriaens F, Bie TD, Gionis A, Lijffijt J, Rozenshtein P (2018) From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths. CoRR, arXiv:1802.03549"},{"key":"812_CR2","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/s10618-020-00673-0","volume":"34","author":"F Adriaens","year":"2020","unstructured":"Adriaens F, De Bie T, Gionis A, Lijffijt J, Matakos A, Rozenshtein P (2020) Relaxing the strong triadic closure problem for edge strength inference. Data Min Knowl Discov 34:611\u2013651","journal-title":"Data Min Knowl Discov"},{"key":"812_CR3","doi-asserted-by":"publisher","unstructured":"Akcoglu K, Aspnes J, DasGupta B, Kao M-Y (2002) Opportunity cost algorithms for combinatorial auctions. In: Kontoghiorghes EJ, Rustem B, Siokos S (eds) Computational methods in decision-making, economics and finance. Springer, Boston, MA, pp 455\u2013479. https:\/\/doi.org\/10.1007\/978-1-4757-3613-7_23","DOI":"10.1007\/978-1-4757-3613-7_23"},{"key":"812_CR4","doi-asserted-by":"crossref","unstructured":"Arrigo F, Benzi M (2015) Edge modification criteria for enhancing the communicability of digraphs. CoRR arXiv:1508.01056","DOI":"10.1137\/15M1034131"},{"key":"812_CR5","doi-asserted-by":"crossref","unstructured":"Bhaskara A, Charikar M, Chlamtac E, Feige U,Vijayaraghavan A(2010) Detecting high log-densities: an o(n1\/4) approximation for densest k-subgraph. In: STOC, pp 201\u2013210","DOI":"10.1145\/1806689.1806719"},{"issue":"6","key":"812_CR6","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1086\/223238","volume":"67","author":"WR Catton","year":"1962","unstructured":"Catton WR (1962) The acquaintance process. Theodore M. newcomb. Am J Sociol 67(6):704\u2013705","journal-title":"Am J Sociol"},{"key":"812_CR7","doi-asserted-by":"crossref","unstructured":"Chan H, Akoglu L, Tong H (2014) Make it or break it: manipulating robustness in large networks. In: SDM. SIAM, pp 325\u2013333","DOI":"10.1137\/1.9781611973440.37"},{"key":"812_CR8","first-page":"83","volume-title":"Approximation and online algorithms","author":"DZ Chen","year":"2010","unstructured":"Chen DZ, Fleischer R, Li J (2010) Densest k-subgraph approximation on intersection graphs. In: Jansen K, Solis-Oba R (eds) Approximation and online algorithms. Springer, Berlin, pp 83\u201393"},{"key":"812_CR9","doi-asserted-by":"crossref","unstructured":"Demaine ED, Zadimoghaddam M (2010). Minimizing the diameter of a network using shortcut edges. In: SWAT","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"812_CR10","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, Cambridge"},{"issue":"1","key":"812_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J Comput 18(1):30\u201355","journal-title":"SIAM J Comput"},{"key":"812_CR12","doi-asserted-by":"crossref","unstructured":"Garimella K, Morales GDF, Gionis A, Mathioudakis M (2017) Reducing controversy by connecting opposing views. In: WSDM","DOI":"10.1145\/3018661.3018703"},{"key":"812_CR13","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, CHI \u201909, 2009. Association for Computing Machinery, New York, NY, pp 211\u2013220","DOI":"10.1145\/1518701.1518736"},{"key":"812_CR14","unstructured":"Goldberg AV (1984) Finding a maximum density subgraph. Technical report, USA"},{"issue":"6","key":"812_CR15","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1086\/225469","volume":"78","author":"MS Granovetter","year":"1973","unstructured":"Granovetter MS (1973) The strength of weak ties. Am J Sociol 78(6):1360\u20131380","journal-title":"Am J Sociol"},{"key":"812_CR16","doi-asserted-by":"crossref","unstructured":"Khot S (2004) Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: FOCS, pp 136\u2013145","DOI":"10.1109\/FOCS.2004.59"},{"key":"812_CR17","doi-asserted-by":"crossref","unstructured":"Lahoti P, Garimella K, Gionis A (2018) Joint non-negative matrix factorization for learning ideological leaning on twitter. In: WSDM","DOI":"10.1145\/3159652.3159669"},{"key":"812_CR18","doi-asserted-by":"crossref","unstructured":"Meyerson A, Tagiku B (2009) Minimizing average shortest path distances via shortcut edge addition. In: APPROX, pp 272\u2013285","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"812_CR19","doi-asserted-by":"crossref","unstructured":"Papagelis M, Bonchi F, Gionis A (2011) Suggesting ghost edges for a smaller world. In: CIKM","DOI":"10.1145\/2063576.2063952"},{"key":"812_CR20","doi-asserted-by":"crossref","unstructured":"Parotsidis N, Pitoura N, Tsaparas P (2015) Selecting shortcuts for a smaller world. In: SDM","DOI":"10.1137\/1.9781611974010.4"},{"key":"812_CR21","doi-asserted-by":"crossref","unstructured":"Parotsidis N, Pitoura E, Tsaparas P (2016) Centrality-aware link recommendations. In: WSDM, pp 503\u2013512","DOI":"10.1145\/2835776.2835818"},{"key":"812_CR22","doi-asserted-by":"crossref","unstructured":"Perumal S, Basu P, Guan Z (2013) Minimizing eccentricity in composite networks via constrained edge additions. In: MILCOM, pp 1894\u20131899","DOI":"10.1109\/MILCOM.2013.319"},{"issue":"4","key":"812_CR23","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/BF02476440","volume":"15","author":"A Rapoport","year":"1953","unstructured":"Rapoport A (1953) Spread of information through a population with socio-structural bias. Bull Math Biophys 15(4):523\u2013533","journal-title":"Bull Math Biophys"},{"key":"812_CR24","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Inferring the strength of social ties: a community-driven approach. In: KDD, pp 1017\u20131025","DOI":"10.1145\/3097983.3098199"},{"key":"812_CR25","unstructured":"Simmel G (1908) Soziologie Untersuchungen uber die Formen der Vergesellschaftung"},{"key":"812_CR26","doi-asserted-by":"crossref","unstructured":"Sintos S, Tsaparas P (2014) Using strong triadic closure to characterize ties in social networks. In: KDD, pp 1466\u20131475. ACM","DOI":"10.1145\/2623330.2623664"},{"key":"812_CR27","doi-asserted-by":"crossref","unstructured":"Torro O, Pirkkalainen H (2017) Strengthening social ties via ICT in the organization. In: Proceedings of the 50th Hawaii international conference on system sciences, pp 5511\u20135520","DOI":"10.24251\/HICSS.2017.666"},{"key":"812_CR28","unstructured":"Ugander J, Karrer B, Backstrom B, Marlow C (2011) The anatomy of the facebook social graph. CoRR arXiv:1111.4503"},{"key":"812_CR29","doi-asserted-by":"crossref","unstructured":"Ye Y, Borodin A (2009) Elimination graphs. In: ICALP, pp 774\u2013785","DOI":"10.1007\/978-3-642-02927-1_64"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00812-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-021-00812-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00812-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T06:26:00Z","timestamp":1642832760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-021-00812-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["812"],"URL":"https:\/\/doi.org\/10.1007\/s10618-021-00812-1","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]},"assertion":[{"value":"20 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}