Information Spread Maximization With Multi-Boosting Stages
Shengminjie Chen, Yapu Zhang, Wenguo Yang, Ruiqi Yang · IEEE Transactions on Network Science and Engineering · 2022
Most of the existing works forInfluence Maximization (IM)are defined over a ground set. As the natural extension of set space, in recent years, some works have begun to considerIMon lattice space. The lattice boosting problem, however, has not yet been considered. In this paper, we focus onLattice$k$-Boosting Problem. Because each edge has multi-boosting stages, it is an obstacle to estimate the value of boosting influence function by conventional sampling technique. To overcome this obstacle, we adopt the largest boosting probability of each edge to generatePotentially Reverse-Reachable graph (PRR graph)and propose a boosting parameter of each boosting edge to amend it. Additionally, it is an unbiased estimation of boosting influence. BecauseLattice$k$-Boosting Problemis not diminishing returns submodular (DR-submodular), we simplifySandwich ApproachtoSemi-Sandwich Approachby finding a tight DR-submodular lower bound, which also keeps a data-driven approximation ratio. Besides, we design a heuristic algorithm, namelyKtop Algorithm, to return a feasible solution of the original problem. Numerical experiments show that, under the same constraint, selecting each node with the stronger boosting power rather than many nodes may have large boosting influences.