Proceedings of the AAAI Conference on Artificial Intelligence · 2014 · 178 citations · 19 references
Social SciencesSociologyCollective BehaviorRecommender SystemsSocial InfluenceInformation SpreadNetwork PropagationSocial Network AnalysisStochastic NetworksInfluence PropagationInformation Diffusion ModelsNetwork GraphsNode InfluenceSocial Influence ModelingSocial Network InfluenceSolution GenerationSolution Quality Assessment
Influence maximization is a problem to find small sets of highly influential individuals in a social network to maximize the spread of influence under stochastic cascade models of propagation. Although the problem has been well-studied, it is still highly challenging to find solutions of high quality in large-scale networks of the day. While Monte-Carlo-simulation-based methods produce near-optimal solutions with a theoretical guarantee, they are prohibitively slow for large graphs. As a result, many heuristic methods without any theoretical guarantee have been developed, but all of them substantially compromise solution quality. To address this issue, we propose a new method for the influence maximization problem. Unlike other recent heuristic methods, the proposed method is a Monte-Carlo-simulation-based method, and thus it consistently produces solutions of high quality with the theoretical guarantee. On the other hand, unlike other previous Monte-Carlo-simulation-based methods, it runs as fast as other state-of-the-art methods, and can be applied to large networks of the day. Through our extensive experiments, we demonstrate the scalability and the solution quality of the proposed method.
19
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
Mining the network value of customers
Pedro Domingos, Matt Richardson · 2001 · 2.9K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7
Efficient influence maximization in social networks
Wei Chen, Yajun Wang, Siyu Yang · 2009 · 2.2K citations