# Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
## 5 Experimental Evaluation
### Comparing to the Literature
\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Sampling Method** & **Avg. Clustering Coef.** & **Transitivity Ratio** & **PageRank Ratio** & **Density** \\ \hline Metropolis-Hastings & 0.255 (72.46\%) & 0.312 (30.50\%) & 1.457 & \(6.74\times 10^{-4}\) \\ CNRW & 0.397 (168.32\%) & 0.308 (28.85\%) & 1.910 & \(2.71\times 10^{-3}\) \\ CNARW & 0.284 (92.07\%) & 0.303 (26.89\%) & 1.909 & \(2.37\times 10^{-3}\) \\ Forest fire & 0.317 (114.05\%) & 0.298 (24.65\%) & 1.859 & \(2.10\times 10^{-3}\) \\ \hline
**Fireball** & 0.346 (133.83\%) & 0.317 (32.72\%) & 1.839 & \(2.33\times 10^{-3}\) \\
**Edgeball** & 0.363 (145.33\%) & 0.264 (10.37\%) & 1.744 & \(3.06\times 10^{-3}\) \\
**Hubball** & 0.397 (168.16\%) & 0.264 (10.64\%) & 1.545 & \(2.79\times 10^{-3}\) \\
**Coreball** & 0.400 (170.69\%) & 0.296 (23.83\%) & 1.940 & \(3.23\times 10^{-3}\) \\ \hline Snowball & 0.360 (143.13\%) & 0.285 (19.50\%) & 1.576 & \(1.97\times 10^{-3}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Numerical results for the Google+ graph sampled at 10%. Full graph’s average clustering coefficient is 0.148, transitivity ratio is 0.238, density is \(5.57\times 10^{-5}\). Relative error for the average clustering coefficient and transitivity ratio is shown between parentheses. detection algorithm (we used Louvain in our experiments) is run on the initial graph. We then select the largest communities, in order to cover a sufficient fraction of the nodes (80% in our experiments). Let us denote by \(C=\{C_{0},C_{1},...\}\) the set of the selected communities and by \(d_{C_{k}}\) the sum of the degrees of all nodes belonging to the community \(C_{k}\). In the sampled graph, some of the nodes belonging to these communities might be present. We denote by \(C_{k}^{*}\) the sampled nodes belonging to \(C_{k}\), and by \(d_{C_{k}^{*}}\) the sum of the degrees (in the original graph) of nodes in \(C_{k}^{*}\). For each sampled graph, the IVIP score is:  
\[\frac{\sum_{k}d_{C_{k}^{*}}}{\sum_{k}d_{C_{k}}}.\]  
This metric will be higher if the high degree nodes of the large communities are sampled, which is the desired behavior when trying to find influencers in a social network. In order to ensure the stability of IVIP, we computed it for 10 different sampling runs (using different initial seeds) and averaged the results. The results are shown on Table 7.  
**Transitivity:** When a sampling scheme focuses on collecting more high degree nodes, there is a risk to get stuck in a single community, where these nodes are mostly connected to each other and not to outside communities. The experiments show that Spikyballs, as well as other sampling methods, do not have this behavior and explore more than one community (see IVIP score). This is confirmed by the values of the transitivity ratio in Table 4. Indeed, staying within a community would lead to more connections between nodes so more triangles and a higher transitivity ratio. The experiments show that the values for all sampling methods are close, and even the ones of the Spikyball are slightly smaller. **Pagerank ratio:** Concerning the pagerank measure, all samplings are increasing the values (ratio >1) of the initial graph. This is expected as it is difficult to collect weakly connected nodes (hence with low pagerank), at the periphery of the graph. We notice a higher value for the Coreball on all graphs. This confirms the fact that it collects more high degree nodes, more central, with high page rank. The other members of the Spikyball have diverse values, showing that the average pagerank of a sampled graph can be controlled by the Spikyball parameters. Coreball focuses on the central part of the network, while Hubball samples a more balanced proportion of central and peripheral nodes. **Density:** Coreball creates the network with the highest density, confirming again, its tendency to collect high degree nodes. The rest of the Spikyball family have values similar to Forest Fire, CNARW, and CNRW.