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

Abedelaziz Mohaisen, Pengkui Luo, Yanhua Li, Yongdae Kim, Zhi Li Zhang

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

9 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationMILCOM 2012 - 2012 IEEE Military Communications Conference
StatePublished - 2012
Event2012 IEEE Military Communications Conference, MILCOM 2012 - Orlando, FL, United States
Duration: Nov 1 2012Nov 1 2012

Publication series

NameProceedings - IEEE Military Communications Conference MILCOM


Other2012 IEEE Military Communications Conference, MILCOM 2012
Country/TerritoryUnited States
CityOrlando, FL


  • Biased estimation
  • Mixing Time
  • Sampling
  • Social graphs


Dive into the research topics of 'Measuring bias in the mixing time of social graphs due to graph sampling'. Together they form a unique fingerprint.

Cite this