Fairness in Influence Maximization

Online social networks such as Facebook, LinkedIn, and Twitter are an inseparable part of our life. They help us to interact with other people at little cost (and) easily. These networks play an essential role in spreading information, ideas, and knowledge among users. This results in affecting or changing users' opinions about certain topics. When a user of a social network receives a piece of information, she may share it with her friends, and her friends can share it with her friends’ friends and so on. In this way, the information may spread to a large number of people. In computer science, these phenomena have been studied under two names information diffusion and social influence. These topics have received a high level of attention by researchers and have many applications in advertisement, news propagation, disease spread, viral marketing, sales promotions and many others. However, social media has been criticized for creating situations that some users or groups of users have a high chance of receiving information or getting most of the attention while others stay disregarded, thus discriminating among users or groups of users.~Note that such discrimination or disparity among different groups of a network especially in real world applications related to health, education, and job opportunities, can put minority groups at a big disadvantage. In computational social choice, the notion of group fairness was developed in order to address this issue. The study of this notion in the context of information diffusion is the main focus of this thesis. We study several optimization problems with the focus of addressing the groups of a network in a fair way when information is spread in the network. We first consider the standard maximin criterion for group fairness and study the problem of determining key seed nodes to maximize the minimum probability that groups (or communities) receive information. We define two different variants of this problem that involve probabilistic strategies and analyze the relation between the two problems. We then design approximation algorithms achieving a constant multiplicative factor of $1-1/e$ minus an arbitrarily small additive error, while the original deterministic maximin problem was inapproximable. Our experimental study shows that the our methods ex-ante fairness values, i.e., minimum expected probability that an individual (or group) receives the information, dominate over the fairness values achieved by previous approaches. Interestingly and maybe more surprisingly, we observe that even the our methods ex-post fairness values, i.e., fairness values obtained by sampling single sets according to the probabilistic strategies, frequently outperform the ex-post fairness achieved by other tested methods. When using the maximin criterion, it is likely that still different groups receive different shares of information. Hence, we turn to study two classes of optimization problems involving notions of group fairness that aim to lessen this unfavourable situation. The goal here is to maximize the overall spread (or spread within a target set) while enforcing strict levels of fairness via constraints (either ex-post or ex-ante). The constraints require the coverage among groups to be similar. The level of fairness hence becomes a user choice rather than a property to be observed upon output. We present several NP-hardness and hardness of approximation results, even in the case that the fairness constraints are violated (multiplicatively and additively). For one of our problems we still design an algorithm with both constant approximation factor and constant fairness violation. For the other problem class, we propose two heuristics that allow the user to choose the tolerated fairness violation.~In an extensive experimental study, we show that our algorithms perform well in practice, that is, they achieve the best fairness values while maintaining similar levels of total spread. Finally, we study optimization problems with the goal of modifying the network structure by adding links in such a way that the minimum community coverage is maximized when information is spread using a purely efficiency oriented seeding strategy. We propose two optimization problems and present NP-hardness and hardness of approximation results for them. For some special cases, we propose efficient algorithms as well as several heuristics for solving one of the problems. In our experimental study, we show that our approach can be very successful in practice.