Random Walk Sampling in Social Networks Involving Private Nodes
arXiv:2305.12314 · doi:10.1145/3561388
Abstract
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.
arXiv comment27 pages, 10 figures, 3 tables
References in corpus (9)
- Emergence of scaling in random networks
- Error and attack tolerance of complex networks
- Resilience of the Internet to random breakdowns
- General state space Markov chains and MCMC algorithms
- Crawling Facebook for Social Network Analysis Purposes
- Respondent-driven sampling bias induced by clustering and community structure in social networks
- Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks
- A General Framework for Estimating Graphlet Statistics via Random Walk
- Estimating Properties of Social Networks via Random Walk considering Private Nodes