Abstract

Awareness of online social networking sites is increasing day by day. This has made the topology of networks complex. Analyzing such networks is difficult when we take into consideration a large graph. For such analysis we use graph sampling techniques. These techniques extract a representative sample graph from the original graph and the obtained graph is taken into consideration for analysis. Usage of representative sample graph decreases the complexity of the graph and leads to easy computation. The results can then be generalized on the entire network. In this paper, we discuss various sampling techniques and infer that Metro-polis Hastings Random Walk (MHRW) is an efficient graph sampling algorithm.