# Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
## 5 Experimental Evaluation
### Comparing to the Literature  
In order to compare the Spikyball approach to the methods presented in the literature, we investigate their quality as graph sampling methods. We first focus on the degree distribution of the sampled graphs. Using the open-source graph sampling toolbox [19], we compare our main Spikyball variants, to the Snowball, Forest Fire, CNRW and CNARW and Metropolis-Hasting sampling implemented therein. The results of sampling random networks are shown in Figure 2 and on a real network in Figure 4. The real network is a part of the Facebook graph, provided in the toolbox [20]. There is a general decrease in the number of nodes for each degree value, which is of course due to the fact that we subsample the network (to 10% of its original size). As explained in Section 3, the Fireball and Forest Fire give similar results as their random exploration is almost identical. Both methods are close to the Snowball sampling distribution. As expected, the Coreball 2, tends to collect more high degree nodes than the other methods. This is more pronounced in the real network case. On random networks, the pink curve is below the others for degrees smaller than 5 and slightly above beyond this value. The Metropolis Hasting method, which does not belong to the same sampling family, collects more low degree nodes. It is the closest to the shape of the initial graph distribution for the real network and the Erdos-Renyi one. However, it is one of the worst for the Barabasi-Albert one with a steeper slope. All methods have difficulties to capture nodes with extreme degrees (too small or too large). In order to further compare the different graph exploration methods, several metrics have been computed, using different real-world datasets taken from [19; 21]. The main characteristics of those datasets have been summarized in Table 1. Each graph has been sampled to get 10% of its nodes (and 20% for the networks having less than 50 k nodes). For each sampled graph, its degree distribution is compared to the original one using the Kolmogorov-Smirnov (KS) test, in Table 2. In order to better exhibit the behavior on high-degree nodes, the KS test is also performed on a partial degree distribution, for degrees higher than the mean degree in the original graph. Other parameters, namely, the average clustering coefficient relative error, transitivity ratio relative error, average PageRank fraction from the original graph, sampled edges ratio and density, are compared in Tables 3-6. On these tables, Coreball refers to Coreball 2 and  
Figure 4: Degree distribution (**left**) and density (**right**) of the collected nodes on the Facebook graph. The sampling reduces the graph to 20% of its original size. The curve corresponding to the initial graph is in cyan. \begin{table}
\begin{tabular}{l r r} \hline \hline  & \(|V|\) & \(|E|\) \\ \hline Facebook [20] & 22 k & 171 k \\ Github [20] & 37.7 k & 289 k \\ Google+ [21] & 202 k & 1.13 M \\ Youtube [21] & 495 k & 1.93 M \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Datasets used in numerical experiments. Only the largest connected component has been kept in case of a disconnected graph.