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

Yusheng Xie; Zhengzhang Chen; Lu Liu; Ankit Agrawal; Alok Choudhary

doi:10.1145/2505515.2507822

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

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

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 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 language	English (US)
Title of host publication	CIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management
Pages	1473-1476
Number of pages	4
DOIs	https://doi.org/10.1145/2505515.2507822
State	Published - 2013
Event	22nd ACM International Conference on Information and Knowledge Management, CIKM 2013 - San Francisco, CA, United States Duration: Oct 27 2013 → Nov 1 2013

Publication series

Name	International Conference on Information and Knowledge Management, Proceedings

Other

Other	22nd ACM International Conference on Information and Knowledge Management, CIKM 2013
Country/Territory	United States
City	San Francisco, CA
Period	10/27/13 → 11/1/13

Keywords

Heterogeneous bipartite graphs
Network sampling
Random walk
Social networks

ASJC Scopus subject areas

General Decision Sciences
General Business, Management and Accounting

Access to Document

10.1145/2505515.2507822

Cite this

Xie, Y., Chen, Z., Liu, L., Agrawal, A., & Choudhary, A. (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

@inproceedings{bcf00d45eb964d7cad6757e074bbdca6,

title = "Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs",

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.",

keywords = "Heterogeneous bipartite graphs, Network sampling, Random walk, Social networks",

author = "Yusheng Xie and Zhengzhang Chen and Lu Liu and Ankit Agrawal and Alok Choudhary",

year = "2013",

doi = "10.1145/2505515.2507822",

language = "English (US)",

isbn = "9781450322638",

series = "International Conference on Information and Knowledge Management, Proceedings",

pages = "1473--1476",

booktitle = "CIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management",

note = "22nd ACM International Conference on Information and Knowledge Management, CIKM 2013 ; Conference date: 27-10-2013 Through 01-11-2013",

}

Xie, Y, Chen, Z, Liu, L, Agrawal, A & Choudhary, A 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. International Conference on Information and Knowledge Management, Proceedings, pp. 1473-1476, 22nd ACM International Conference on Information and Knowledge Management, CIKM 2013, San Francisco, CA, United States, 10/27/13. https://doi.org/10.1145/2505515.2507822

Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs. / Xie, Yusheng; Chen, Zhengzhang; Liu, Lu et al.
CIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. 2013. p. 1473-1476 (International Conference on Information and Knowledge Management, Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Xie, Yusheng

AU - Chen, Zhengzhang

AU - Liu, Lu

AU - Agrawal, Ankit

AU - Choudhary, Alok

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Heterogeneous bipartite graphs

KW - Network sampling

KW - Random walk

KW - Social networks

UR - http://www.scopus.com/inward/record.url?scp=84889597086&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84889597086&partnerID=8YFLogxK

U2 - 10.1145/2505515.2507822

DO - 10.1145/2505515.2507822

M3 - Conference contribution

AN - SCOPUS:84889597086

SN - 9781450322638

T3 - International Conference on Information and Knowledge Management, Proceedings

SP - 1473

EP - 1476

BT - CIKM 2013 - Proceedings of the 22nd ACM International Conference on Information and Knowledge Management

T2 - 22nd ACM International Conference on Information and Knowledge Management, CIKM 2013

Y2 - 27 October 2013 through 1 November 2013

ER -

Xie Y, Chen Z, Liu L, Agrawal A , Choudhary A. 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. 2013. p. 1473-1476. (International Conference on Information and Knowledge Management, Proceedings). doi: 10.1145/2505515.2507822

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this