Abstract

Graph sampling provides an efficient way by selecting a representative subset of the original graph thus making the graph scale small for improved computations. Random walk graph sampling has been considered as a fundamental tool to collect uniform node samples from a large graph. In this paper, a comprehensive analysis and comparison of four existing sampling algorithms- BFS, NBRW-rw, MHRW and MHDA is presented. The comparison is shown on the basis of the performance of each algorithm on different kinds of datasets. Here, the considered parameters are node-degree distribution and clustering coefficient which effect the performance of an algorithm in generating unbiased samples. The sampling methods as in this study are analysed on the real-network datasets and finally the conclusion says that MHDA performs excellently whereas BFS gives a poor performance.

References

• D. Corlette and F. Shipman, “Capturing On-line Social Network Link Dynamics using Event-Driven Sampling, ” International Conference on Computational Science and Engineering, IEEE, 2009.
• T. Wang, Y. Chen, Z. Zhang, T. Xu, L. Jin, P. Hui, B. Deng, and X. Li, “Understanding Graph Sampling Algorithms for Social Network Analysis,” 31st International Conference on Distributed Computing Systems Workshops (ICDCSW), IEEE, 2011.
• C.-I. Wong, K.-Y. Wong, K.-W. Ng, W. Fan, and K.-H. Yeung, “Design of a Crawler for Online Social Network Analysis,” WSEAS TRANSACTIONS on COMMUNICATIONS, vol.13, 2014.
• M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, “Walking in Facebook: A Case Study of Unbiased Sampling of OSNs,” in proc. of the IEEE INFOCOM, 2010.
• M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, “Practical Recommendations on Crawling Online Social Networks,” IEEE Journal on Selected Areas in Communications, vol.29, Issue 9, October 2011.
• W. M. K. Trochim, “Sampling,” 2002, [Online],Available: http://trochim.human.cornell.edu/tutorial/mugo/tutorial.htm.
• M. Doherty, “Probability versus Non-Probability Sampling in Sample Surveys,” The New Zealand Statistics Review, pp. 21-28, March 1994.
• M. V. Gwetu, “The Application of Sampling to the Design of Structural Analysis Web Crawlers,” IJCSI, vol. 7, Issue 4, no. 8, July 2010.
• M. Kurant, A. Markopoulou, and P.Thiran, “On the Bias of Breadth First Search (BFS) and of Other Graph Sampling Techniques,” International Teletraffic Congress (ITC 22), 2010.
• L. Goodman, “Snowball Sampling,” Annals of Mathematical Statistics vol.32, pp.148-170, 1961.
• S. Dhawan, K. Singh, and K. Saini, “Comparing Crawling Techniques In Social Network,” IJIRS, vol.3, Issue 7, July 2014.
• C.-H. Lee, X. Xu, and D. Y. Eun, “Beyond Random Walk and Metropolis –Hastings Samplers: Why you should not Backtrack for Unbiased Graph Sampling,” SIGMETRICS, 2012.
• M. Strand, “Metropolis-Hastings Markov Chain Monte Carlo,” May 2009.
• R.-H. Li, J. X. Yu, L. Qin, R. Mao, and T. Jin, “On Random Walk Based Graph Sampling,” 31st International Conference on Data Engineering (ICDE), IEEE, 2015.
• D. Achlioptas, D. Kempe, A. Clauset, and C. Moore, “On the Bias of Traceroute Sampling or, Power-law Degree Distributions in Regular Graphs,” in proc. of the 37th ACM Symposium on Theory of Computing (STOC), May 2005.
• Stanford Large Network Dataset collection. http://snap.stanford.edu/data/index.html.