2-hop+ Sampling: Efficient and Effective Influence Estimation

doi:10.1109/TKDE.2021.3093934

2-hop+ Sampling: Efficient and Effective Influence Estimation

2021-01-01

6

OA

AI

DOI：10.1109/TKDE.2021.3093934

Original

Original request for help

Save

Abstract

En 中文

rapidly growing sizes of online social networks, computational challenges arise in analyzing the diffusion process over networks. Sampling methods are commonly used to study the cascade effect and estimate users' influence. In this paper, we propose a brand-new sampling method, called 2-hop+ sampling for quickly and accurately estimating the cascade size generated by a set of seed users under the independent cascade model. Our method generates only samples with at least one 2-hop live path from the source to reduce the number of samples. We further enhance the sampling efficiency of our method by a SkipEdge technique. Moreover, we improve the generalized stopping rule algorithm to obtain an (e, d)-estimate of the mean of random variables with fewer samples needed. Extensive experiments with real-world datasets show that our techniques can significantly improve the estimation efficiency compared to the state-of-the-art methods.

Keywords:

Estimation

Integrated circuit modeling

Sampling methods

Social networking (online)

Random variables

Diffusion processes

Computational modeling

Online social networks

influence estimation

sampling

2-hop+ Sampling: Efficient and Effective Influence Estimation

Abstract

Journal

Organization