  This paper provides the first analysis of the differentially private
computation of three centrality measures, namely eigenvector, Laplacian and
closeness centralities, on arbitrary weighted graphs, using the smooth
sensitivity approach. We do so by finding lower bounds on the amounts of noise
that a randomised algorithm needs to add in order to make the output of each
measure differentially private. Our results indicate that these computations
are either infeasible, in the sense that there are large families of graphs for
which smooth sensitivity is unbounded; or impractical, in the sense that even
for the cases where smooth sensitivity is bounded, the required amounts of
noise result in unacceptably large utility losses.
