A Heuristic Approach to Solving Stackelberg Game to Mitigate Misinformation for Large Real World Networks

With the rise in popularity of social media, misinformation has become an increasingly serious problem. Most of the strategies to reduce the spread of misinformation proposed in the extensive literature on the subject are not scalable to large real world networks. In this project, a potentially scalable strategy is pursued: determine sets of nodes in a large network that, when blocked, would minimize the spread of fake news.

The foundation of our approach are Stackelberg Games. The specific Stackelberg Game for this project is as follows: the defender first chooses a number of nodes (k _D ) to block, after which the attacker chooses a number of nodes (k _A ) to attack that will maximize the spread of fake news. The goal of the defender is to minimize the attacker’s influence on the rest of the network. The defender does so by greedily choosing k _D nodes, whereas the attacker tries to maximize their influence using Greedy and CELF algorithms derived from Kempe et al. (2003) and Leskovec et al. (2007) respectively. To enhance scalability, degree and page rank centrality measures are used to prune the nodes to attack and defend.