Robustness of network measures to link errors

2013/09/18 by John Platig, Edward Ott, Ed Ott +1 · 32 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · Physics and Astronomy · #Betweenness centrality #Centrality #Complex Network Analysis Techniques #Complex network #Computer science #Data mining #Engineering #Graph theory and applications #Katz centrality #Mathematics #Network analysis #Network science #Network theory #Opinion Dynamics and Social Influence #Robustness (evolution) #Statistics #cond-mat.stat-mech #cs.SI #physics.soc-ph #q-bio.MN

paper · pdf · doi:10.1103/physreve.88.062812

published in Physical Review E 88(6), 062812 (American Physical Society) · 9 pages, 9 figures

arxiv created 2013/09/18 · openalex publication_date 2013/12/11 · arxiv updated 2014/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Missing and spurious interactions and the reconstruction of complex networks
• Emergence of scaling in random networks
• The effect of network topology on the stability of discrete state models of genetic control
• Error and attack tolerance of complex networks
• Controllability of complex networks
• ARACNE: An Algorithm for the Reconstruction of Gene Regulatory Networks in a Mammalian Cellular Context