research-article

Public Access

RePBubLik: Reducing Polarized Bubble Radius with Link Insertions

Authors:

Shahrzad Haddadan,

Cristina Menghini,

Matteo Riondato,

Eli UpfalAuthors Info & Claims

WSDM '21: Proceedings of the 14th ACM International Conference on Web Search and Data Mining

Pages 139 - 147

https://doi.org/10.1145/3437963.3441825

Published: 08 March 2021 Publication History

Abstract

The topology of the hyperlink graph among pages expressing different opinions may influence the exposure of readers to diverse content. Structural bias may trap a reader in a 'polarized' bubble with no access to other opinions. We model readers' behavior as random walks. A node is in a 'polarized' bubble if the expected length of a random walk from it to a page of different opinion is large. The structural bias of a graph is the sum of the radii of highly-polarized bubbles. We study the problem of decreasing the structural bias through edge insertions. 'Healing' all nodes with high polarized bubble radius is hard to approximate within a logarithmic factor, so we focus on finding the best k edges to insert to maximally reduce the structural bias. We present RePBubLik, an algorithm that leverages a variant of the random walk closeness centrality to select the edges to insert. RePBubLik obtains, under mild conditions, a constant-factor approximation. It reduces the structural bias faster than existing edge-recommendation methods, including some designed to reduce the polarization of a graph.

References

[1]

Lada A. Adamic and Natalie Glance. 2005. The Political Blogosphere and the 2004 U.S. Election: Divided They Blog. In Proceedings of the 3rd International Workshop on Link Discovery (Chicago, Illinois) (LinkKDD '05). Association for Computing Machinery, New York, NY, USA, 36--43. https://doi.org/10.1145/1134271.1134277

[2]

Leman Akoglu. 2014. Quantifying political polarity based on bipartite opinion networks. In Eighth International AAAI Conference on Weblogs and Social Media.

[3]

Aris Anagnostopoulos, Luca Becchetti, Adriano Fazzone, Cristina Menghini, and Chris Schwiegelshohn. 2020. Principal Fairness: Removing Bias via Projections. arxiv: 1905.13651 [cs.DS]

[4]

Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski, Daniel Zügner, Stephan Günnemann, and Henning Meyerhenke. 2020. Group Centrality Maximization for Large-scale Graphs. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX).

[5]

Francesca Arrigo and Michele Benzi. 2016a. Edge modification criteria for enhancing the communicability of digraphs. SIAM J. Matrix Anal. Appl., Vol. 37, 1 (2016), 443--468.

Digital Library

[6]

Francesca Arrigo and Michele Benzi. 2016b. Updating and downdating techniques for optimizing network communicability. SIAM Journal on Scientific Computing, Vol. 38, 1 (2016), B25--B49.

[7]

Cigdem Aslay, Antonis Matakos, Esther Galbrun, and Aristides Gionis. 2018. Maximizing the Diversity of Exposure in a Social Network. In 2018 IEEE International Conference on Data Mining (ICDM). 863--868.

[8]

Eytan Bakshy, Solomon Messing, and Lada A Adamic. 2015. Exposure to ideologically diverse news and opinion on Facebook. Science, Vol. 348, 6239 (2015), 1130--1132.

[9]

Ruben Becker, Federico Corò, Gianlorenzo D'Angelo, and Hugo Gilbert. 2020. Balancing Spreads of Influence in a Social Network. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, 01 (2020), 3--10.

[10]

