On the impact of network size and average degree on the robustness of centrality measures
Research output: Journal contributions › Journal articles › Research › peer-review
Standard
In: Network Science, Vol. 9, No. S1, 20.10.2021, p. S61-S82.
Research output: Journal contributions › Journal articles › Research › peer-review
Harvard
APA
Vancouver
Bibtex
}
RIS
TY - JOUR
T1 - On the impact of network size and average degree on the robustness of centrality measures
AU - Martin, Christoph
AU - Niemeyer, Peter
N1 - Conference code: 8
PY - 2021/10/20
Y1 - 2021/10/20
N2 - Measurement errors are omnipresent in network data. Most studies observe an erroneous network instead of the desired error-free network. It is well known that such errors can have a severe impact on network metrics, especially on centrality measures: a central node in the observed network might be less central in the underlying, error-free network. The robustness is a common concept to measure these effects. Studies have shown that the robustness primarily depends on the centrality measure, the type of error (e.g., missing edges or missing nodes), and the network topology (e.g., tree-like, core-periphery). Previous findings regarding the influence of network size on the robustness are, however, inconclusive. We present empirical evidence and analytical arguments indicating that there exist arbitrary large robust and non-robust networks and that the average degree is well suited to explain the robustness. We demonstrate that networks with a higher average degree are often more robust. For the degree centrality and ErdÅ's-Rényi (ER) graphs, we present explicit formulas for the computation of the robustness, mainly based on the joint distribution of node degrees and degree changes which allow us to analyze the robustness for ER graphs with a constant average degree or increasing average degree.
AB - Measurement errors are omnipresent in network data. Most studies observe an erroneous network instead of the desired error-free network. It is well known that such errors can have a severe impact on network metrics, especially on centrality measures: a central node in the observed network might be less central in the underlying, error-free network. The robustness is a common concept to measure these effects. Studies have shown that the robustness primarily depends on the centrality measure, the type of error (e.g., missing edges or missing nodes), and the network topology (e.g., tree-like, core-periphery). Previous findings regarding the influence of network size on the robustness are, however, inconclusive. We present empirical evidence and analytical arguments indicating that there exist arbitrary large robust and non-robust networks and that the average degree is well suited to explain the robustness. We demonstrate that networks with a higher average degree are often more robust. For the degree centrality and ErdÅ's-Rényi (ER) graphs, we present explicit formulas for the computation of the robustness, mainly based on the joint distribution of node degrees and degree changes which allow us to analyze the robustness for ER graphs with a constant average degree or increasing average degree.
KW - Business informatics
KW - centrality measures
KW - measurement error
KW - missing data
KW - robustness
UR - http://www.scopus.com/inward/record.url?scp=85114751266&partnerID=8YFLogxK
U2 - 10.1017/nws.2020.37
DO - 10.1017/nws.2020.37
M3 - Journal articles
VL - 9
SP - S61-S82
JO - Network Science
JF - Network Science
SN - 2050-1242
IS - S1
T2 - International Conference on Complex Networks and their Applications - 2019
Y2 - 10 December 2019 through 12 December 2019
ER -