论文标题
通过随机步行估算社交网络的属性，考虑私人节点
Estimating Properties of Social Networks via Random Walk considering Private Nodes
论文作者
论文摘要
准确分析社交网络的图形属性是一项具有挑战性的任务，因为访问图形数据的访问限制。为了应对这一挑战，已经研究了几种算法以通过随机散步从几个样品中获得无偏估计的估计。但是，现有的算法不考虑将邻居隐藏在实际社交网络中的私人节点，从而导致一些实际问题。在这里，我们设计了基于步行的算法以准确估算属性，而不会引起私人节点引起的任何问题。首先，我们设计了一种基于步行的采样算法，该算法包括邻居选择，以获取具有Markov属性的样品和每个样品的权重计算以纠正采样偏差。此外，对于两个图形属性估计器，我们提出了加权方法，不仅减少了采样偏差，而且还要减少由于私有节点引起的估计错误。所提出的算法在实际数据集上提高了现有算法的估计准确性高达92.6％。
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.
