Influential spreaders identification in complex networks with improved k-shell hybrid method

Abstract

Identifying influential spreaders in a complex network has practical and theoretical significance. In appli- cations such as disease spreading, virus infection in computer networks, viral marketing, immunization, rumor containment, among others, the main strategy is to identify the influential nodes in the network. Hence many different centrality measures evolved to identify central nodes in a complex network. The degree centrality is the most simple and easy to compute whereas closeness and betweenness central- ity are complex and more time-consuming. The k-shell centrality has the problem of placing too many nodes in a single shell. Over the time many improvements over k-shell have been proposed with pros and cons. The k-shell hybrid ( ksh ) method has been recently proposed with promising results but with a free parameter that is set empirically which may cause some constraints to the performance of the method. This paper presents an improvement of the ksh method by providing a mathematical model for the free parameter based on standard network parameters. Experiments on real and artificially generated networks show that the proposed method outperforms the ksh method and most of the state-of-the-art node indexing methods. It has a better performance in terms of ranking performance as measured by the Kendall’s rank correlation, and in terms of ranking efficiency as measured by the monotonicity value. Due to the absence of any empirically set free parameter, no time-consuming preprocessing is required for optimal parameter value selection prior to actual ranking of nodes in a large network.