CELF++: optimizing the greedy algorithm for influence maximization in social networks
Lists
Only you see this
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...