Approximating Special Social Influence Maximization Problems  

作　　者：Jie Wu Ning Wang 

机构地区：[1]the Department of Computer and Information Sciences,Temple University.Philadelphia,PA 19122,USA [2]the Department of Computer Science,Rowan University,Glassboro,NJ 08028,USA

出　　处：《Tsinghua Science and Technology》2020年第6期703-711,共9页清华大学学报（自然科学版（英文版）

基　　金：the National Science Foundation(NSF)grants Computer and Network Systems(CNS)1824440,CNS 1828363,CNS 1757533,CNS 1618398,CNS 1651947,and CNS 1564128。

摘　　要：Social Influence Maximization Problems(SIMPs)deal with selecting k seeds in a given Online Social Network(OSN)to maximize the number of eventually-influenced users.This is done by using these seeds based on a given set of influence probabilities among neighbors in the OSN.Although the SIMP has been proved to be NP-hard,it has both submodular(with a natural diminishing-return)and monotone(with an increasing influenced users through propagation)that make the problem suitable for approximation solutions.However,several special SIMPs cannot be modeled as submodular or monotone functions.In this paper,we look at several conditions under which non-submodular or non-monotone functions can be handled or approximated.One is a profit-maximization SIMP where seed selection cost is included in the overall utility function,breaking the monotone property.The other is a crowd-influence SIMP where crowd influence exists in addition to individual influence,breaking the submodular property.We then review several new techniques and notions,including double-greedy algorithms and the supermodular degree,that can be used to address special SIMPs.Our main results show that for a specific SIMP model,special network structures of OSNs can help reduce its time complexity of the SIMP.

关 键 词：influence maximization online social networks submodular function 

分 类 号：C912.3[经济管理] O157.5[社会学]