Variance reduction in large graph sampling

作者：

Highlights：

• We derive an upper bound for the variance of RE sampling.

• We show that variance of RN sampling grows with data size for scale-free networks.

• Thereby RE sampling excels when data size is large.

• We support the analytical results with simulation studies and 18 real networks.

摘要

•We derive an upper bound for the variance of RE sampling.•We show that variance of RN sampling grows with data size for scale-free networks.•Thereby RE sampling excels when data size is large.•We support the analytical results with simulation studies and 18 real networks.

论文关键词：Uniform random sampling,Random walk,Graph sampling,Online social network,Scale-free network,Harmonic mean

论文评审过程：Received 25 March 2013, Revised 7 January 2014, Accepted 11 February 2014, Available online 14 March 2014.

论文官网地址：https://doi.org/10.1016/j.ipm.2014.02.003