poster

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

Authors:

Lu LiuAuthors Info & Claims

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Pages 1473 - 1476

https://doi.org/10.1145/2505515.2507822

Published: 27 October 2013 Publication History

Get Access

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.

References

[1]

M. Gjoka, M. Kurant, C. Butts, and A. Markopoulou. Walking in facebook: A case study of unbiased sampling of osns. In INFOCOM, March 2010.

Digital Library

Google Scholar

[2]

J. Leskovec and C. Faloutsos. Sampling from large graphs. KDD '06, pages 631--636. ACM, 2006.

Digital Library

Google Scholar

[3]

L. Liu, J. Tang, J. Han, and S. Yang. Learning influence from heterogeneous social networks. Data Min. Knowl. Discov., 25(3):511--544, 2012.

Crossref

Google Scholar

[4]

L. Lovasz. Random walks on graphs: A survey, 1993.

Google Scholar

[5]

N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087--1092, 1953.

Crossref

Google Scholar

[6]

M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E, 64:026118, Jul 2001.

Crossref

Google Scholar

[7]

M. E. J. Newman, D. J. Watts, and S. H. Strogatz. Random graph models of social networks. PNAS, 99(Suppl 1):2566--2572, 2002.

Crossref

Google Scholar

[8]

Y. Xie, Z. Chen, K. Zhang, Y. Cheng, A. Agrawal, W. keng Liao, and A. Choudhary. Detecting and tracking disease outbreaks in real-time through social media. In IJCAI, 2013.

Digital Library

Google Scholar

[9]

K. Zhang, Z. Chen, Y. Cheng, Y. Xie, D. Downey, A. Agrawal, W. keng Liao, and A. Choudhary. A probabilistic graphical model for brand reputation assessment in social networks. In ASONAM '13, 2013.

Digital Library

Google Scholar

Cited By

View all

Mao YGupta VWang KLiao WChoudhary AAgrawal A(2022)To Shuffle or Not To Shuffle: Mini-Batch Shuffling Strategies for Multi-class Imbalanced Classification2022 International Conference on Computational Science and Computational Intelligence (CSCI)10.1109/CSCI58124.2022.00057(298-301)Online publication date: Dec-2022
https://doi.org/10.1109/CSCI58124.2022.00057
Luo CChen ZTang LShrivastava ALi ZChen HYe JGuo YFarooq F(2018)TINETProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3219819.3220003(1890-1899)Online publication date: 19-Jul-2018
https://dl.acm.org/doi/10.1145/3219819.3220003
Liu YJi SMittal PWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)SmartWalkProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978319(492-503)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978319
Show More Cited By

Index Terms

Random walk-based graphical sampling in unbalanced heterogeneous bipartite social graphs
1. Information systems
  1. Information retrieval

Recommendations

Weighted Jump in Random Walk graph sampling
Abstract
Graph sampling is a challenging problem in network analysis due to the complex structures of networks. Currently, a series of graph sampling algorithms based on random walks achieve good results in graph sampling tasks. However, the existing ...
Sampling online social networks by random walk with indirect jumps

Random walk-based sampling methods are gaining popularity and importance in characterizing large networks. While powerful, they suffer from the slow mixing problem when the graph is loosely connected, which results in poor estimation accuracy. Random ...
Network Sampling Using k-hop Random Walks for Heterogeneous Network Embedding
CODS-COMAD '19: Proceedings of the ACM India Joint International Conference on Data Science and Management of Data

Capturing neighborhood information by generating node sequences or node samples is an important prerequisite step for many of the neural network embedding approaches. Majority of the recent studies on neural network embedding exploit random walk as a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

October 2013

2612 pages

ISBN:9781450322638

DOI:10.1145/2505515

General Chairs:
Qi He
LinkedIn, USA
,
Arun Iyengar
IBM T.J. Watson Research Center, USA
,
Program Chairs:
Wolfgang Nejdl
L3S Research Center, Germany
,
Jian Pei
Simon Fraser University, Canada
,
Rajeev Rastogi
Amazon, India

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

CIKM'13

Sponsor:

CIKM'13: 22nd ACM International Conference on Information and Knowledge Management

October 27 - November 1, 2013

California, San Francisco, USA

Acceptance Rates

CIKM '13 Paper Acceptance Rate 143 of 848 submissions, 17%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
216
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mao YGupta VWang KLiao WChoudhary AAgrawal A(2022)To Shuffle or Not To Shuffle: Mini-Batch Shuffling Strategies for Multi-class Imbalanced Classification2022 International Conference on Computational Science and Computational Intelligence (CSCI)10.1109/CSCI58124.2022.00057(298-301)Online publication date: Dec-2022
https://doi.org/10.1109/CSCI58124.2022.00057
Luo CChen ZTang LShrivastava ALi ZChen HYe JGuo YFarooq F(2018)TINETProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3219819.3220003(1890-1899)Online publication date: 19-Jul-2018
https://dl.acm.org/doi/10.1145/3219819.3220003
Liu YJi SMittal PWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)SmartWalkProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978319(492-503)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978319
Xie YChen ZPalsetia DAgrawal AChoudhary AJia YRokne JWu XEster MXu G(2014)Indexing bipartite memberships in web graphsProceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.5555/3191835.3191868(166-173)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.5555/3191835.3191868
Xie YChen ZPalsetia DAgrawal AChoudhary A(2014)Indexing bipartite memberships in web graphs2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014)10.1109/ASONAM.2014.6921578(166-173)Online publication date: Aug-2014
https://doi.org/10.1109/ASONAM.2014.6921578

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Weighted Jump in Random Walk graph sampling

Sampling online social networks by random walk with indirect jumps

Network Sampling Using k-hop Random Walks for Heterogeneous Network Embedding