The sensitivity of networks to the removal of vertices has been studied extensively over the last 15 years. A common approach to measuring this sensitivity is (i) successively removing vertices following a specific removal strategy and (ii) comparing the original and the modified network using a specific comparison method. In this paper we apply a wide range of removal strategies and comparison methods in order to study the sensitivity of medium-sized networks from the real world and randomly generated networks. In the first part of our study we observe that social networks and web graphs differ in sensitivity. When removing vertices, social networks are robust, web graphs are not. This effect is consistent with the work of who analyzed very large social networks and web graphs. For randomly generated networks we find that their sensitivity depends significantly on the comparison method. The choice of removal strategy has surprisingly marginal impact on the sensitivity for removal strategies derived from common centrality measures. However, the removal strategy has a strong impact when removing the vertices in random order.
@cite_19: The ability to measure centrality in social networks has been a particularly useful development in social network analysis. For researchers trying to decide which centrality measure is most meaningful and valid for their research purposes, various papers have explored the conceptual foundations of centrality measures. Less well documented is the empirical performance of centrality measures under different research scenarios or constraints. This study uses bootstrap sampling procedures to determine how sampling affects the stability of 11 different network centrality measures. Results indicate that some measures are more stable than others, and that stability is also a function of network and study properties.
@cite_5: Abstract Although the concept of centrality has been well developed in the social networks literature, its empirical development has lagged somewhat. This paper moves a step in that direction by assessing the performance of four centrality models under a variety of known and controlled situations. It begins by examining the assumptions underlying each model, as well as its behavior in a community influence network. It then assesses the robustness and sensitivity of each model under conditions of random and systematic variation introduced into this network.
@cite_14: Abstract Research on measurement error in network data has typically focused on missing data. We embed missing data, which we term false negative nodes and edges, in a broader classification of error scenarios. This includes false positive nodes and edges and falsely aggregated and disaggregated nodes. We simulate these six measurement errors using an online social network and a publication citation network, reporting their effects on four node-level measures – degree centrality, clustering coefficient, network constraint, and eigenvector centrality. Our results suggest that in networks with more positively-skewed degree distributions and higher average clustering, these measures tend to be less resistant to most forms of measurement error. In addition, we argue that the sensitivity of a given measure to an error scenario depends on the idiosyncracies of the measure's calculation, thus revising the general claim from past research that the more ‘global’ a measure, the less resistant it is to measurement error. Finally, we anchor our discussion to commonly-used networks in past research that suffer from these different forms of measurement error and make recommendations for correction strategies.
@cite_25: An analysis is conducted on the robustness of measures of centrality in the face of random error in the network data. We use random networks of varying sizes and densities and subject them (separately) to four kinds of random error in varying amounts. The types of error are edge deletion, node deletion, edge addition, and node addition. The results show that the accuracy of centrality measures declines smoothly and predictably with the amount of error. This suggests that, for random networks and random error, we shall be able to construct confidence intervals around centrality scores. In addition, centrality measures were highly similar in their response to error. Dense networks were the most robust in the face of all kinds of error except edge deletion. For edge deletion, sparse networks were more accurately measured.
Modifying graphs and comparing the outcome with the respective source graph is a common approach to tackle a variety of questions. In the field of social network analysis, networks are modified in order to simulate measurement errors and to examine the robustness of centrality measures. An empirical network was altered by Bolland @cite_5 and Pearson correlation was used to measure the robustness. Random samples have been taken from empirical networks by Costenbader and Valente @cite_19 to investigate the stability of various centrality measures. Four error types have been applied to Erd o s-R 'enyi graphs by @cite_25 to measure centrality robustness regarding different types of accuracy measures. Six types of measurement errors have been applied to real-world and generated networks by @cite_14 in order to examine the robustness of node-level network measures by means of Spearman's rho.