The complexity of influence maximization problem in the deterministic linear threshold model

Zaixin Lu (), Wei Zhang (), Weili Wu (), Joonmo Kim () and Bin Fu ()
Additional contact information
Zaixin Lu: University of Texas at Dallas
Wei Zhang: Xi’an JiaoTong University
Weili Wu: University of Texas at Dallas
Joonmo Kim: Dankook University
Bin Fu: University of Texas–Pan American

Journal of Combinatorial Optimization, 2012, vol. 24, issue 3, No 15, 374-378

Abstract: Abstract The influence maximization is an important problem in the field of social network. Informally it is to select few people to be activated in a social network such that their aggregated influence can make as many as possible people active. Kempe et al. gave a $(1-{1 \over e})$ -approximation algorithm for this problem in the linear threshold model and the independent cascade model. In addition, Chen et al. proved that the exact computation of the influence given a seed set is #P-hard in the linear threshold model. Both of the two models are based on randomized propagation, however such information might be obtained by surveys and data mining techniques. This will make great difference on the complexity of the problem. In this note, we study the complexity of the influence maximization problem in deterministic linear threshold model. We show that in the deterministic linear threshold model, there is no n 1−ε -factor polynomial time approximation for the problem unless P=NP. We also show that the exact computation of the influence given a seed set can be solved in polynomial time.

Keywords: Social network; Inapproximation; Deterministic model (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9393-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:3:d:10.1007_s10878-011-9393-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9393-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().