Análise de sensibilidade de técnicas de amostragem em grafos aleatórios

Abstract

In this work, we propose a sensitivity analysis of sampling methods for random graphs in order to find the best sampling strategy for each model analyzed. For best sampling strategy we mean the ability of a sampling method to preserve the characteristics of the graph, even under increasing loss of information. The following random graph models were used to capture different relational data structures: Erdös Rényi, Geometric, Barabasi Albert and Watts Strogatz. For each of these graph models we tested the following sampling methods: random vertex sampling, random edge sampling, and snowball sampling. Sampling graphs is a promising area and there are studies using individual topological measures to validate the sampling strategy. Our work differs from the others in proposing the use of a more robust synthetic information − the spectral density of the graph. In addition to being a synthetic measure, it preserves all the information contained in the graph, including the topological metrics individually used. We use the Kullback-Leibler Divergence between spectral density of the original graph and their sampled versions to validate its use and then, using spectral densities, we built a test from the Jensen Shannon test statistics to check if the loss of vertices or edges affects the identifiability of the original model. Our sampling approach yielded two main results. First, we found a lower limit of 500 vertices to guarantee the recovery of the original model, regardless of the sampling method or graph model used. Second, our approach allowed us to inform which sampling method is most appropriate for each observed graph.