A connection-based analysis of networks using the position value: a computational approach

Abstract

In this paper, we introduce the position value as a centrality measure to evaluate the relevance of the edges and players in a network, with the additional advantage that this value integrates the degree measure of each player in it. In fact, in the real world, it is particularly important to consider the natural influence of connections of a player in a network. Its applications were very limited in real-world situations due to the high computational complexity of exactly obtaining this value. With the aim of solving this problem we provide a method, based on sampling theory, to estimate the position value, which is analyzed in terms of the theoretical properties of the resulting estimator. Moreover, we establish specific statistical results for bounding the absolute error in this approximation. It is important to emphasize that this approach allows for obtaining rankings not only of the nodes but also of the edges of the network. To illustrate the advantages and interest of the proposed methodology, as well as the variety of problems that can be analyzed in this framework, we applied it in three very different settings, the suburban train network of Madrid in the year 2000, the Spanish national team in a match against Portugal, and the Zerkani network responsible for the terrorist attacks of Paris (2015) and Brussels (2016).