Towards Unbiased BFS Sampling
Kurant, Maciej; Markopoulou, Athina; Thiran, Patrick
2011

Abstract

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.

Details

Title Towards Unbiased BFS Sampling
Author(s) Kurant, Maciej ; Markopoulou, Athina ; Thiran, Patrick
Published in IEEE Journal on Selected Areas in Communications
Volume 29
Pages 1799-1809
Date 2011
Publisher Institute of Electrical and Electronics Engineers
ISSN 0733-8716
Keywords
DOI https://doi.org/10.1109/JSAC.2011.111005
Other identifier(s) View record in Web of Science
Laboratories LCA3
Record Appears in Scientific production and competences > I&C - School of Computer and Communication Sciences > IC Archives > LCA3 - Computer Communications and Applications Laboratory 3
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date 2011-12-16

Actions