Paper Info
Title
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.
Year
DOI
Venue
2016
10.5555/3192424.3192447
ASONAM '16: Advances in Social Networks Analysis and Mining 2016 Davis California August, 2016
Keywords
Field
DocType
large real world network,graph sample representation,graph sampling algorithm,graph exploration,edge selection,Facebook
Data mining,Computer science,Random walk,Theoretical computer science,Artificial intelligence,Network completion,Network analysis,Graph,Algorithm design,Graph sampling,Algorithm,Sampling (statistics),Machine learning
Conference
ISBN
Citations 
PageRank 
978-1-5090-2846-7
4
0.38
References 
Authors
21
4
Name
Order
Citations
PageRank
Elli Voudigari191.49
Nikos Salamanos2102.54
Theodore Papageorgiou370.77
Emmanuel J. Yannakoudakis4183.25