A Numerical Evaluation of the Accuracy of Influence Maximization Algorithms
2020-08-24Springer 2020Code Available0· sign in to hype
Hautahi Kingi, Li-An Daniel Wang, Tom Shafer, Minh Huynh, MikeTrinh, Aaron Heuser
Code Available — Be the first to reproduce this paper.
ReproduceCode
- github.com/hautahi/IM-EvaluationIn papernone★ 6
Abstract
We develop an algorithm to compute exact solutions to the influence maximization problem using concepts from reverse influence sampling (RIS). We implement the algorithm using GPU resources to evaluate the empirical accuracy of theoretically-guaranteed greedy and RIS approximate solutions. We find that the approximations yield solutions that are remarkably close to optimal — usually achieving greater than 99% of the optimal influence spread. These results are consistent across a wide range of network structures.