## 5 Sampling
### Random Node Selection  
If we want to apply sampling to the naive algorithm for obtaining the eccentricity distribution, we could choose to evaluate only a subset of size \(n^{\prime}\) of the original \(n\) nodes, and multiply the values of the sampled eccentricity distribution by a factor \(n/n^{\prime}\) to get an idea of the real eccentricity distribution, a process referred to as _random node selection_. Indeed, taking only a subset of the nodes would clearly speed up the computation of the eccentricity distribution and realize the second type of speedup discussed in Section 4. The trade-off here is that we no longer obtain the exact eccentricity distribution, but only get an approximation. The main question is then whether or not this approximation is representative of the original distribution. The effectiveness of sampling by random node selection with respect to various graph properties has been demonstrated in [19]. Using similar arguments as presented in [20,21], the absolute error can be assessed; indeed, when the chosen sampling subset is sufficiently large, the error is effectively bounded.  
However, there are situations where we are not interested in minimizing the absolute error, but in minimizing the relative standard deviation (_i.e._, the absolute standard deviation divided by the mean) of the distribution of a particular eccentricity value. This especially makes sense when each eccentricity value is of equal importance, which might be the case when the extreme values of the distribution that are realizing the radius and diameter are of relevance. Let us consider an example. The real exact eccentricity distribution over all nodes in the Enron dataset [22] is as follows:  
\begin{tabular}{c|c|c|c|c|c|c|c} \(\varepsilon(v)\) & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline \(f(\varepsilon(v))\) & 24 & 12 210 & 17 051 & 3 647 & 485 & 44 & 11 \\ \end{tabular}  
Figure 5 shows the relative standard deviation for each eccentricity value for different sample sizes (\(1\%\), \(2\%\), \(5\%\), \(10\%\), and \(20\%\)). For each sample size, we took 100 random samples to average the result. We note that low relative standard deviations can be observed for the more common eccentricity values (in this case, 8, 9 and 10). However, the standard deviation is quite large for the extreme values, meaning that on many occasions, the sample did not correctly reflect the frequency of that particular eccentricity value. Indeed, if only 11 out of 33,696 nodes (\(0.03\%\)) have a particular eccentricity value (in this case, a value of 13), we need a sample size of at least \(100\%/11=9\%\) if we want to expect just one node with that particular eccentricity value. Even with a large sample size of \(20\%\), the standard deviation for the extreme value of 13 is very high (\(0.63\)). For sample sizes of \(1\%\) or \(2\%\), the eccentricity value of 13, that exists in the real distribution, was never even found. Similar events were observed for our other datasets, which is not surprising: the eccentricity distributions are tailed on the extremes, and these tails are likely to be left out in a sample. So clearly sampling does not suffice when extreme values of the eccentricity distribution have to be found, because such extreme values are simply too rare. However, for the more common eccentricity values, errors are very low, even for small sample sizes.