CELF++: optimizing the greedy algorithm for influence maximization in social networks

Amit Goyal, Wei Lu, Laks V. S. Lakshmanan

Abstract

Kempe et al. [4] (KKT) showed the problem of influence maximization is NP-hard and a simple greedy algorithm guarantees the best possible approximation factor in PTIME. However, it has two major sources of inefficiency. First, finding the expected spread of a node set is #P-hard. Second, the basic greedy algorithm is quadratic in the number of nodes. The first source is tackled by estimating the spread using Monte Carlo simulation or by using heuristics[4, 6, 2, 5, 1, 3]. Leskovec et al. proposed the CELF algorithm for tackling the second. In this work, we propose CELF++ and empirically show that it is 35-55% faster than CELF.
BibTeX
@inproceedings{goyal2011celf,
  author = {Amit Goyal and Wei Lu and Laks V. S. Lakshmanan},
  title = {{CELF++: optimizing the greedy algorithm for influence maximization in social networks}},
  booktitle = {The Web Conference},
  year = {2011},
  doi = {10.1145/1963192.1963217},
}

Loading related content...

Figure