Empirical characterization of graph sampling algorithms

The article delves into the challenges and solutions of analyzing large complex networks through graph sampling. It introduces the concept of graph sampling and its importance in preserving the properties of large graphs. The study focuses on five state-of-the-art sampling algorithms, including Frontier Sampling, Expansion Sampling, Rank Degree, List Sampling, and Hybrid Jump, and evaluates their performance on fifteen real-world and synthetic datasets. The authors analyze how well these algorithms preserve six key properties of graphs: degree, clustering coefficient, path length, global clustering coefficient, assortativity, and modularity. The evaluation metrics include point statistics, distributions, and error measures like Root Mean Square Error (RMSE) and Jensen–Shannon Distance (JSD). The results reveal the strengths and limitations of each sampling method, providing valuable insights into the design of future sampling algorithms. The study concludes with a summary of the findings and suggestions for future research directions in graph sampling.