2014 StabilityofInfluenceMaximizatio

• (He & Kempe, 2014) ⇒ Xinran He, and David Kempe. (2014). “Stability of Influence Maximization.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623746

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Stability+of+Influence+Maximization
• http://dl.acm.org/citation.cfm?id=2623330.2623746&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; influence maximization; noise; robust optimization; submodular optimization; uncertainty

Abstract

The present article serves as an erratum to our paper of the same title, which was presented and published in the KDD-2014 conference. In that article, we claimed falsely that the objective function defined in Section 1.4 is non-monotone submodular. We are deeply indebted to Debmalya Mandal, Jean Pouget-Abadie and Yaron Singer for bringing to our attention a counter-example to that claim.

Subsequent to becoming aware of the counter-example, we have shown that the objective function is in fact NP-hard to approximate to within a factor of O (n^1-ε) for any ε > 0.

In an attempt to fix the record, the present article combines the problem motivation, models, and experimental results sections from the original incorrect article with the new hardness result. We would like readers to only cite and use this version (which will remain an unpublished note) instead of the incorrect conference version.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 StabilityofInfluenceMaximizatio	David Kempe Xinran He			Stability of Influence Maximization				10.1145/2623330.2623746		2014