We investigate sampling techniques in unbalanced heterogeneous bipartite graphs (UHBGs), which have wide applica- tions in real world web-scale social networks. We propose random walked-based link sampling and stratified sampling for UHBGs and show that they have advantages over generic random walk samplers. In addition, each sampler's node degree distribution parameter estimator statistic is analytically derived to be used as a quality indicator. In the experiments, we apply the two sampling techniques, with a baseline node sampling method, to both synthetic and real Facebook data. The experimental results show that random walk-based stratified sampler has significant advantage over node sampler and link sampler on UHBGs.
22nd ACM CIKM 2013Yusheng Xie, Zhengzhang Chen, Lu Liu, Ankit Agrawal, and Alok Choudhary. Sampling From Unbalanced Heterogeneous Bipartite Social Graph
