  The research of influence propagation in social networks via word-of-mouth
processes has been given considerable attention in recent years. Arguably, the
most fundamental problem in this domain is influence maximization, where the
goal is to identify a seed set of individuals that can trigger a large cascade
of influence in the network. While there has been significant progress
regarding this problem and its variants, one basic shortcoming of the models is
that they lack the flexibility in the way the budget is allocated to
individuals. Indeed, budget allocation is a critical issue in advertising and
viral marketing. Taking the other point of view, known models allowing flexible
budget allocation do not take into account the influence spread in the network.
We introduce a generalized model that captures both budgets and influence
propagation simultaneously.
  For the offline setting, we identify a large family of budget-based
propagation functions that admit tight approximation guarantee. This family
extends most of the previously studied influence models, including the
well-known Triggering model. We establish that any function in this family
implies an instance of a monotone submodular function maximization over the
integer lattice subject to a knapsack constraint. This problem is known to
admit an optimal (1-1/e)-approximation. We also study the price of anarchy of
the multi-player game that extends the model and establish tight results.
  For the online setting, in which an unknown subset of agents arrive in a
random order and the algorithm needs to make an irrevocable budget allocation
in each step, we develop a 1/(15e)-competitive algorithm. This setting extends
the secretary problem, and its variant, the submodular knapsack secretary
problem. Notably, our algorithm improves over the best known approximation for
the latter problem, even though it applies to a more general setting.
