Influence maximization (IM), which selects a set of k users (called seeds) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications such as viral marketing and network monitoring. Existing IM solutions fail to consider the highly dynamic nature of social influence, which results in either poor seed qualities or long processing time when the network evolves. To address this problem, we define a novel IM query named Stream Influence Maximization (SIM) on social streams. Technically, SIM adopts the sliding window model and maintains a set of k seeds with the largest influence value over the most recent social actions. Next, we propose the Influential Checkpoints (IC) framework to facilitate continuous SIM query processing. The IC framework creates a checkpoint for each window shift and ensures an e-approximate solution. To improve its efficiency, we further devise a Sparse Influential Checkpoints (SIC) framework which selectively keeps O(logN β checkpoints for a sliding window of size N and maintains an e(1−β) 2-approximate solution. Experimental results on both real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed frameworks against the state-of-the-art IM approaches.
Several works @cite_32 @cite_21 studied how to continuously estimate a function in the sliding window model. They leverage special properties of target functions to achieve sublinear performance and reasonable quality. Let @math be the target function, and @math , @math , @math be three sequences on streams such that @math is a tail subsequence of @math and @math is contiguous to @math . The exponential histogram @cite_32 is proposed to approximate weakly additive functions, i.e., @math for some small constant @math . The smooth histogram @cite_21 requires that the target functions are @math -smooth . Specifically, we say @math is @math -smooth if @math , then @math for some @math . Following the analysis in @cite_21 , smooth histograms are applicable only when @math can be computed with an approximation ratio of at least @math in the append-only streaming setting. In this paper, we use monotone submodular influence functions @cite_8 widely adopted in the social influence analysis. However, monotone submodular functions are not weakly additive and existing SSO algorithms @cite_1 @cite_19 can only achieves an approximation of at most @math . This imply that these techniques cannot be directly applied to our scenario.
@cite_8 @cite_21 @cite_1 @cite_32 @cite_19
2128846062 2801503411 2963116072 2089729462
In the streaming model elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and non-trivial task in the model. This becomes even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar, Gionis, Indyk and Motwani [15] presented exponential histograms, an effective method for estimating statistics on sliding windows. In this paper we present a new smooth histograms method that improves the approximation error rate obtained via exponential histograms. Furthermore, our smooth histograms method not only captures and improves multiple previous results on sliding windows bur also extends the class functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: Lp norms for p notin [1,2], frequency moments, length of increasing subsequence and geometric mean. We initiate the study of numerical linear algebra in the sliding window model, where only the most recent @math updates in the data stream form the underlying set. Although most existing work in the sliding window model uses the smooth histogram framework, most interesting linear-algebraic problems are not smooth; we show that the spectral norm, vector induced matrix norms, generalized regression, and low-rank approximation are not amenable for the smooth histogram framework. To overcome this challenge, we first give a deterministic algorithm that achieves spectral approximation in the sliding window model that can be viewed as a generalization of smooth histograms, using the Loewner ordering of PSD matrices. We then give algorithms for both spectral approximation and low-rank approximation that are space-optimal up to polylogarithmic factors. Our algorithms are based on a new notion of "reverse online" leverage scores that account for both how unique and how recent a row is, while preserving sparsity so that both our algorithms run in input sparsity runtime, up to lower order factors. We show that our techniques have applications to linear-algebraic problems in other settings. Specifically, we show that our analysis immediately implies an algorithm for low-rank approximation in the online setting that is space-optimal up to logarithmic factors, as well as nearly input sparsity time. We show our deterministic spectral approximation algorithm can be used to handle @math spectral approximation in the sliding window model under a certain assumption on the bit complexity of the entries. Finally, we show that our downsampling framework can be applied to the problem of approximate matrix multiplication and provide upper and lower bounds that are tight up to @math factors. In this paper, we study the problem of maximizing continuous submodular functions that naturally arise in many learning applications such as those involving utility functions in active learning and sensing, matrix approximations and network inference. Despite the apparent lack of convexity in such functions, we prove that stochastic projected gradient methods can provide strong approximation guarantees for maximizing continuous submodular functions with convex constraints. More specifically, we prove that for monotone continuous DR-submodular functions, all fixed points of projected gradient ascent provide a factor @math approximation to the global maxima. We also study stochastic gradient methods and show that after @math iterations these methods reach solutions which achieve in expectation objective values exceeding @math . An immediate application of our results is to maximize submodular functions that are defined stochastically, i.e. the submodular function is defined as an expectation over a family of submodular functions with an unknown distribution. We will show how stochastic gradient methods are naturally well-suited for this setting, leading to a factor @math approximation when the function is monotone. In particular, it allows us to approximately maximize discrete, monotone submodular optimization problems via projected gradient ascent on a continuous relaxation, directly connecting the discrete and continuous domains. Finally, experiments on real data demonstrate that our projected gradient methods consistently achieve the best utility compared to other continuous baselines while remaining competitive in terms of computational effort. A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". Our main result is that for any fixed instance that exhibits a certain "symmetry gap" in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g. the optimality of (1-1 e)-approximation for monotone submodular maximization under a cardinality constraint, and the impossibility of (1 2+epsilon)-approximation for unconstrained (non-monotone) submodular maximization. It follows from our result that (1 2+epsilon)-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0.309-approximation for this problem, improving the previously known factor of 1 4-o(1).As another application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. A (1 6-o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k≫=2, there is a class of matroids of fractional base packing number nu = k (k-1), such that any algorithm achieving a better than (1-1 nu)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1 2 (1-1 nu-o(1))-approximation algorithm for the same problem. Our hardness results hold in fact for very special symmetric instances. For such symmetric instances, we show that the approximation factors of 1 2 (for submodular maximization subject to a matroid constraint) and 1-1 nu (for a matroid base constraint) can be achieved algorithmically and hence are optimal.