Higher order monotonicity and submodularity of influence in social networks: From local to global

doi:10.1016/j.ic.2022.104864

	Higher order monotonicity and submodularity of influence in social networks: From local to global
	Chen, Wei 1; Li, Qiang 2,3; Shan, Xiaohan 4; Sun, Xiaoming 2,3; Zhang, Jialin 2,3
	2022-05-01
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	285 页码:17
摘要	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.
关键词	Social networks General Threshold model Submodular Higher order monotonicity
DOI	10.1016/j.ic.2022.104864
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000886255300018
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/20310
专题	中国科学院计算技术研究所期刊论文
通讯作者	Shan, Xiaohan
作者单位	1.Microsoft Res Asia, 5 Dan Ling St, Beijing, Peoples R China 2.Univ Chinese Acad Sci, 19 A Yuquan Rd, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, 6 Kexueyuan South Rd, Beijing, Peoples R China 4.Tsinghua Univ, Dept Comp Sci & Technol, 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.