Influence maximization based on reachability sketches in dynamic graphs
- Influence maximization based on reachability sketches in dynamic graphs
- Dongeun Kim; Dongmin Hyeon; Jinoh Oh; Han, W.-S; YU, HWANJO
- Date Issued
- Influence maximization is the problem of selecting the most influential nodes in a given graph. The problem is applicable to viral marketing and is actively researched as social networks become the media of information propagation. To solve the challenges of influence maximization, previous works approximate the influence evaluationt to reduce the running time and to simultaneously guarantee the quality of those evaluations. We propose a new influence maximization algorithm that overcomes the limitations of the state of the art algorithms. We also devise our algorithm to process update operations of dynamic graphs. Our algorithm outperforms the state of the art algorithms TIM+ and SKIM in running time, and its influence spread is also comparable to the others. Our experiments show that processing update operations is faster than executing baselines each time. Additional experiments with synthetic graphs show that the process preserves the quality of influence spread. (C) 2017 Elsevier Inc. All rights reserved.
- Social network; Influence maximization; Dynamic graph
- Article Type
- Information Sciences, vol. 394-395, page. 217 - 231, 2017-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.