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.
Keywords: Breadth-First-Search (BFS) ; network topology ; sampling methods ; bias ; estimation ; online social networks ; Hidden Populations ; Finite Population ; Degree Sequence ; Replacement ; Networks ; Probabilities ; Graphs
Record created on 2011-12-16, modified on 2016-08-09