Influence of measurement errors on networks: Estimating the robustness of centrality measures

摘要

Most network studies rely on an observed network that differs from theunderlying network which is obfuscated by measurement errors. It is well knownthat such errors can have a severe impact on the reliability of networkmetrics, especially on centrality measures: a more central node in the observednetwork might be less central in the underlying network. We introduce a metric for the reliability of centrality measures -- calledsensitivity. Given two randomly chosen nodes, the sensitivity means theprobability that the more central node in the observed network is also morecentral in the underlying network. The sensitivity concept relies on theunderlying network which is usually not accessible. Therefore, we propose twomethods to approximate the sensitivity. The iterative method, which simulatespossible underlying networks for the estimation and the imputation method,which uses the sensitivity of the observed network for the estimation. Bothmethods rely on the observed network and assumptions about the underlying typeof measurement error (e.g., the percentage of missing edges or nodes). Our experiments on real-world networks and random graphs show that theiterative method performs well in many cases. In contrast, the imputationmethod does not yield useful estimations for networks other thanErdH{o}s-R'enyi graphs.