TY - CHAP

T1 - An Empirical Study of the Effect of Noise Models on Centrality Metrics

AU - Sarkar, Soumya

AU - Karn, Abhishek

AU - Mukherjee, Animesh

AU - Bhowmick, Sanjukta

PY - 2019

Y1 - 2019

N2 - An important yet little studied problem in network analysis is the effect of the presence of errors in creating the networks. Errors can occur both due to the limitations of data collection techniques and the implicit bias during modeling the network. In both cases, they lead to changes in the network in the form of additional or missing edges, collectively termed as noise. Given that network analysis is used in many critical applications from criminal identification to targeted drug discovery, it is important to evaluate by how much the noise affects the analysis results. In this paper, we present an empirical study of how different types of noise affect real-world networks. Specifically, we apply four different noise models to a suite of nine networks, with different levels of perturbations to test how the ranking of the top-k centrality vertices changes. Our results show that deletion of edges has less effect on centrality than the addition of edges. Nevertheless, the stability of the ranking depends on all three parameters: the structure of the network, the type of noise model used, and the centrality metric to be computed. To the best of our knowledge, this is one of the first extensive studies to conduct both longitudinal (across different networks) and horizontal (across different noise models and centrality metrics) experiments to understand the effect of noise in network analysis.

AB - An important yet little studied problem in network analysis is the effect of the presence of errors in creating the networks. Errors can occur both due to the limitations of data collection techniques and the implicit bias during modeling the network. In both cases, they lead to changes in the network in the form of additional or missing edges, collectively termed as noise. Given that network analysis is used in many critical applications from criminal identification to targeted drug discovery, it is important to evaluate by how much the noise affects the analysis results. In this paper, we present an empirical study of how different types of noise affect real-world networks. Specifically, we apply four different noise models to a suite of nine networks, with different levels of perturbations to test how the ranking of the top-k centrality vertices changes. Our results show that deletion of edges has less effect on centrality than the addition of edges. Nevertheless, the stability of the ranking depends on all three parameters: the structure of the network, the type of noise model used, and the centrality metric to be computed. To the best of our knowledge, this is one of the first extensive studies to conduct both longitudinal (across different networks) and horizontal (across different noise models and centrality metrics) experiments to understand the effect of noise in network analysis.

KW - Accuracy of analysis

KW - Centrality metrics

KW - Noise models in networks

UR - http://www.scopus.com/inward/record.url?scp=85065828640&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065828640&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14683-2_1

DO - 10.1007/978-3-030-14683-2_1

M3 - Chapter

AN - SCOPUS:85065828640

T3 - Springer Proceedings in Complexity

SP - 3

EP - 21

BT - Springer Proceedings in Complexity

PB - Springer

ER -