On the robustness of centrality measures under conditions of imperfect data

An analysis is conducted on the robustness of measures of centrality in the face of random error in the network data. We use random networks of varying sizes and densities and subject them (separately) to four kinds of random error in varying amounts. The types of error are edge deletion, node deletion, edge addition, and node addition. The results show that the accuracy of centrality measures declines smoothly and predictably with the amount of error. This suggests that, for random networks and random error, we shall be able to construct confidence intervals around centrality scores. In addition, centrality measures were highly similar in their response to error. Dense networks were the most robust in the face of all kinds of error except edge deletion. For edge deletion, sparse networks were more accurately measured. (c) 2005 Published by Elsevier B.V.