# Random Walk Sampling in Social Networks Involving Private Nodes

arXiv: https://arxiv.org/abs/2305.12314 · HTML: https://mlsanity.com/paper/2305.12314/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2023.

## Built on by (most cited first, 1 of 1)

- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)

## Abstract (arXiv)

Analysis of social networks with limited data access is challenging for third parties. To address this challenge, a number of studies have developed algorithms that estimate properties of social networks via a simple random walk. However, most existing algorithms do not assume private nodes that do not publish their neighbors' data when they are queried in empirical social networks. Here we propose a practical framework for estimating properties via random walk-based sampling in social networks involving private nodes. First, we develop a sampling algorithm by extending a simple random walk to the case of social networks involving private nodes. Then, we propose estimators with reduced biases induced by private nodes for the network size, average degree, and density of the node label. Our results show that the proposed estimators reduce biases induced by private nodes in the existing estimators by up to 92.6% on social network datasets involving private nodes.