Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs

Yusheng Xie, Zhengzhang Chen, Lu Liu, Ankit Agrawal, Alok Nidhi Choudhary

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We investigate sampling techniques in unbalanced heterogeneous bipartite graphs (UHBGs), which have wide applications 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.

Original languageEnglish (US)
Title of host publicationCIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management
Pages1473-1476
Number of pages4
DOIs
StatePublished - Dec 11 2013
Event22nd ACM International Conference on Information and Knowledge Management, CIKM 2013 - San Francisco, CA, United States
Duration: Oct 27 2013Nov 1 2013

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Other

Other22nd ACM International Conference on Information and Knowledge Management, CIKM 2013
CountryUnited States
CitySan Francisco, CA
Period10/27/1311/1/13

Keywords

  • Heterogeneous bipartite graphs
  • Network sampling
  • Random walk
  • Social networks

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint Dive into the research topics of 'Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs'. Together they form a unique fingerprint.

  • Cite this

    Xie, Y., Chen, Z., Liu, L., Agrawal, A., & Choudhary, A. N. (2013). Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs. In CIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (pp. 1473-1476). (International Conference on Information and Knowledge Management, Proceedings). https://doi.org/10.1145/2505515.2507822