Spreading information in social networks containing adversarial users

Abstract

In the modern day, social networks have become an integral part of how people communicate information and ideas. Consequently, leveraging the network to maximize information spread is a science that is applied in viral marketing, political propaganda. In social networks, an idea/information starts from a small group of users (known as seed users) and is propagated through the network via connections of the seed users. There are limitations on the number of seed users that can be convinced to adopt a certain idea. Therefore, the problem exists in finding a small set of users who can maximally spread an idea/information. This is known as the influence maximization problem. While this problem has been studied extensively, the presence of potential adversarial users and their impact on the information spread, has not been considered in existing solutions. In this thesis, we study the problem of spreading information to Target users while limiting the spread from reaching adversarial(Non Target) users. To this end, we consider a hard constraint - the objective is to maximize the information spread among the Target users while the number of Non-Target users to whom the information reaches is limited by a hard constraint. We design two algorithms - Natural Greedy and Multi Greedy with efficient RIS based implementations. We run our solutions on real world social networks to study the information spread. Finally, we evaluate the quality of our solutions on different models of diffusion and network settings.