Answers are grounded in this paper and cite their sources.
Given a social network G , a cost associated with each user, and an influence threshold η, the minimum cost seed selection problem (MCSS) aims to find a set of seeds that minimizes the total cost to reach η users. Existing works are mainly devoted to providing an expected coverage guarantee on reaching η, classified as MCSS-ECG, where their solutions either rely on an impractical influence oracle or cannot attain the expected influence threshold. More importantly, due to the expected coverage guarantee, the actual influence in a campaign may drift from the threshold evidently. Thus, the advertisers would like to request for a probability guarantee of reaching η. This motivates us to further solve the MCSS problem with a probabilistic coverage guarantee, termed MCSS-PCG. In this paper, we first propose our algorithm CLEAR to solve MCSS-ECG, which reaches the expected influence threshold without any influence oracle or influence shortfall but a practical approximation ratio. However, the ratio involves an unknown term (i.e., the optimal cost). Thus, we further devise the STAR method to derive a lower bound of the optimal cost and then obtain the first explicit approximation ratio for MCSS-ECG. In MCSS-PCG, it is necessary to estimate the probability that the current seeds reach η, to decide when to stop seed selection. To achieve this, we design a new technique named MRR, which provides efficient probability estimation with a theoretical guarantee. With MRR in hand, we propose our algorithm SCORE for MCSS-PCG, whose performance guarantee is derived by measuring the gap between MCSS-ECG and MCSS-PCG, and applying the theoretical results in MCSS-ECG. Finally, extensive experiments demonstrate that our algorithms achieve up to two orders of magnitude speed-up compared to alternatives while meeting the requirement of MCSS-PCG with the smallest cost.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: