RePBubLik: Reducing Polarized Bubble Radius with Link Insertions

The topology of the hyperlink graph connecting pages representing different opinions may influence the exposure of readers to diverse content. A structural bias in the hyperlink graph may trap a reader in a “polarized” bubble of nodes with no access to other opinions. We model and study this problem through a generalized random walk model of web surfers. We say that a node is in a “polarized” bubble if the expected length of a random walk from that node to a page of different opinion is large. We define the structural bias of a graph as the sum of the radius of highly polarized bubbles. We study the problem of decreasing the structural bias through edge insertions. We show that the problem of “healing” all nodes with high polarized bubble radius is hard to even approximate within a constant factor, and we pose the problem of finding the best k edges to insert to maximize the reduction in the structural bias. We present RePBubLik that leverages a task-specific variant of the random walk closeness centrality to select the edges to insert. We prove RePBubLik is constant-factor approximation under mild conditions. Our experimental evaluation of RePBubLik shows that it is capable of reducing the structural bias faster than existing edge-recommendation methods, including some designed to reduce the polarization of a graph