Anna Ben-Hamou, Roberto I. Oliveira, and Yuval Peres. 2018. Estimating Graph Parameters via Random Walks with Restarts. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana) (SODA '18). Society for Industrial and Applied Mathematics, USA, 1702--1714.

[11]

Seyla Benhabib. 1996. Toward a deliberative model of democratic legitimacy. In Democracy and difference: Contesting the boundaries of the political. Princeton University Press, Princeton, N.J., 67--94.

[12]

Suman K. Bera and C. Seshadhri. 2020. How to Count Triangles, without Seeing the Whole Graph. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (Virtual Event, CA, USA) (KDD '20). Association for Computing Machinery, New York, NY, USA, 306--316. https://doi.org/10.1145/3394486.3403073

[13]

Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo, Henning Meyerhenke, Lorenzo Severini, and Yllka Velaj. 2018. Improving the betweenness centrality of a node by adding links. Journal of Experimental Algorithmics (JEA), Vol. 23 (2018), 1--32.

Digital Library

[14]

Hau Chan, Leman Akoglu, and Hanghang Tong. 2014. Make it or break it: Manipulating robustness in large networks. In Proceedings of the 2014 SIAM International Conference on Data Mining. SIAM, 325--333.

[15]

Flavio Chierichetti and Shahrzad Haddadan. 2018. On the Complexity of Sampling Vertices Uniformly from a Graph. In 45th International Colloquium on Automata, Languages, and Programming (Prague, Czech Republic) (ICALP 2018).

[16]

Uthsav Chitra and Christopher Musco. 2020. Analyzing the Impact of Filter Bubbles on Social Network Polarization. In Proceedings of the 13th International Conference on Web Search and Data Mining. ACM.

Digital Library

[17]

Michael D Conover, Jacob Ratkiewicz, Matthew Francisco, Bruno Goncc alves, Filippo Menczer, and Alessandro Flammini. 2011. Political polarization on Twitter. In Fifth international AAAI conference on weblogs and social media.

[18]

Alessandro Cossard, Gianmarco De Francisci Morales, Kyriaki Kalimeri, Yelena Mejova, Daniela Paolotti, and Michele Starnini. 2020. Falling into the Echo Chamber: The Italian Vaccination Debate on Twitter. In Proceedings of the International AAAI Conference on Web and Social Media.

[19]

Gianlorenzo D'Angelo, Martin Olsen, and Lorenzo Severini. 2019. Coverage centrality maximization in undirected networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 501--508.

Digital Library

[20]

Abhimanyu Das, Sreenivas Gollapudi, and Kamesh Munagala. 2014. Modeling opinion dynamics in social networks. In Proceedings of the 7th ACM international conference on Web search and data mining. 403--412.

Digital Library

[21]

Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. 2014. On Estimating the Average Degree. In Proceedings of the 23rd International Conference on World Wide Web (Seoul, Korea) (WWW '14). Association for Computing Machinery, New York, NY, USA, 795--806. https://doi.org/10.1145/2566486.2568019

Digital Library

[22]

Erik D Demaine and Morteza Zadimoghaddam. 2010. Minimizing the diameter of a network using shortcut edges. In Scandinavian Workshop on Algorithm Theory. Springer, 420--431.

Digital Library

[23]

Ioana Dumitriu, Prasad Tetali, and Peter Winkler. 2003. On Playing Golf with Two Balls. SIAM J. Discrete Math., Vol. 16 (2003), 604--615.

Digital Library

[24]

Ronald Fagin, Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, and Andrew Tomkins. 2001. Random Walks with "Back Buttons". The Annals of Applied Probability, Vol. 11 (06 2001).

[25]

Seth Flaxman, Sharad Goel, and Justin M Rao. 2016. Filter bubbles, echo chambers, and online news consumption. Public opinion quarterly, Vol. 80, S1 (2016), 298--320.

[26]

Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2017a. Reducing Controversy by Connecting Opposing Views. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM '17).

Digital Library

[27]

Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018a. Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship. In Proceedings of the 2018 World Wide Web Conference. 913--922.

Digital Library

[28]

Kiran Garimella, Aristides Gionis, Nikos Parotsidis, and Nikolaj Tatti. 2017b. Balancing information exposure in social networks. In Advances in Neural Information Processing Systems. 4663--4671.

[29]

Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018b. Quantifying controversy on social media. ACM Transactions on Social Computing (2018).

[30]

Mouzhi Ge, Carla Delgado-Battenfeld, and Dietmar Jannach. 2010. Beyond Accuracy: Evaluating Recommender Systems by Coverage and Serendipity. In Proceedings of the Fourth ACM Conference on Recommender Systems (RecSys '10). 257--260.

Digital Library

[31]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 855--864.

Digital Library

[32]

Shahrzad Haddadan, Cristina Menghini, Matteo Riondato, and Eli Upfal. 2021. RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions. CoRR, Vol. abs/2101.04751 (2021). arxiv: 2101.04751 https://arxiv.org/abs/2101.04751

[33]

Daniel J. Isenberg. 1986. Group polarization: A critical review and meta-analysis. Journal of personality and social psychology, Vol. 50, 6 (1986), 1141.

[34]

Denis Kotkov, Jari Veijalainen, and Shuaiqiang Wang. 2016. Challenges of serendipity in recommender systems. In WEBIST 2016: Proceedings of the 12th International conference on web information systems and technologies.

[35]

Srijan Kumar, William L. Hamilton, Jure Leskovec, and Dan Jurafsky. 2018. Community interaction and conflict on the web. In Proceedings of the 2018 World Wide Web Conference. 933--943.

Digital Library

[36]

Rob LeFebvre. 2017. Obama Foundation taps social media to fight online echo chambers. (2017).

[37]

Jure Leskovec, Lada A Adamic, and Bernardo A Huberman. 2007. The dynamics of viral marketing. ACM Transactions on the Web (TWEB), Vol. 1, 1 (2007), 5--es.

Digital Library

[38]

Q Vera Liao and Wai-Tat Fu. 2014a. 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. 184--196.

[39]

Q. Vera Liao and Wai-Tat Fu. 2014b. Expert voices in echo chambers: effects of source expertise indicators on exposure to diverse opinions. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. 2745--2754.

Digital Library

[40]

Ahmad Mahmoody, Charalampos E Tsourakakis, and Eli Upfal. 2016. Scalable betweenness centrality maximization via sampling. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[41]

Antonis Matakos, Evimaria Terzi, and Panayiotis Tsaparas. 2017. Measuring and moderating opinion polarization in social networks. Data Mining and Knowledge Discovery, Vol. 31 (2017), 1480--1505.

Digital Library

[42]

Antonis Matakos, Sijing Tu, and Aristides Gionis. 2020. Tell me something my friends do not know: diversity maximization in social networks. Knowledge and Information Systems 9 (2020), 3697--3726.

Digital Library

[43]

Sourav Medya, Arlei Silva, Ambuj Singh, Prithwish Basu, and Ananthram Swami. 2018. Group centrality maximization via network design. In Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, 126--134.

[44]

C. Menghini, A. Anagnostopoulos, and E. Upfal. 2019. Wikipedia Polarization and Its Effects on Navigation Paths. In 2019 IEEE International Conference on Big Data (Big Data). 6154--6156.

[45]

Cristina Menghini, Aris Anagnostopoulos, and Eli Upfal. 2020. Wikipedia's Network Bias on Controversial Topics. https://arxiv.org/abs/2007.08197

[46]

Alfredo Jose Morales, Javier Borondo, Juan Carlos Losada, and Rosa M. Benito. 2015. Measuring political polarization: Twitter shows the two sides of Venezuela. Chaos: An Interdisciplinary Journal of Nonlinear Science, Vol. 25, 3 (2015), 033114.

[47]

Elchanan Mossel and Omer Tamuz. 2017. Opinion exchange dynamics. Probability Surveys, Vol. 14 (2017), 155--204.

[48]

Sean A Munson, Stephanie Y. Lee, and Paul Resnick. 2013. Encouraging reading of diverse political viewpoints with a browser widget. In Seventh International AAAI Conference on Weblogs and Social Media.

[49]

Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. 2018. Minimizing Polarization and Disagreement in Social Networks. In Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18.

[50]

Matti Nelimarkka, Salla-Maaria Laaksonen, and Bryan Semaan. 2018. Social media is polarized, social media is polarized: towards a new design agenda for mitigating polarization. In Proceedings of the 2018 Designing Interactive Systems Conference. 957--970.

Digital Library

[51]

Manos Papagelis, Francesco Bonchi, and Aristides Gionis. 2011. Suggesting ghost edges for a smaller world. In Proceedings of the 20th ACM international conference on Information and knowledge management. 2305--2308.

Digital Library

[52]

Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2015. Selecting shortcuts for a smaller world. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 28--36.

[53]

Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2016. Centrality-aware link recommendations. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. 503--512.

Digital Library

[54]

Senni Perumal, Prithwish Basu, and Ziyu Guan. 2013. Minimizing eccentricity in composite networks via constrained edge additions. In MILCOM 2013--2013 IEEE Military Communications Conference. 1894--1899.

[55]

Bashir Rastegarpanah, Krishna P. Gummadi, and Mark Crovella. 2019. Fighting Fire with Fire: Using Antidote Data to Improve Polarization and Fairness of Recommender Systems. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (WSDM '19).

Digital Library

[56]

Manoel Horta Ribeiro, Raphael Ottoni, Robert West, Virg'ilio A. F. Almeida, and Wagner Meira. 2020. Auditing Radicalization Pathways on YouTube. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency (FAT* '20). 131--141.

Digital Library

[57]

Ana-Andreea Stoica and Augustin Chaintreau. 2019. Hegemony in Social Media and the effect of recommendations. In Companion Proceedings of The 2019 World Wide Web Conference.

Digital Library

[58]

Ana-Andreea Stoica, Jessy Xinyi Han, and Augustin Chaintreau. 2020. Seeding Network Influence in Biased Networks and the Benefits of Diversity. In Proceedings of The Web Conference 2020. ACM.

Digital Library

[59]

Ana-Andreea Stoica, Christopher Riederer, and Augustin Chaintreau. 2018. Algorithmic Glass Ceiling in Social Networks. In Proceedings of the 2018 World Wide Web Conference. ACM Press.

Digital Library

[60]

Cass R. Sunstein. 2002. The Law of Group Polarization. Journal of Political Philosophy, Vol. 10, 2 (2002), 175--195.

[61]

Hanghang Tong, B Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012. Gelling, and melting, large graphs by edge manipulation. In Proceedings of the 21st ACM international conference on Information and knowledge management. 245--254.

Digital Library

[62]

Tomasz Wka s, Marcin Waniek, Talal Rahwan, and Tomasz Michalak. 2020. The Manipulability of Centrality Measures-An Axiomatic Approach. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 1467--1475.

[63]

Scott White and Padhraic Smyth. 2003. Algorithms for Estimating Relative Importance in Networks. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '03). 266--275.

Digital Library

[64]

An Zeng, Linyuan Lü, and Tao Zhou. 2012. Manipulating directed networks for better synchronization. New Journal of Physics, Vol. 14, 8 (2012), 083006.

Cited By

Zhu LZhang Z(2025)Opinion Maximization in Social Networks via Link RecommendationTheoretical Computer Science10.1016/j.tcs.2025.115090(115090)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115090
Haddadan SXin CGao JSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Optimally improving cooperative learning in a social settingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692752(17148-17188)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692752
Chen XSong YTang JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Link Recommendation to Augment Influence Diffusion with Provable GuaranteesProceedings of the ACM Web Conference 202410.1145/3589334.3645521(2509-2518)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645521
Show More Cited By

Index Terms

RePBubLik: Reducing Polarized Bubble Radius with Link Insertions
1. Information systems
  1. World Wide Web
    1. Web searching and information discovery
      1. Social recommendation
2. Theory of computation

Recommendations

Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights
Abstract
The sets of hyperlinks in web pages, relationship ties in social networks, or sets of recommendations in recommender systems, have a major impact on the diversity of content accessed by the user in a browsing session. Bias induced by the graph ...
Polarized modes dispersion in anisotropic optical fiber communication lines

Equations are derived for calculation of the propagation constants and of the dispersion of the fundamental modes in anisotropic waveguides. This work shows how to obtain approximate analytic expressions which can be used to calculate with sufficient ...
Circularly Polarized Antennas

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '21: Proceedings of the 14th ACM International Conference on Web Search and Data Mining

March 2021

1192 pages

ISBN:9781450382977

DOI:10.1145/3437963

General Chairs:
Liane Lewin-Eytan
Amazon, Israel
,
David Carmel
Amazon, Israel
,
Elad Yom-Tov
Microsoft, Israel
,
Program Chairs:
Eugene Agichtein
Emory University and Amazon, USA
,
Evgeniy Gabrilovich
Google Health, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 March 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Conference

WSDM '21

Sponsor:

WSDM '21: The Fourteenth ACM International Conference on Web Search and Data Mining

March 8 - 12, 2021

Virtual Event, Israel

Acceptance Rates

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
733
Total Downloads

Downloads (Last 12 months)193
Downloads (Last 6 weeks)27

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhu LZhang Z(2025)Opinion Maximization in Social Networks via Link RecommendationTheoretical Computer Science10.1016/j.tcs.2025.115090(115090)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115090
Haddadan SXin CGao JSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Optimally improving cooperative learning in a social settingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692752(17148-17188)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692752
Chen XSong YTang JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Link Recommendation to Augment Influence Diffusion with Provable GuaranteesProceedings of the ACM Web Conference 202410.1145/3589334.3645521(2509-2518)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645521
Mashayekhi YKang BLijffijt JDe Bie T(2024)GREASE: Graph Imbalance Reduction by Adding Sets of EdgesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.330447836:4(1611-1623)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3304478
Zhu LZhou XTian JLi WZhang Z(2024)Defending Against Malicious Influence Control in Online Leader-Follower Social NetworksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338324419(4809-4819)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3383244
Fabbri FWang YBonchi FCastillo CMathioudakis MElkind E(2023)Rewiring what-to-watch-next recommendations to reduce radicalization pathways (extended abstract)Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/715(6431-6435)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/715
Zareie ASakellariou R(2023)Maximizing the Diversity of Exposure in Online Social Networks by Identifying Users with Increased Susceptibility to PersuasionACM Transactions on Knowledge Discovery from Data10.1145/362582618:2(1-21)Online publication date: 14-Nov-2023
https://dl.acm.org/doi/10.1145/3625826
Adriaens FWang HGionis ASingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Minimizing Hitting Time between Disparate Groups with Shortcut EdgesProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599434(1-10)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599434
Bhalla NLechowicz AMusco CChua TLauw HSi LTerzi ETsaparas P(2023)Local Edge Dynamics and Opinion PolarizationProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining10.1145/3539597.3570442(6-14)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1145/3539597.3570442
Hohmann MDevriendt KCoscia M(2023)Quantifying ideological polarization on a network using generalized Euclidean distanceScience Advances10.1126/sciadv.abq20449:9Online publication date: 3-Mar-2023
https://doi.org/10.1126/sciadv.abq2044
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten