Optimizing Information Access in Networks via Edge Augmentation

Given a graph G = (V, E) and a model of information flow on that network, a fundamental question is to understand if all the nodes have sufficient access to information generated at other nodes in the graph. If not, we can ask if a small set of edge additions improve information access. Formally, the broadcast value of a network is defined to be the minimum over pairs u, v V of the probability that an information cascade starting at u reaches v. Recent work in the algorithmic fairness literature has focused on heuristics for adding a few edges to a graph to improve its broadcast. Our goal is to formally study the approximability of the Broadcast Improvement problem: given G and a parameter k, find the best set of k edges to add to G in order to maximize the broadcast value of the resulting graph. We develop efficient bicriteria approximation algorithms. If the optimal solution adds k edges and achieves a broadcast of ^*, we develop algorithms that can (a) add 2k-1 edges and achieve a broadcast value roughly (^*) ⁴, or (b) add O (k n) edges and achieve a broadcast roughly ^*. We also provide other trade-offs, that can be better depending on k and the parameter associated with propagation in the cascade model. We complement our results by proving that unless P = NP, any algorithm that adds O (k) edges must lose significantly in the approximation of ^*, resolving an open question. Our techniques are inspired by connections between Broadcast Improvement and problems such as Metric k-Center and Diameter Reduction. However, since the objective involves information cascades, we need to develop novel probabilistic tools to reason about the existence of paths in edge-sampled graphs. Finally, we show that our techniques extend to a single-source variant, for which we show both bicriteria algorithms and inapproximability results.