Towards Unbiased BFS Sampling

A large body of work in the networking community focuses on Internet topology measurements at various levels, including the IP or AS connectivity, the Web (WWW), Peer-To-Peer (P2P) and Online Social Networks (OSN). The size of these networks and other restrictions often make measuring the entire graph impossible. For example, learning only the topology of Facebook social graph would require downloading more than 115TB of HTML data, which is impractical. Instead, researchers typically collect and study a small but representative sample of the graph of interest. In this paper, the authors are particularly interested in sampling networks that naturally allow to explore the neighbors of a given node, as it is the case in WWW, P2P and OSN.