Semantic Web Dog Food

Presented at: 20th International World Wide Web Conference (WWW2011)

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

Kempe et al. (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. 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.

CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social Networks was presented at this event.

Keywords: World Wide Web

Resource URI on the dog food server: http://data.semanticweb.org/conference/www/2011/poster/celf-optimizing-the-greedy-algorithm-for-influence

Explore this resource elsewhere:

• on Snorql
• on Sindice
• on dotAC Explorer