text: Although influence maximization problem has been extensively studied over the past ten years, majority of existing work adopt one of the following models: or . In the zero-feedback model, we have to commit the seed users all at once in advance, this strategy is also known as non-adaptive policy. In the full-feedback model, we select one seed at a time and wait until the diffusion completes, before selecting the next seed. Full-feedback model has better performance but potentially huge delay, zero-feedback model has zero delay but poorer performance since it does not utilize the observation that may be made during the seeding process. To fill the gap between these two models, we propose , which allows us to select a seed at any intermediate stage. We develop a novel @math -greedy policy that, for the first time, achieves a bounded approximation ratio.
  @cite_0: Influence maximization is the problem of selecting top @math seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of influence ranking (IR) and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the influence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is much more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory.
  @cite_1: The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a (1 -- 1 e)2-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call locally-adaptive policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the (1 -- 1 e)2-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most k that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from P lanted -C lique that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of locally-adaptive policies we use in the main result.
  @cite_3: Many problems in artificial intelligence require adaptively making a sequence of decisions with uncertain outcomes under partial observability. Solving such stochastic optimization problems is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. In addition to providing performance guarantees for both stochastic maximization and coverage, adaptive submodularity can be exploited to drastically speed up the greedy algorithm by using lazy evaluations. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse AI applications including management of sensing resources, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases, improve approximation guarantees and handle natural generalizations.
  @cite_2: It has been reported that 40 of consumers will share an email offer with their friend and 28 of consumers will share deals via social media platforms. This motivates us to study the influence maximization discount allocation problem: given a social network and a limited marketing budget, which set of initial users should be selected to receive the discount, and how much should the discounts be worth? Our goal is to maximize the number of customers who finally adopt the target product. We investigate this problem under both non-adaptive and adaptive settings. In the first setting, we have to commit the set of initial users and corresponding discounts all at once in advance. In the latter case, given that an user has been offered a discount, we are able to know immediately her decision on whether or not to accept that discount, therefore, the decision process is performed in a sequential manner based on the feedback from previously selected users. We propose a simple greedy policy with an approximation ratio of (1-1 e) in non-adaptive setting. For the significantly more complex adaptive setting, we propose a series of adaptive policies with bounded approximation ratio in terms of expected utility.
summary: The first category is non-adaptive influence maximization: we must find a set of influential customers all at once in advance subject to a budget constraint. first formalized and studied this problem under two diffusion models, namely Independent Cascade model and Linear Threshold model. study influence maximization problem under various extended models. The second category is adaptive influence maximization, which is closely related to adaptive stochastic submodular maximization @cite_3 @cite_1 @cite_0 @cite_2 . Existing studies mainly adopt full-feedback model, assuming that we can observe the full status of the previous cascade before selecting the next seed. We relax this assumption by incorporating partial-feedback and develop a novel @math -greedy adaptive policy that achieves the first bounded approximation ratio under partial-feedback model.