ausblenden:
Schlagwörter:
cs.SI,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Learning, cs.LG,Statistics, Machine Learning, stat.ML
Zusammenfassung:
A typical viral marketing model identifies influential users in a social
network to maximize a single product adoption assuming unlimited user
attention, campaign budgets, and time. In reality, multiple products need
campaigns, users have limited attention, convincing users incurs costs, and
advertisers have limited budgets and expect the adoptions to be maximized soon.
Facing these user, monetary, and timing constraints, we formulate the problem
as a submodular maximization task in a continuous-time diffusion model under
the intersection of a matroid and multiple knapsack constraints. We propose a
randomized algorithm estimating the user influence in a network
($|\mathcal{V}|$ nodes, $|\mathcal{E}|$ edges) to an accuracy of $\epsilon$
with $n=\mathcal{O}(1/\epsilon^2)$ randomizations and
$\tilde{\mathcal{O}}(n|\mathcal{E}|+n|\mathcal{V}|)$ computations. By
exploiting the influence estimation algorithm as a subroutine, we develop an
adaptive threshold greedy algorithm achieving an approximation factor $k_a/(2+2
k)$ of the optimal when $k_a$ out of the $k$ knapsack constraints are active.
Extensive experiments on networks of millions of nodes demonstrate that the
proposed algorithms achieve the state-of-the-art in terms of effectiveness and
scalability.
