Real-time Topic-aware Influence Maximization Using Preprocessing
This work addresses the computational efficiency challenge for real-time influence maximization in social networks, though it is incremental as it builds on existing topic-aware models.
The paper tackles the problem of topic-aware influence maximization in social networks by proposing preprocessing methods to avoid recalculating influence spread for each new item, achieving microsecond online response times and competitive influence spread in empirical tests.
Influence maximization is the task of finding a set of seed nodes in a social network such that the influence spread of these seed nodes based on certain influence diffusion model is maximized. Topic-aware influence diffusion models have been recently proposed to address the issue that influence between a pair of users are often topic-dependent and information, ideas, innovations etc. being propagated in networks (referred collectively as items in this paper) are typically mixtures of topics. In this paper, we focus on the topic-aware influence maximization task. In particular, we study preprocessing methods for these topics to avoid redoing influence maximization for each item from scratch. We explore two preprocessing algorithms with theoretical justifications. Our empirical results on data obtained in a couple of existing studies demonstrate that one of our algorithms stands out as a strong candidate providing microsecond online response time and competitive influence spread, with reasonable preprocessing effort.