Social Graph Restoration via Random Walk Sampling
arXiv:2111.11966
Abstract
Analyzing social graphs with limited data access is challenging for third-party researchers. To address this challenge, a number of algorithms that estimate structural properties via a random walk have been developed. However, most existing algorithms are limited to the estimation of local structural properties. Here we propose a method for restoring the original social graph from the small sample obtained by a random walk. The proposed method generates a graph that preserves the estimates of local structural properties and the structure of the subgraph sampled by a random walk. We compare the proposed method with subgraph sampling using a crawling method and the existing method for generating a graph that structurally resembles the original graph via a random walk. Our experimental results show that the proposed method more accurately reproduces the local and global structural properties on average and the visual representation of the original graph than the compared methods. We expect that our method will lead to exhaustive analyses of social graphs with limited data access.
arXiv comment17 pages, 4 figures, 5 tables. To appear in 38th IEEE International Conference on Data Engineering (IEEE ICDE 2022)
References in corpus (10)
- Random graphs with arbitrary degree distributions and their applications
- Kronecker Graphs: An Approach to Modeling Networks
- Social Structure of Facebook Networks
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
- Statistical properties of sampled networks
- Modeling social networks from sampled data
- Crawling Facebook for Social Network Analysis Purposes
- Quantifying randomness in real networks
- NetGAN: Generating Graphs via Random Walks
- Random Graphs with Prescribed -Core Sequences: A New Null Model for Network Analysis