MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Social Networks

Influence maximization (IM) is one of the most important problems in social network analysis. Its objective is to find a given number of seed nodes who maximize the spread of information through a social network. Since it is an NPhard problem, many approximate/heuristic methods have been developed, and a number of them repeats Monte Carlo (MC) simulations over and over, specifically tens of thousands of times or more, to reliably estimate the influence of a seed set, i.e., the number of infected nodes. In this work, we present an inductive machine learning method, called Mon te Carlo S imulator (MONSTOR), to predict the results of MC simulations on networks unseen during training. MONSTOR can greatly accelerate existing IM methods by replacing repeated MC simulations. In our experiments, MONSTOR achieves near-perfect accuracy on unseen real social networks with little sacrifice of accuracy in IM use cases. 1 Introduction Viral marketing via influence maximization has received considerable attention over the last two decades, as social networks have become an essential part of our daily lives. Many people connect to and acquire information from social networks on a daily basis, and thus information diffusion over such social networks is often more effective than that over conventional media, such as newspapers and television. Influence maximization (IM) is to find a certain number of seed nodes who maximize the spread of information through a social network. There exist several real-world applications where influence maximization played a key role, such as 2010 U.S. congressional elections, attempts to raise awareness about HIV among homeless youth, and so on [2, 18].