  Accurately analyzing graph properties of social networks is a challenging
task because of access limitations to the graph data. To address this
challenge, several algorithms to obtain unbiased estimates of properties from
few samples via a random walk have been studied. However, existing algorithms
do not consider private nodes who hide their neighbors in real social networks,
leading to some practical problems. Here we design random walk-based algorithms
to accurately estimate properties without any problems caused by private nodes.
First, we design a random walk-based sampling algorithm that comprises the
neighbor selection to obtain samples having the Markov property and the
calculation of weights for each sample to correct the sampling bias. Further,
for two graph property estimators, we propose the weighting methods to reduce
not only the sampling bias but also estimation errors due to private nodes. The
proposed algorithms improve the estimation accuracy of the existing algorithms
by up to 92.6% on real-world datasets.
