RePBubLik: Reducing Polarized Bubble Radius with Link Insertions
RePBubLik: Reducing Polarized Bubble Radius with Link Insertions
复制标题
DOI：
10.1145/3437963.3441825
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Shahrzad Haddadan;Cristina Menghini;Matteo Riondato;E. Upfal
中科院分区：
文献类型：
--
作者：
Shahrzad Haddadan;Cristina Menghini;Matteo Riondato;E. Upfal
表达不同观点的页面之间的超链接图的拓扑结构可能会影响读者对不同内容的曝光。结构性偏见可能会使读者陷入“两极分化”的泡沫中，无法获得其他观点。我们将读者的行为建模为随机漫步。如果从一个节点到另一个观点不同的页面的随机游走的预期长度很大，那么这个节点就处于“极化”泡中。图的结构偏差是高度极化气泡半径的总和。我们研究了通过边插入来减小结构偏差的问题。“修复”具有高极化气泡半径的所有节点很难在对数因子内近似，因此我们专注于找到最佳的k条边来插入，以最大限度地减少结构偏差。我们提出了RePBubLik算法，该算法利用随机游走接近中心性的一种变体来选择要插入的边。RePBubLik在温和的条件下得到一个常因子近似。它比现有的边缘推荐方法更快地减少了结构偏差，包括一些旨在减少图的极化的方法。
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.