## 6 Experiments
### Hybrid Algorithm  
In our second set of experiments, we have evaluated the performance of the hybrid approach that incorporates sampling for the non-extreme values of the distribution (Algorithm 3). We will verify the quality of the obtained distribution by using the measure of _distribution accuracy_, defined as one minus the sum of the absolute difference between the eccentricity counts of real relative eccentricity distribution \(F(x)\) and the estimated distribution \(\hat{F}(x)\):  
\[\text{distribution accuracy}=1-\sum_{x=\Gamma(G)}^{\Delta(G)}|F(x)-\hat{F}(x)|\]  
A distribution accuracy value of \(1\) indicates a perfect match between the actual and estimated relative eccentricity distributions. We note that for our hybrid approach, the error outside the sampling window is always equal to \(0\). As a result of the exact approach, we have access to the real eccentricity distribution. Therefore we can investigate the number of iterations that are needed to obtain an accuracy of \(0.95\) in order to determine how we should set the sampling rate \(q\). The sixth column of Table 2 shows the number of iterations needed to (exactly) compute the extreme values (center and periphery), which together with the column titled \"Sampling\" (averaged over 10 runs) results in the value denoted in column \"Total\", which shows the total number of iterations needed to obtain an accuracy of \(0.95\). Apparently, for large graphs (over 100,000 nodes), a sampling rate of \(q=0.10\) is more than sufficient to accurately derive the \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Nodes**} & \multicolumn{3}{c}{**Exact algorithm**} & \multicolumn{3}{c}{**Hybrid algorithm**} \\  & & **Pruned** & **Iterations** & **Speedup** & **Exact** & **Sampling** & **Total** & **Speedup** \\ \hline yeast & 1 846 & 399 & 213 & **8.7** & 104 & 483 & 587 & 3.1 \\ CA-HepTh & 8 638 & 351 & 1 055 & 8.2 & 150 & 350 & 500 & **17.3** \\ CA-HepPh & 11 204 & 282 & 1 588 & 7.1 & 57 & 264 & 321 & **34.9** \\ dip20090126 & 19 928 & 3 032 & 224 & **89.0** & 8 & 1321 & 1 329 & 15.0 \\ ca-CondMat & 21 363 & 353 & 3 339 & 6.4 & 73 & 388 & 461 & **46.3** \\ cit-HepTh & 27 400 & 140 & 8 104 & 3.4 & 57 & 444 & 501 & **54.7** \\ Enron & 33 696 & 8 715 & 678 & **49.7** & 536 & 145 & 681 & 49.5 \\ cit-HepPh & 34 401 & 150 & 10 498 & 3.3 & 37 & 271 & 308 & **112** \\ slashdot & 51 083 & 19,255 & 31 & **1648** & 24 & 180 & 204 & 250 \\ p2p-Gnutella & 62 561 & 16 413 & 21 109 & 3.0 & 8 575 & 177 & 8 752 & **7.1** \\ facebook & 63 392 & 1 075 & 11 185 & 5.7 & 780 & 168 & 948 & **66.9** \\ epnions & 75 877 & 20 779 & 4302 & 17.6 & 1 308 & 75 & 1 383 & **54.9** \\ soc-slash & 82 168 & 14 848 & 1460 & 56.3 & 990 & 156 & 1 146 & **71.7** \\ ttdk0304-rilnks & 190 914 & 16 434 & 10 830 & 17.6 & 312 & 960 & 1 272 & **150** \\ web-Stanford & 255 265 & 10 350 & 9 & **28 363** & 8 & 1 198 & 1 206 & 212 \\ web-Notredame & 325 729 & 141,178 & 143 & 2277 & 94 & 1 381 & 1 475 & **4528** \\ dblp20080824 & 511 163 & 22 579 & 42 273 & 12.1 & 150 & 355 & 505 & **1012** \\ eu-2005 & 862 664 & 26 507 & 59 751 & 14.4 & 71 & 1 630 & 1 701 & **507** \\ flickr & 1 624 992 & 553 242 & 4 810 & 338 & 200 & 1 618 & 1 818 & **932** \\ as-Skitter & 1 694 616 & 114 803 & 42 996 & 39.4 & 14 & 308 & 322 & **5502** \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Performance (number of pruned nodes, number of iterations and speedup) of the exact algorithm (Algorithm 2) and the hybrid algorithm (Algorithm 3). eccentricity distribution. An alternative would be to change the number of samples to a constant number, which would ensure that the number of eccentricity calculations does not exceed some fixed maximum. An advantage of the exact approach is obviously that the nodes that have a certain eccentricity value can be pointed out exactly, whereas this is only possible for the extreme values in case of the hybrid approach.