Towards Unbiased BFS Sampling

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify and correct the degree bias of BFS.


Published in:
IEEE Journal on Selected Areas in Communications, 29, 1799-1809
Year:
2011
Publisher:
Institute of Electrical and Electronics Engineers
ISSN:
0733-8716
Keywords:
Laboratories:




 Record created 2011-12-16, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)