Robustness of network measures to link errors

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.

Figure 1

Model 1: Contour map of correlation before and after introduction of link errors where $\delta$ is the fraction of missing links and $\alpha$ is the fraction of false links for Erdos-Renyi and scale-free networks. False links are added randomly (Model 1), missing links proportional to the original degree. True and noisy network measures are perfectly correlated when $\rho$ is 1 [cream (white)] and not correlated when $\rho$ is 0 [red (dark gray)].

Figure 2

Model 2: Contour map of correlation before and after introduction of link errors where $\delta$ is the fraction of missing links and $\alpha$ is the fraction of false links for Erdos-Renyi and scale-free networks. False and missing links are proportional to the original degree. True and noisy network measures are perfectly correlated when $\rho$ is 1 [cream (white)] and not correlated when $\rho$ is 0 [red (dark gray)].

Figure 3

The centrality correlation for the three measures studied: degree centrality [red (dark gray)], betweenness centrality [green (light gray)], and dynamical importance (black). Squares correspond to results in which noise is added according to Model 1, circles correspond to results in which noise is added according to Model 2. Panels (a) and (b) are for Erdos-Renyi truth networks, and panels (c) and (d) are for scale-free truth networks. In (a) and (c), the fraction of false edges is fixed at $\alpha =0.5$, and the fraction of true edges deleted, $\delta$ is varied. In (b) and (d), the fraction of true edges deleted is fixed at $\delta =0.5$ and the fraction of false edges added, $\alpha$, is varied.

Figure 4

Model 1: Contour map of the overlap between the top $10\%$ (250) nodes in the true network and the top $10\%$ in the noisy network as ranked by each node's centrality measure before and after introduction of link errors where $\delta$ is the fraction of missing links and $\alpha$ is the fraction of false links for Erdos-Renyi and scale-free networks. False links are added randomly, missing links proportional to the original degree.

Figure 5

Model 2: Contour map of the overlap between the top $10\%$ (250) nodes in the true network and the top $10\%$ in the noisy network as ranked by each node's centrality measure before and after introduction of link errors where $\delta$ is the fraction of missing links and $\alpha$ is the fraction of false links for Erdos-Renyi and scale-free networks. The number of false and missing links for each node is proportional to the original degree of that node.

Figure 6

Model 1: The first (lower black), second [red (light gray)], and third (upper black) quartiles for the ratio of noisy-true degree ($\tilde{D}$), betweenness ($\tilde{B}$), and dynamical importance ($\tilde{I}$) versus degree (k) in ER (left column) and SF (right column) networks for $\alpha =\delta =0.3$. The open circles are derived from the theory described in 4. Results are averaged over 500 realizations of the noise model with the same underlying true network.

Figure 7

Model 2: The first (lower black), second [red (light gray)], and third (upper black) quartiles for the ratio of noisy-true degree ($\tilde{D}$), betweenness ($\tilde{B}$), and dynamical importance ($\tilde{I}$) versus degree (k) in ER (left column) and SF (right column) networks for $\alpha =0.3$, $\delta =0.3$. The open circles are derived from the theory described in 4. Results are averaged over 500 independent realizations of the noise model with the same underlying true network.

Figure 8

Model 1: Pearson correlation between the true degree centrality $k$ and the noisy degree $n$ as a function of missing link fraction, $\delta$, and false link fraction, $\alpha$. Markers reflect simulation results and theoretical results are plotted as solid lines.

Figure 9

Model 2: Pearson correlation between the true degree centrality $k$ and the degree noisy $n$ as a function of missing link fraction, $\delta$, and false link fraction, $\alpha$. Markers reflect simulation results and theoretical results are plotted as solid lines.