Measuring bias in the mixing time of social graphs due to graph sampling

Sampling of large social graphs is used for addressing infeasibility of measurements in large social graphs, or for crawling graphs from online social network services where accessing an entire social graph at once is often impossible. Sampling algorithms aim at maintaining certain properties of the...

Full description

Saved in:
Bibliographic Details
Main Authors: Mohaisen, A., Pengkui Luo, Yanhua Li, Yongdae Kim, Zhi-Li Zhang
Format: Conference Proceeding
Language:English
Subjects:
Area measurement
Biased estimation
Estimation
Facebook
Mixing Time
Sampling
Social graphs
Time measurement
YouTube
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Sampling of large social graphs is used for addressing infeasibility of measurements in large social graphs, or for crawling graphs from online social network services where accessing an entire social graph at once is often impossible. Sampling algorithms aim at maintaining certain properties of the original graphs in the sampled (or crawled) ones. Several sampling algorithms, such as breadth-first search, standard random walk, and Metropolis-Hastings random walk, among others, are widely used in the literature for sampling graphs. Some of these sampling algorithms are known for their bias, mainly towards high degree nodes, while bias for other metrics is not well-studied. In this paper we consider the bias of sampling algorithms on the mixing time. We quantitatively show that some existing sampling algorithms, even those which are unbiased to the degree distribution, always produce biased estimation of the mixing time of social graphs. We argue that bias in sampling algorithms accepted in the literature is rather metric-dependent, and a given sampling algorithm, while may work nicely and unbiased to one property, may produce considerable amount of bias in other properties.
ISSN:2155-7578
2155-7586
DOI:10.1109/MILCOM.2012.6415714