中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
Higher order monotonicity and submodularity of influence in social networks: From local to global

文献类型：期刊论文

作者Chen, Wei4; Li, Qiang2,3; Shan, Xiaohan1; Sun, Xiaoming2,3; Zhang, Jialin2,3
刊名INFORMATION AND COMPUTATION
出版日期2022-05-01
卷号285页码:17
关键词Social networks General Threshold model Submodular Higher order monotonicity
ISSN号0890-5401
DOI10.1016/j.ic.2022.104864
英文摘要Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity implies global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function is monotone and submodular. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD -k (Alternating Difference -k) as a generalization of monotonicity and submodularity. Specifically, a set function f is called AD -k if all the t-th order differences off on all inputs have sign (-1)e+1 for every t & LE; k. We propose a refined version of KKT's conjecture: in the general threshold model, local AD -k implies global AD -k. We prove the correctness of our conjecture when the social graph is a DAG. Furthermore, we affirm our conjecture on general social graphs when k = & INFIN;.(c) 2022 Elsevier Inc. All rights reserved.
资助项目National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61872334] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDA27000000]
WOS研究方向Computer Science ; Mathematics
语种英语
WOS记录号WOS:000886255300018
出版者ACADEMIC PRESS INC ELSEVIER SCIENCE
源URL[http://119.78.100.204/handle/2XEOYT63/20309]  
专题中国科学院计算技术研究所期刊论文
通讯作者Shan, Xiaohan
作者单位1.Tsinghua Univ, Dept Comp Sci & Technol, Beijing, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, 6 Kexueyuan South Rd, Beijing, Peoples R China
3.Univ Chinese Acad Sci, 19 A Yuquan Rd, Beijing, Peoples R China
4.Microsoft Res Asia, 5 Dan Ling St, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Chen, Wei,Li, Qiang,Shan, Xiaohan,et al. Higher order monotonicity and submodularity of influence in social networks: From local to global[J]. INFORMATION AND COMPUTATION,2022,285:17.
APA Chen, Wei,Li, Qiang,Shan, Xiaohan,Sun, Xiaoming,&Zhang, Jialin.(2022).Higher order monotonicity and submodularity of influence in social networks: From local to global.INFORMATION AND COMPUTATION,285,17.
MLA Chen, Wei,et al."Higher order monotonicity and submodularity of influence in social networks: From local to global".INFORMATION AND COMPUTATION 285(2022):17.

入库方式： OAI收割

来源：计算技术研究所

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

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