How to Spread Information in Social Networks That Contain Adversarial Users
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 etc. 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, a 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 talk, we study how to spread information maximally with a hard constraint imposed on the number of adversarial users influenced. We formulate this as the Constrained Influence Maximization (CIM) problem and present its theoretical challenges followed by scalable algorithms and empirical results.
Madhavan Rajagopal Padmanabhan is a PhD student in the Department of Computer Science at Iowa State University. His research focuses on Information Diffusion, Submodular Optimization.