Rank degree: an efficient algorithm for graph sampling

Abstract

The study of a large real world network in terms of graph sample representation constitutes a very powerful and useful tool in several domains of network analysis. This is the motivation that has led the work of this paper towards the development of a new graph sampling algorithm. Previous research in this area proposed simple processes such as the classic Random Walk algorithm, Random node and Random edge sampling and has evolved during the last decade to more advanced graph exploration approaches such as Forest Fire and Frontier sampling. In this paper, we propose a new graph sampling method based on edge selection. In addition, we crawled Facebook collecting a large dataset consisting of 10 million users and 80 million users' relations, which we have also used to evaluate our sampling algorithm. The experimental evaluation on several datasets proves that our approach preserves several properties of the initial graphs, leading to representative samples and outperforms all the other approaches.