中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Cumulative activation in social networks

文献类型：期刊论文

作者Shan, Xiaohan4; Chen, Wei1; Li, Qiang2,3; Sun, Xiaoming2,3; Zhang, Jialin2,3
刊名SCIENCE CHINA-INFORMATION SCIENCES
出版日期2019-05-01
卷号62期号:5页码:21
ISSN号1674-733X
关键词social networks cumulative activation influence maximization seed minimization
DOI10.1007/s11432-018-9609-7
英文摘要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.
资助项目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
语种英语
出版者SCIENCE PRESS
WOS记录号WOS:000464862800001
源URL[http://119.78.100.204/handle/2XEOYT63/4273]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Shan, Xiaohan; Chen, Wei; Li, Qiang; Sun, Xiaoming; Zhang, Jialin
作者单位1.Microsoft, Beijing 100080, Peoples R China
2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
3.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China
4.Tsinghua Univ, Dept Comp Sci & Technol, Beijing 100084, 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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。