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.

RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions / Haddadan, Shahrzad; Menghini, Cristina; Riondato, Matteo; Upfal, Eli. - (2021), pp. 139-147. (Intervento presentato al convegno Fourteenth ACM International Conference on Web Search and Data Mining (WSDM '21) tenutosi a Virtual Event, Israel) [10.1145/3437963.3441825].

RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions

Cristina Menghini
;
2021

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.
2021
Fourteenth ACM International Conference on Web Search and Data Mining (WSDM '21)
Bias; Fairness; Polarization
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
RePBubLik: Reducing the Polarized Bubble Radius with Link Insertions / Haddadan, Shahrzad; Menghini, Cristina; Riondato, Matteo; Upfal, Eli. - (2021), pp. 139-147. (Intervento presentato al convegno Fourteenth ACM International Conference on Web Search and Data Mining (WSDM '21) tenutosi a Virtual Event, Israel) [10.1145/3437963.3441825].
File allegati a questo prodotto
File Dimensione Formato  
Haddadan_postprint_RePBubLik_2021.pdf.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Creative commons
Dimensione 899.95 kB
Formato Adobe PDF
899.95 kB Adobe PDF
Haddadan_RePBubLik_2021.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.47 MB
Formato Adobe PDF
1.47 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1487853
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 11
social impact