Reducing Polarization and Increasing Diverse Navigability in Graphs
19A Google TechTalk, presented by Shahrzad Haddadan, 2021/11/11
ABSTRACT: An Algorithms Seminar. Full Title: "Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weights"
The sets of hyperlinks in web pages, relationship ties in social net-works, or sets of recommendations in recommender systems, have a major impact on the diversity of content accessed by the user in a browsing session. Structural bias may trap a reader in a polarized bubble with no access to other opinions. It is widely accepted that exposure to diverse opinions creates more informed citizens and consumers. A node has a large polarized bubble radius if the expected length of a random walk from it to a node of different opinion is large. Using the bubble radius, this paper introduces the measures of structural bias and diverse navigability to quantify the effect of links and recommendations on the diversity of content visited in a browsing session. We then propose algorithmic techniques to reduce the structural bias of the graph or improve the diverse navigability of the system through minimal modifications, such as edge insertions or flipping the order of existing links or recommendations,corresponding to switching the edge traversal probabilities. Under mild conditions, our techniques obtain a constant factor-approximation of their respective tasks. In our extensive experimental evaluation, we show that our algorithms.
Authors: Shahrzad Haddadan, Cristina Menghini, Matteo Riondato, Eli Upfal.
Part of this work appeared in WSDM 2021 and was a runner up for best paper award.
Bio: Shahrzad Haddadan is currently a postdoctoral researcher at Brown university working under supervision of Prof. Eli Upfal. Shahrzad's expertise is to employ combinatorial structures and statistical tools to model massive data problems. Her area of research includes study of social issues in online networks, analyses of algorithms using MCMC and study of primary problems in graph mining in different computational models. She received her PhD from Dartmouth College where she was working under supervision of Prof. Peter Winkler.