Centrality measures in large and sparse networks

Abstract

The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these centrality measures to the sparse network, it is possible that the obtained set of central nodes will be similar to the set of central nodes in large networks. If these sets are similar, the centrality measures with a high computational complexity can be used for central nodes detection in large networks. To check the idea, several random networks were generated and different techniques of network reduction were considered. We also adapted some rules from social choice theory for the key nodes detection. As a result, we show how the initial network should be narrowed in order to apply centrality measures with a high computational complexity and maintain the set of key nodes of a large network.