We consider the accuracy of the approximated centrality scores both in terms of absolute error and, more importantly, the preservation of the ranking order of nodes.
Our incremental algorithm has exactly the same accuracy as RK.
The authors of [1]} study the behavior of the algorithm also experimentally, considering the average and maximum estimation error on a small set of real graphs.
We study the absolute and relative errors (i. e. ratio between the approximated and the exact score) on a wider set of graphs. For our experiments we use PGPgiantcompo, as-22july06 and Dorogovtsev-Mendes graphs of several sizes. Our results confirm those of [1]} in the sense that the measured absolute errors are always below the guaranteed maximum error \(\epsilon \)  and the measured average error is orders of magnitude smaller than \(\epsilon \) . We observe that the relative error is almost constant among the different ranks and increases for high values of \(\epsilon \) .
We also study the relative rank error introduced by Geisberger et al.  [3]} (i. e. \(\max \lbrace \rho , 1/\rho \rbrace \) , denoting \(\rho \)  the ratio between the estimated rank and the
true rank), which we consider the most relevant measure of the quality of the approximations. Figure REF  shows the results for PGPgiantcompo, a similar trend can be observed on our other test instances as well. On the left, we see the errors for the whole set of nodes (ordered by exact rank) and, on the right, we focus on the top 100 nodes. The plot show that for a small value of \(\epsilon \)  (0.01), the ranking is very well preserved over all the positions. With higher values of \(\epsilon \) , the rank error of the nodes with low betweenness increases, as they are harder to approximate. However, the error remains small for the nodes with highest betweenness, the most important ones for many applications.
<FIGURE>