期刊
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
卷 15, 期 5, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3447396
关键词
Adaptive influence maximization; social networks; integer lattice; adaptive dr-submodularity; sampling techniques; approximation algorithm
资金
- National Science Foundation [1747818, 1907472]
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1907472] Funding Source: National Science Foundation
This article explores the Adaptive Influence Maximization with Multiple Activations (Adaptive-IMMA) problem, considering the probability of successful activation of seed nodes and multiple activation attempts. The concept of adaptive dr-submodularity is introduced and mathematically modeled on the domain of integer lattice to maximize an adaptive monotone and dr-submodular function. The study presents a non-trivial generalization of adaptive submodularity and combines a greedy policy with sampling techniques to estimate expected influence spread efficiently.
Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this article, we study the adaptive influence maximization with multiple activations (Adaptive-IMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process; if no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive dr-submodularity, and show our Adaptive-IMMA is the problem that maximizing an adaptive monotone and dr-submodular function under the expected knapsack constraint. Adaptive dr-submodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a non-trivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据