Robustness of Network Measures to Link Errors

Abstract

In various applications involving complex networks, network measures are employed to assess the relative importance of network nodes. However, the robustness of such measures in the presence of link inaccuracies has not been well characterized. Here we present two simple stochastic models of false and missing links and study the effect of link errors on three commonly used node centrality measures: degree centrality, betweenness centrality, and dynamical importance. We perform numerical simulations to assess robustness of these three centrality measures. We also develop an analytical theory, which we compare with our simulations, obtaining very good agreement.

9 pages, 9 figures

References in corpus (4)

• ARACNE: An Algorithm for the Reconstruction of Gene Regulatory Networks in a Mammalian Cellular Context
• Structure and tie strengths in mobile communication networks
• Missing and spurious interactions and the reconstruction of complex networks
• Characterizing the dynamical importance of network nodes and links

Cited by in corpus (8)

• Estimation of global network statistics from incomplete data
• Identifying significant edges via neighborhood information
• Estimating the sensitivity of centrality measures w.r.t. measurement errors
• Damage detection via shortest path network sampling
• A perturbation-based approach to identifying potentially superfluous network constituents
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• The Impact of Imperfect Information on Network Attack
• Probabilistic Network Metrics: Variational Bayesian Network Centrality