An Overall Evaluation on Benefits of Competitive Influence Diffusion

作     者：Guo, Jianxiong Zhang, Yapu Wu, Weili 

作者机构：Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON BIG DATA》 (IEEE Trans. Big Data)

年 卷 期：2023年第9卷第2期

页      面：653-664页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [1747818, 1907472] Direct For Computer & Info Scie & Enginr Div Of Information & Intelligent Systems Funding Source: National Science Foundation Direct For Computer & Info Scie & Enginr Div Of Information & Intelligent Systems Funding Source: National Science Foundation 

主　　题：Social networking (online) Approximation algorithms Linear programming Computational modeling Greedy algorithms Heuristic algorithms Big Data Overall evaluations influence maximization submodularity modular-modular proceduce sampling techniques social networks approximation algorithm 

摘      要：Influence maximization (IM) is a representative and classic problem that has been studied extensively before. The most important application derived from the IM problem is viral marketing. Take us as a promoter, we want to get benefits from the influence diffusion in a given social network, where each influenced (activated) user is associated with a benefit. However, there is often competing information initiated by our rivals that diffuses in the same social network at the same time. Consider such a scenario, a user is influenced by both our information and our rivals information. Here, the benefit from this user should be weakened to a certain degree. How to quantify the degree of weakening? Based on that, we propose an overall evaluation on benefits of influence (OEBI) problem. We prove the objective function of the OEBI problem is not monotone, not submodular, and not supermodular. Fortunately, we can decompose this objective function into the difference of two submodular functions and adopt a modular-modular procedure to approximate it with a data-dependent approximation guarantee. Because of the difficulty to compute the exact objective value, we design a group of unbiased estimators by exploiting the idea of reverse influence sampling, which can improve time efficiency significantly without losing its approximation ratio. Finally, numerical experiments on real datasets verified the effectiveness of our approaches regardless of performance and efficiency.