Estimating Properties of Social Networks via Random Walk considering Private Nodes
Aug 13, 20209 views
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.