Fast algorithms to improve fair information access in networks

We consider the problem of selecting k seed nodes in a network to maximize the minimum probability of activation under an independent cascade beginning at these seeds. The motivation is to promote fairness by ensuring that even the least advantaged members of the network have good access to information. Our problem can be viewed as a variant of the classic influence maximization objective, but it appears somewhat more difficult to solve: only heuristics are known. Moreover, the scalability of these methods is sharply constrained by the need to repeatedly estimate access probabilities. We design and evaluate a suite of 10 new scalable algorithms which crucially do not require probability estimation. To facilitate comparison with the state-of-the-art, we make three more contributions which may be of broader interest. We introduce a principled method of selecting a pairwise information transmission parameter used in experimental evaluations, as well as a new performance metric which allows for comparison of algorithms across a range of values for the parameter k. Finally, we provide a new benchmark corpus of 174 networks drawn from 6 domains. Our algorithms retain most of the performance of the state-of-the-art while reducing running time by orders of magnitude. Specifically, a meta-learner approach is on average only 20% less effective than the state-of-the-art on held-out data, but about 75-130 times faster. Further, the meta-learner’s performance exceeds the state-of-the-art on about 20% of networks, and the magnitude of its running time advantage is maintained on much larger networks.Author summary: A classic question in the study of how information flows over social networks is this: Where across a network should we seed information, such as news about public health measures or employment opportunities, so that it spreads well? Using a simple gossip-style model of information spread on a network, we evaluate different algorithms for selecting a set of initial seeds and their subsequent performance on maximizing the minimum probability that anyone receives the spreading information. That is, we define “spreading well” as everyone in the network having a good chance of receiving the target information. We introduce a new, large-scale benchmark of 174 networks for evaluating information seeding algorithms, two new measures for quantifying and comparing algorithm performance on this task, and 10 new seeding algorithms. These new algorithms exploit theoretical insights about how network structure can influence information access, allowing them to avoid a significant computational bottleneck present in existing solutions and scale up to much larger networks. Finally, we show that a meta-learning algorithm that learns which particular algorithm to run on a network, based only on its structural signature, is more scalable than past solutions and remains highly accurate.