Information Spread Maximization With Multi-Boosting Stages
Lists
Only you see this
Abstract
Most of the existing works for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Influence Maximization (IM)</i> are defined over a ground set. As the natural extension of set space, in recent years, some works have begun to consider <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">IM</i> on lattice space. The lattice boosting problem, however, has not yet been considered. In this paper, we focus on <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Lattice <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Boosting Problem</i> . 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 generate <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Potentially Reverse-Reachable graph (PRR graph)</i> and propose a boosting parameter of each boosting edge to amend it. Additionally, it is an unbiased estimation of boosting influence. Because <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Lattice <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Boosting Problem</i> is not diminishing returns submodular (DR-submodular), we simplify <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Sandwich Approach</i> to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Semi-Sandwich Approach</i> by finding a tight DR-submodular lower bound, which also keeps a data-driven approximation ratio. Besides, we design a heuristic algorithm, namely <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ktop Algorithm</i> , 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.
BibTeX
@article{chen2022information,
author = {Shengminjie Chen and Yapu Zhang and Wenguo Yang and Ruiqi Yang},
title = {{Information Spread Maximization With Multi-Boosting Stages}},
journal = {IEEE Transactions on Network Science and Engineering},
year = {2022},
doi = {10.1109/tnse.2022.3185047},
}Loading related content...