## 5 Sampling
### Hybrid Algorithm  
From Figures 4,5 we can conclude that the exact approach is able to quickly derive the more extreme values of the eccentricity distribution, whereas a sampling technique is able to approximate the values in between the extremes with a very low error. Therefore we propose to combine the two approaches in order to quickly converge to an accurate estimation of the eccentricity distribution using a _hybrid_ approach. This technique assumes that the eccentricity distribution has a somewhat unimodal shape, which is the case for all real-world graphs that we have investigated.  
The _sampling window_ consists of bounding variables \(\ell\) and \(r\) that denote between which eccentricity values the algorithm is going to use the sampling technique. This window obviously depends on the distribution itself, which is not known until the exact algorithm has finished. Therefore we propose to set the value of \(\ell\) and \(r\) dynamically, _i.e._, \(\ell=\min_{v\in V}\varepsilon_{L}[v]\) and \(r=\max_{v\in V}\varepsilon_{U}[v]\). We furthermore change the stopping criterion in line 9 of Algorithm 2 to **\"while**\(|\{w\in W\mid\varepsilon_{L}[w]=\ell\text{ or }\varepsilon_{U}[w]=r\}|>0\)**do**\".  
Figure 5: Relative standard deviation (vertical axis) _vs_. eccentricity value (horizontal axis) for different random sample sizes of the Enron dataset.  
This means that the algorithm should stop when there are no more candidates that are potentially part of the center or the periphery of the graph. Note that these bounds apply to the candidate set \(W\), but use information about all nodes \(V\), ensuring that at least the center and periphery are known before the exact phase is terminated. When the exact algorithm has done its job, it can tighten \(\ell\) and \(r\) even further, based on the eccentricity of the remaining candidate nodes: \(\ell=\min_{v\in W}\varepsilon_{L}[v]-1\) and \(r=\max_{v\in W}\varepsilon_{U}[v]+1\). After this, \(\ell\) and \(r\) become static, and the rest of the eccentricity distribution will be derived by using the sampling approach outlined in Algorithm 3. We will refer to the adjusted version of Algorithm 2 as BoundingEccentricitiesLR.  
```
1:Input: Graph \(G(V,E)\) and sampling rate \(q\)
2:Output: Vector \(f\), containing the eccentricity distribution of \(G\), initialized to \(0\)
3:\(\varepsilon^{\prime}\leftarrow\text{BoundingEccentricitiesLR}(G,\ell,r)\)
4:\(Z\leftarrow\emptyset\)
5:for\(v\in V\)do
6:if\(\varepsilon^{\prime}[v]\
eq 0\)and\((\varepsilon^{\prime}[v]\leq\ell\)or\(\varepsilon^{\prime}[v]\geq r)\)then
7:\(f[\varepsilon^{\prime}[v]]\gets f[\varepsilon^{\prime}[v]]+1\)
8:else
9:\(Z\gets Z\cup\{v\}\)
10:endif
11:endfor
12:for\(i\gets 1\)to\(n\cdot q\)do
13:\(v\leftarrow\text{RandomFrom}(Z)\)
14:\(\varepsilon[v]\leftarrow\text{Eccentricity}(v)\)
15:\(f[\varepsilon[v]]\gets f[\varepsilon[v]]+(1/q)\)
16:\(Z\gets Z-\{v\}\)
17:endfor
18:return\(f\)
```  
**Algorithm 3** HybridEccentricities  
Compared to Algorithm 2, the difference in terms of input is that the hybrid algorithm given in Algorithm 3 takes as input both the original graph and a sampling rate \(q\) between \(0\) and \(1\), where \(q=0.10\) means that \(10\%\) of the nodes have to be sampled. In Section 6 we will perform experiments to determine how \(q\) should be set. The result vector \(f\) holds the eccentricity distribution and is initialized based on the exact eccentricity values \(\varepsilon^{\prime}\) for values outside the sampling window (line 7). Nodes for which the exact eccentricity is not yet known are added to the candidate set \(Z\) (line 9). In lines 12-17, the eccentricity of a total of \(n\cdot q\) random nodes are calculated, and if this value lies within the specified window, the frequency of this eccentricity value is increased proportionally to the sample size. Finally, the eccentricity distribution \(f\) is returned.