{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:24:50Z","timestamp":1724372690842},"reference-count":32,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2024,8,21]],"date-time":"2024-08-21T00:00:00Z","timestamp":1724198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"MICINN","award":["PID2022-139835NB-C22"]},{"name":"consolidated research group","award":["SGR 01615"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"The bipartite polarization problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labeled graph that represents a debate developed through some social network, where nodes represent user\u2019s opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work, approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we further investigate the complexity of this problem by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition. In view of the experimental results, it is computationally feasible to implement transparent mechanisms to monitor polarization on online discussions and to inform about solutions for creating healthier social media environments.<\/jats:p>","DOI":"10.3390\/a17080369","type":"journal-article","created":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T10:28:51Z","timestamp":1724322531000},"page":"369","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of the Bipartite Polarization Problem: From Neutral to Highly Polarized Discussions"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-4594-5502","authenticated-orcid":false,"given":"Teresa","family":"Alsinet","sequence":"first","affiliation":[{"name":"Department of Computer Engineering and Digital Design, University of Lleida, Jaume II, 69, 25001 Lleida, Spain"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4089-6422","authenticated-orcid":false,"given":"Josep","family":"Argelich","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Digital Design, University of Lleida, Jaume II, 69, 25001 Lleida, Spain"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5208-685X","authenticated-orcid":false,"given":"Ram\u00f3n","family":"B\u00e9jar","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Digital Design, University of Lleida, Jaume II, 69, 25001 Lleida, Spain"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-1031-6522","authenticated-orcid":false,"given":"Santi","family":"Mart\u00ednez","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Digital Design, University of Lleida, Jaume II, 69, 25001 Lleida, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2024,8,21]]},"reference":[{"key":"ref_1","unstructured":"Neudert, L.M., and Marchal, N. (2019). Polarisation and the Use of Technology in Political Campaigns and Communication, European Parliamentary Research Service. Technical Report."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Valentini, D., Lorusso, A.M., and Stephan, A. (2020). Onlife Extremism: Dynamic Integration of Digital and Physical Spaces in Radicalization. Front. Psychol., 11.","DOI":"10.3389\/fpsyg.2020.00524"},{"key":"ref_3","first-page":"51","article-title":"Polarizaci\u00f3n y tecnolog\u00edas de la informaci\u00f3n: Radicales vs. extremistas","volume":"34","author":"Almagro","year":"2021","journal-title":"Trevista Int. \u00e9Ticas Apl."},{"key":"ref_4","unstructured":"Cf, O. (2015). Transforming Our World: The 2030 Agenda for Sustainable Development."},{"key":"ref_5","first-page":"74","article-title":"A systematic review of worldwide causal and correlational evidence on digital media and democracy","volume":"7","author":"Oswald","year":"2023","journal-title":"Nat. Hum. Behav."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Barber\u00e0, P. (2020). Social Media, Echo Chambers, and Political Polarization. Social Media and Democracy: The State of the Field, Prospects for Reform, Cambridge University Press. SSRC Anxieties of Democracy.","DOI":"10.1017\/9781108890960.004"},{"key":"ref_7","first-page":"557","article-title":"Cross-Country Trends in Affective Polarization","volume":"106","author":"Boxell","year":"2020","journal-title":"Natl. Bur. Econ. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"120924","DOI":"10.1016\/j.techfore.2021.120924","article-title":"The impact of group polarization on the quality of online debate in social media: A systematic literature review","volume":"170","author":"Iandoli","year":"2021","journal-title":"Technol. Forecast. Soc. Chang."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3316809","article-title":"Polarization and fake news: Early warning of potential misinformation targets","volume":"13","author":"Vicario","year":"2019","journal-title":"ACM Trans. Web (TWEB)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1038\/d41586-018-07034-4","article-title":"The biggest pandemic risk? Viral misinformation","volume":"562","author":"Larson","year":"2018","journal-title":"Nature"},{"key":"ref_11","unstructured":"European Commission, Directorate-General for Communications Networks, Content and Technology (2024, August 12). Tackling online disinformation: A European approach, Communication from the Commission to the European Parliament, the Council, the European Economic and Social Committee and the Committee of the Regions, Available online: https:\/\/eur-lex.europa.eu\/legal-content\/EN\/TXT\/PDF\/?uri=CELEX:52018DC0236."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1080\/10584609.2020.1785067","article-title":"Political Polarization on the Digital Sphere: A Cross-platform, Over-time Analysis of Interactional, Positional, and Affective Polarization on Social Media","volume":"38","author":"Yarchi","year":"2021","journal-title":"Political Commun."},{"key":"ref_13","first-page":"188","article-title":"The role of (social) media in political polarization: A systematic review","volume":"45","author":"Kubin","year":"2021","journal-title":"Ann. Int. Commun. Assoc."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bessi, A., Zollo, F., Vicario, M.D., Puliga, M., Scala, A., Caldarelli, G., Uzzi, B., and Quattrociocchi, W. (2016). Users Polarization on Facebook and Youtube. PLoS ONE, 11.","DOI":"10.1371\/journal.pone.0159641"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Vicario, M.D., Vivaldo, G., Bessi, A., Zollo, F., Scala, A., Caldarelli, G., and Quattrociocchi, W. (2016). Echo chambers: Emotional contagion and group polarization on Facebook. Sci. Rep., 6.","DOI":"10.1038\/srep37825"},{"key":"ref_16","unstructured":"Choudhury, M.D., Chunara, R., Culotta, A., and Welles, B.F. (2020, January 8\u201311). Hyperpartisanship, Disinformation and Political Conversations on Twitter: The Brazilian Presidential Election of 2018. Proceedings of the Fourteenth International AAAI Conference on Web and Social Media, ICWSM 2020, Held Virtually, Original Venue, Atlanta, GA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Morales, G.D.F., Monti, C., and Starnini, M. (2021). No echo in the chambers of political interactions on Reddit. Sci. Rep., 11.","DOI":"10.1038\/s41598-021-81531-x"},{"key":"ref_18","first-page":"7313","article-title":"Emotion shapes the diffusion of moralized content in social networks","volume":"114","author":"Brady","year":"2017","journal-title":"Psychol. Cogn. Sci."},{"key":"ref_19","first-page":"e2024292118","article-title":"Out-group animosity drives engagement on social media","volume":"118","author":"Rathje","year":"2021","journal-title":"Psychol. Cogn. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1093\/poq\/nfz042","article-title":"Thinking fast and furious: Emotional intensity and opinion polarization in online media","volume":"83","author":"Asker","year":"2019","journal-title":"Public Opin. Q."},{"key":"ref_21","unstructured":"Rosen, G. (2020, May 27). Facebook: Investments to Fight Polarization. Available online: https:\/\/about.fb.com\/news\/2020\/05\/investments-to-fight-polarization\/."},{"key":"ref_22","first-page":"263","article-title":"On the Impact of Social Media Recommendations on Opinion Consensus","volume":"Volume 13196","author":"Bandini","year":"2021","journal-title":"Proceedings of the AIxIA 2021\u2014Advances in Artificial Intelligence\u201420th International Conference of the Italian Association for Artificial Intelligence"},{"key":"ref_23","unstructured":"Candogan, O., Immorlica, N., and Anunrojwong, B.L.J. (2022). Social Learning under Platform Influence: Consensus and Persistent Disagreement. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Alsinet, T., Argelich, J., B\u00e9jar, R., and Mart\u00ednez, S. (2021). Measuring Polarization in Online Debates. Appl. Sci., 11.","DOI":"10.3390\/app112411879"},{"key":"ref_25","first-page":"17","article-title":"Approximate and Optimal Solutions for the Bipartite Polarization Problem","volume":"Volume 356","author":"Grimaldo","year":"2022","journal-title":"Proceedings of the Artificial Intelligence Research and Development\u2014Proceedings of the 24th International Conference of the Catalan Association for Artificial Intelligence, CCIA 2022"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1111\/1467-9760.00148","article-title":"The Law of Group Polarization","volume":"10","author":"Sunstein","year":"2002","journal-title":"J. Political Philos."},{"key":"ref_27","unstructured":"Huang, C., and Jurafsky, D. (2010, January 23\u201327). Support or Oppose? Classifying Positions in Online Debates from Reply Activities and Opinion Expressions. Proceedings of the COLING 2010, 23rd International Conference on Computational Linguistics, Posters Volume, Beijing, China."},{"key":"ref_28","unstructured":"Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., and Aho, A.V. (1978, January 1\u20133). Node- and Edge-Deletion NP-Complete Problems. Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1080\/10556788.2017.1335312","article-title":"SCIP: Global optimization of mixed-integer nonlinear programs in a branch-and-cut framework","volume":"33","author":"Vigerske","year":"2018","journal-title":"Optim. Methods Softw."},{"key":"ref_30","unstructured":"Bestuzheva, K., Besan\u00e7on, M., Chen, W.K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., and Gleixner, A. (2021). The SCIP Optimization Suite 8.0. Technical Report 21\u201341, ZIB, Takustr. 7, 14195 Berlin, 2021. arXiv."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1162","DOI":"10.1016\/j.engappai.2012.09.001","article-title":"Breakout Local Search for the Max-Cutproblem","volume":"26","author":"Benlic","year":"2013","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_32","unstructured":"Kiciman, E., Ellison, N.B., Hogan, B., Resnick, P., and Soboroff, I. (2013, January 8\u201311). A Measure of Polarization on Social Media Networks Based on Community Boundaries. Proceedings of the Seventh International Conference on Weblogs and Social Media, ICWSM 2013, Cambridge, MA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/369\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T11:57:06Z","timestamp":1724327826000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,21]]},"references-count":32,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2024,8]]}},"alternative-id":["a17080369"],"URL":"http:\/\/dx.doi.org\/10.3390\/a17080369","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,21]]}}}
