Computing and maximizing influence in linear threshold and triggering models
We establish upper and lower bounds for the influence of a set of nodes in certain types of contagion models. We derive two sets of bounds, the first designed for linear threshold models, and the second more broadly applicable to a general class of triggering models, which subsumes the popular independent cascade models, as well. We quantify the gap between our upper and lower bounds in the case of the linear threshold model and illustrate the gains of our upper bounds for independent cascade models in relation to existing results. Importantly, our lower bounds are monotonic and submodular, implying that a greedy algorithm for influence maximization is guaranteed to produce a maximizer within a 1 − 1 e -factor of the truth. Although the problem of exact influence computation is NP-hard in general, our bounds may be evaluated efficiently. This leads to an attractive, highly scalable algorithm for influence maximization with rigorous theoretical guarantees.
A series of recent papers [12,21,13] establish computable upper bounds on the influence when information propagates in a stochastic manner according to an independent cascade model. In such a model, the infection spreads in rounds, and each newly infected node may infect any of its neighbors in the succeeding round. Central to the bounds is a matrix known as the hazard matrix, which encodes the transmission probabilities across edges in the graph. A recent paper by Lee et al. [11] leverages "sensitive" edges in the network to obtain tighter bounds via a conditioning argument. Such bounds could be maximized to obtain a surrogate for the influence-maximizing set in the network; however, the tightness of the proposed bounds is yet unknown. The independent cascade model may be viewed as a special case of a more general triggering model, in which the infection status of each node in the network is determined by a random subset of neighbors [9]. The class of triggering models also includes another popular stochastic infection model known as the linear threshold model, and bounds for the influence function in linear threshold models have been explored in an independent line of work [5,23,4]. Naturally, one might wonder whether influence bounds might be derived for stochastic infection models in the broader class of triggering models, unifying and extending the aforementioned results. We answer this question affirmatively by establishing upper and lower bounds for the influence in general triggering models. Our derived bounds are attractive for two reasons: First, we are able to quantify the gap between our upper and lower bounds in the case of linear threshold models, expressed in terms of properties of the graph topology and edge probabilities governing the likelihood of infection. Second, maximizing a lower bound on the influence is guaranteed to yield a lower bound on the true maximum influence in the graph. Furthermore, as shown via the theory of submodular functions, the lower bounds in our paper may be maximized efficiently up to a constantfactor approximation via a greedy algorithm, leading to a highly-scalable algorithm with provable guarantees. To the best of our knowledge, the only previously established bounds for influence maximization are those mentioned above for the special cases of independent cascade and linear threshold models, and no theoretical or computational guarantees were known.
The remainder of our paper is organized as follows: In Section 2, we fix notation to be used in the paper and describe the aforementioned infection models in greater detail. In Section 3, we establish upper and lower bounds for the linear threshold model, which we extend to triggering models in Section 4. Section 5 addresses the question of maximizing the lower bounds established in Sections 3 and 4, and discusses theoretical guarantees achievable using greedy algorithms and convex relaxations of the otherwise intractable influence maximization problem. We report the results of simulations in Section 6, and conclude the paper with a selection of open research questions in Section 7.
The paper develops new upper and lower bounds for computing the influence of a set in the Linear Threshold cascade model, and in the the General Triggering model, which includes the Independent Cascade model as a special case. These seem to be the first such bounds for the Linear Threshold model, and the bounds for the Independent Cascade model are tighter in some cases than previous results. The analysis is based on fairly elementary "path weight" arguments. These are tighter in the Linear Threshold model, where at most one live path exists from a source to any given node, than in the General Triggering model. The paper analyzes the conditions under which the upper and lower bounds are within a constant factor of each other, and provides examples for which their bounds are tighter than previous ones (ref [16]).   The authors further show that the lower bounds are submodular, and so they can be optimized nearly optimally using the greedy algorithm as a principled surrogate for the true influence. Experiments on synthetic graphs demonstrate that the bounds are valid, and that optimizing the bounds as surrogates performs very well for the original influence maximization task.  
The paper is very well written and presents a clear and straightforward analysis of bounds for the influence function in the linear threshold and triggering models.   The technical quality is high. The techniques are straightforward (elementary probability arguments) and provide bounds that appear to be useful in practice. The analysis is careful and thorough. For example, Section 3.3 includes both an example of when the bounds are bad, as well as an analysis of conditions under which the bounds are tight. The experiments demonstrate the the bounds are useful in practice for influence maximization.  The potential impact is reasonable. There continues to be interest in influence maximization and diffusion processes in the CS literature, and I can envision follow-on work or application of these methods. (Note to authors: in general I feel this line of work has become regrettably detached from real applications, so the extent to which you can connect back to real applications would strengthen future work.)  I found two areas that could use further discussion to strengthen the paper:  1) In the experiments on influence maximization, the main benefit of the proposed method is running time. It would be appropriate to compare running times of different methods to quantify the accuracy vs. running-time tradeoff of maximizing the lower bounds. (It appears there is little accuracy lost, so simply reporting running times may tell the story you need to tell).  2) Some further discussion of the comparison to the results of Lemmonier et al. would strengthen the paper. For example, can you quantify empirically the conjecture in Line 217 (condition for when your bound is tighter)? This conjecture suggests that your bound may perform best in the "sub-critical" regime (small cascades relative to graph size). I note that your experiments generally seem to have small cascade sizes (influence < 30 in graphs with 900 nodes). Do your bounds also perform well in with large cascades?   Minor notes:   Definition 1. The wording is somewhat misleading. It says that "f is submodular if either (i) or (ii)" but does not say that (i) and (ii) are equivalent conditions. Consider adding a statement to this effect for clarity.  In Section 5.2 you discuss approximately optimizing the lower bounds, but do not actually state that this problem is NP-hard and cannot be solved optimally. The results in the appendix seem to suggest this. If it is true, I suggest you state it in the main text of the paper.