{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:57:05Z","timestamp":1777615025271,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T00:00:00Z","timestamp":1587600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T00:00:00Z","timestamp":1587600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["286211"],"award-info":[{"award-number":["286211"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["313927"],"award-info":[{"award-number":["313927"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["317085"],"award-info":[{"award-number":["317085"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Social media have a great potential to improve information dissemination in our society, yet they have been held accountable for a number of undesirable effects, such as polarization and filter bubbles. It is thus important to understand these negative phenomena and develop methods to combat them. In this paper, we propose a novel approach to address the problem of breaking filter bubbles in social media. We do so by aiming to maximize the diversity of the information exposed to connected social-media users. We formulate the problem of maximizing the diversity of exposure as a quadratic-knapsack problem. We show that the proposed diversity-maximization problem is inapproximable, and thus, we resort to polynomial nonapproximable algorithms, inspired by solutions developed for the quadratic-knapsack problem, as well as scalable greedy heuristics. We complement our algorithms with instance-specific upper bounds, which are used to provide empirical approximation guarantees for the given problem instances. Our experimental evaluation shows that a proposed greedy algorithm followed by randomized local search is the algorithm of choice given its quality-vs.-efficiency trade-off.<\/jats:p>","DOI":"10.1007\/s10115-020-01456-1","type":"journal-article","created":{"date-parts":[[2020,4,23]],"date-time":"2020-04-23T11:03:41Z","timestamp":1587639821000},"page":"3697-3726","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Tell me something my friends do not know: diversity maximization in social networks"],"prefix":"10.1007","volume":"62","author":[{"given":"Antonis","family":"Matakos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sijing","family":"Tu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,23]]},"reference":[{"key":"1456_CR1","doi-asserted-by":"crossref","unstructured":"Adamic LA, Glance N (2005) The political blogosphere and the 2004 U.S. election: divided they blog. In: International Workshop on Link Discovery, LinkKDD","DOI":"10.1145\/1134271.1134277"},{"key":"1456_CR2","doi-asserted-by":"crossref","unstructured":"Akoglu L (2014) Quantifying political polarity based on bipartite opinion networks. In: ICWSM","DOI":"10.1609\/icwsm.v8i1.14524"},{"issue":"1","key":"1456_CR3","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1093\/pan\/mpu011","volume":"23","author":"P Barber\u00e1","year":"2014","unstructured":"Barber\u00e1 P (2014) Birds of the same feather tweet together: Bayesian ideal point estimation using twitter data. Polit Anal 23(1):76\u201391","journal-title":"Polit Anal"},{"key":"1456_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/0471787779","volume-title":"Nonlinear programming: theory and algorithms","author":"MS Bazaraa","year":"2006","unstructured":"Bazaraa MS, Sherali HD, Shetty CM (2006) Nonlinear programming: theory and algorithms. Wiley, Hoboken OCLC: ocm61478842"},{"key":"1456_CR5","doi-asserted-by":"crossref","unstructured":"Bessi A, Zollo F, Vicario MD, Puliga M, Scala A, Caldarelli G, Uzzi B, Quattrociocchi W (2016) Users Polarization on Facebook and Youtube. PLoS ONE 11(8):e0159641","DOI":"10.1371\/journal.pone.0159641"},{"key":"1456_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd SP, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge"},{"key":"1456_CR7","unstructured":"Conover M, Ratkiewicz J, Francisco MR, Gon\u00e7alves B, Menczer F, Flammini A (2011) Political polarization on Twitter. In: ICWSM"},{"issue":"15","key":"1456_CR8","doi-asserted-by":"publisher","first-page":"5791","DOI":"10.1073\/pnas.1217220110","volume":"110","author":"P Dandekar","year":"2013","unstructured":"Dandekar P, Goel A, Lee DT (2013) Biased assimilation, homophily, and the dynamics of polarization. PNAS 110(15):5791\u20135796","journal-title":"PNAS"},{"key":"1456_CR9","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/050645506","volume":"49","author":"A d\u2019Aspremont","year":"2007","unstructured":"d\u2019Aspremont A, Ghaoui LE, Jordan MI, Lanckriet GR (2007) A direct formulation for sparse PCA using semidefinite programming. SIAM Rev 49:434\u2013448","journal-title":"SIAM Rev"},{"key":"1456_CR10","doi-asserted-by":"crossref","unstructured":"Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. In: Padberg MW (ed) Combinatorial optimization. Springer, pp 132\u2013149","DOI":"10.1007\/BFb0120892"},{"key":"1456_CR11","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. WH Freeman and Co, New York"},{"key":"1456_CR12","unstructured":"Garimella K, Gionis A, Parotsidis N, Tatti N (2017) Balancing information exposure in social networks. In: NIPS"},{"key":"1456_CR13","doi-asserted-by":"crossref","unstructured":"Garimella K, Morales GDF, Gionis A, Mathioudakis M (2016) Quantifying controversy in social media. In: WSDM","DOI":"10.1145\/2835776.2835792"},{"key":"1456_CR14","doi-asserted-by":"crossref","unstructured":"Garimella VRK, Morales GDF, Gionis A, Mathioudakis M (2017) Reducing controversy by connecting opposing views. In: WSDM","DOI":"10.1145\/3018661.3018703"},{"issue":"2","key":"1456_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1111\/j.1083-6101.2009.01440.x","volume":"14","author":"RK Garrett","year":"2009","unstructured":"Garrett RK (2009) Echo chambers online? Politically motivated selective exposure among internet news users1. J Comput-Mediat Commun 14(2):265\u2013285","journal-title":"J Comput-Mediat Commun"},{"issue":"4","key":"1456_CR16","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/mnsc.22.4.455","volume":"22","author":"F Glover","year":"1975","unstructured":"Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Manag Sci 22(4):455\u2013460","journal-title":"Manag Sci"},{"issue":"6","key":"1456_CR17","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115\u20131145","journal-title":"J ACM"},{"key":"1456_CR18","volume-title":"News use across social media platforms 2016","author":"J Gottfried","year":"2016","unstructured":"Gottfried J, Shearer E (2016) News use across social media platforms 2016. Pew Research Center, Washington"},{"key":"1456_CR19","unstructured":"Guerra PHC, W M Jr, Cardie C, Kleinberg R (2013) A measure of polarization on social media networks based on community boundaries. In: WSDM"},{"key":"1456_CR20","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1009898604624","volume":"4","author":"C Helmberg","year":"1996","unstructured":"Helmberg C, Rendl F, Weismantel R (1996) A semidefinite programming approach to the quadratic knapsack problem. J Comb Optim 4:197\u2013215","journal-title":"J Comb Optim"},{"key":"1456_CR21","doi-asserted-by":"crossref","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Introduction to np-completeness of knapsack problems. In: Knapsack problems. Springer, pp 483\u2013493","DOI":"10.1007\/978-3-540-24777-7_16"},{"key":"1456_CR22","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":"1456_CR23","unstructured":"Liao QV, Fu W-T (2014) Can you hear me now? Mitigating the echo chamber effect by source position indicators. In: Proceedings of the 17th ACM conference on computer supported cooperative work & social computing, CSCW \u201914. ACM, New York, NY, USA, pp 184\u2013196"},{"issue":"1","key":"1456_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lovasz","year":"2006","unstructured":"Lovasz L (2006) On the Shannon capacity of a graph. IEEE Trans Inf Theory 25(1):1\u20137","journal-title":"IEEE Trans Inf Theory"},{"issue":"3","key":"1456_CR25","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1109\/MSP.2010.936019","volume":"27","author":"Z-Q Luo","year":"2010","unstructured":"Luo Z-Q, Ma W-K, So AM-C, Ye Y, Zhang S (2010) Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process Mag 27(3):20\u201334","journal-title":"IEEE Signal Process Mag"},{"key":"1456_CR26","doi-asserted-by":"crossref","unstructured":"Matakos A, Gionis A (2018) Tell me something my friends do not know: Diversity maximization in social networks. In: ICDM","DOI":"10.1109\/ICDM.2018.00048"},{"issue":"5","key":"1456_CR27","first-page":"1480","volume":"31","author":"A Matakos","year":"2017","unstructured":"Matakos A, Terzi E, Tsaparas P (2017) Measuring and moderating opinion polarization in social networks. DMKD 31(5):1480\u20131505","journal-title":"DMKD"},{"key":"1456_CR28","doi-asserted-by":"crossref","unstructured":"Munson SA, Resnick P (2010) Presenting diverse political opinions: how and how much. In: CHI","DOI":"10.1145\/1753326.1753543"},{"key":"1456_CR29","doi-asserted-by":"crossref","unstructured":"Musco C, Musco C, Tsourakakis CE (2017) Minimizing polarization and disagreement in social networks. ArXiv e-prints","DOI":"10.1145\/3178876.3186103"},{"issue":"1","key":"1456_CR30","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg M (1989) The boolean quadric polytope: some characteristics, facets and relatives. Math Program 45(1):139\u2013172","journal-title":"Math Program"},{"key":"1456_CR31","volume-title":"The filter bubble: what the internet is hiding from you","author":"E Pariser","year":"2011","unstructured":"Pariser E (2011) The filter bubble: what the internet is hiding from you. Penguin Press, New York"},{"issue":"5","key":"1456_CR32","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.dam.2006.08.007","volume":"155","author":"D Pisinger","year":"2007","unstructured":"Pisinger D (2007) The quadratic knapsack problem\u2014a survey. Discrete Appl Math 155(5):623\u2013648","journal-title":"Discrete Appl Math"},{"key":"1456_CR33","unstructured":"Vicario MD, Scala A, Caldarelli G, Stanley HE, Quattrociocchi W (2016) Modeling confirmation bias and polarization. CoRR. arXiv:1607.00022"},{"key":"1456_CR34","first-page":"1655","volume":"66","author":"V Vydiswaran","year":"2015","unstructured":"Vydiswaran V, Zhai C, Roth D, Pirolli P (2015) Overcoming bias to learn about controversial topics. JASIST 66:1655\u20131672","journal-title":"JASIST"},{"issue":"2","key":"1456_CR35","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10107980012a","volume":"84","author":"Y Ye","year":"1999","unstructured":"Ye Y (1999) Approximating quadratic programming with bound and quadratic constraints. Math Program 84(2):219\u2013226","journal-title":"Math Program"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01456-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-020-01456-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-020-01456-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T07:39:27Z","timestamp":1696059567000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-020-01456-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,23]]},"references-count":35,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1456"],"URL":"https:\/\/doi.org\/10.1007\/s10115-020-01456-1","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,23]]},"assertion":[{"value":"7 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}