Graph Sampling by Exploration. Early crawling of P2P, OSN and WWW typically used graph traversals, mainly BFS [1]}, [2]}, [3]}, [4]}, [5]} and its variants.
However, incomplete BFS introduces bias towards high-degree nodes that is unknown and thus impossible to correct in general graphs  [6]}, [7]}, [8]}, [9]}, [10]}. Later studies followed a more principled approach based on random walks (RW) [11]}, [12]}. The Metropolis-Hasting RW (MHRW)  [13]}, [14]} removes the bias during the walk; it has been used to sample P2P networks [15]}, [16]} and OSNs [9]}.
Alternatively, we can use RW, whose bias is known and can be corrected for [18]}, [19]}, thus leading to a re-weighted RW [16]}, [9]}.
RW was also used to sample Web [22]},
P2P networks [15]}, [16]}, [25]}, OSNs [26]}, [27]}, [9]}, [5]}, and other large graphs [30]}.
It was empirically shown in [16]}, [9]} that RW outperforms MHRW in measurement accuracy. Therefore, RW can be considered as the state-of-the-art.
