Cumulative activation in social networks

doi:10.1007/s11432-018-9609-7

	Cumulative activation in social networks
	Shan, Xiaohan 1; Chen, Wei 4; Li, Qiang 2,3; Sun, Xiaoming 2,3; Zhang, Jialin 2,3
	2019-05-01
发表期刊	SCIENCE CHINA-INFORMATION SCIENCES
ISSN	1674-733X
卷号	62 期号:5 页码:21
摘要	Most studies on influence maximization focus on one-shot propagation, i.e., the influence is propagated from seed users only once following a probabilistic diffusion model and users' activation are determined via single cascade. In reality it is often the case that a user needs to be cumulatively impacted by receiving enough pieces of information propagated to her before she makes the final purchase decision. In this paper we model such cumulative activation as the following process: first multiple pieces of information are propagated independently in the social network following the classical independent cascade model, then the user will be activated (and adopt the product) if the cumulative pieces of information she received reaches her cumulative activation threshold. Two optimization problems are investigated under this framework: seed minimization with cumulative activation (SM-CA), which asks how to select a seed set with minimum size such that the number of cumulatively active nodes reaches a given requirement eta; influence maximization with cumulative activation (IM-CA), which asks how to choose a seed set with fixed budget to maximize the number of cumulatively active nodes. For SM-CA problem, we design a greedy algorithm that yields a bicriteria O(ln n)-approximation when eta = n, where n is the number of nodes in the network. For both SM-CA problem with eta < n and IM-CA problem, we prove strong inapproximability results. Despite the hardness results, we propose two efficient heuristic algorithms for SM-CA and IM-CA respectively based on the reverse reachable set approach. Experimental results on different real-world social networks show that our algorithms significantly outperform baseline algorithms.
关键词	social networks cumulative activation influence maximization seed minimization
DOI	10.1007/s11432-018-9609-7
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61502449] ; National Natural Science Foundation of China[61602440] ; National Basic Research Program of China (973)[2016YFB1000201]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000464862800001
出版者	SCIENCE PRESS
引用统计	被引频次：9[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4274
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shan, Xiaohan; Chen, Wei; Li, Qiang; Sun, Xiaoming; Zhang, Jialin
作者单位	1.Tsinghua Univ, Dept Comp Sci & Technol, Beijing 100084, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 4.Microsoft, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Shan, Xiaohan,Chen, Wei,Li, Qiang,et al. Cumulative activation in social networks[J]. SCIENCE CHINA-INFORMATION SCIENCES,2019,62(5):21.
APA	Shan, Xiaohan,Chen, Wei,Li, Qiang,Sun, Xiaoming,&Zhang, Jialin.(2019).Cumulative activation in social networks.SCIENCE CHINA-INFORMATION SCIENCES,62(5),21.
MLA	Shan, Xiaohan,et al."Cumulative activation in social networks".SCIENCE CHINA-INFORMATION SCIENCES 62.5(2019):21.