2016/12/08 by Nan Du, Yingyu Liang, Du, Nan +9 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Human Mobility and Location-Based Analysis #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI) #cs.DS #cs.LG #cs.SI #stat.ML
paper · pdf · doi:10.48550/arxiv.1612.02712
45 pages, to appear in Journal of Machine Learning Research. arXiv admin note: substantial text overlap with arXiv:1312.2164, arXiv:1311.3669
openalex publication_date 2016/12/08 · arxiv created 2017/01/29 · arxiv updated 2017/01/31 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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 (|V| nodes, |E| edges) to an accuracy of ε with n=O(1/ε2) randomizations and O(n|E|+n|V|) computations. By exploiting the influence estimation algorithm as a subroutine, we develop an adaptive threshold greedy algorithm achieving an approximation factor ka/(2+2 k) of the optimal when ka 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.