Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks

In recent years, notable number of research studies have been conducted on the analysis of diffusion process in complex networks. One fundamental problem in this domain is to find the most influential spreader nodes. For achieving a successful spreading process, nodes having high spreading ability should be selected as spreaders. Many centrality measures have been proposed for determining and ranking the significance of nodes and detecting the best spreaders. The majority of proposed centrality measures require network global information which leads to high time complexity. Moreover, with the advent of large-scale complex networks, there is a critical need for improving accurate measures through using nodes’ local information. On the other hand, most of the formerly proposed centrality measures have attempted to select core nodes as spreaders but global bridge nodes have the highest spreading ability since they are located among several giant communities of the network. In this study, a new local and parameter-free centrality measure is proposed which is aimed at finding global bridge nodes in the network. Hence, two new local metrics, namely edge ratio and neighborhood diversity, are firstly defined which are used in the proposed method. Considering edge ratio of neighbors ensures that the selected node be not in the periphery location of the network. Furthermore, a node with high neighborhood diversity is likely a connector between some modules (dense parts) of the network. Therefore, a node with a high edge ratio and more diverse neighborhood has high spreading ability. The major merits of the proposed measure are near-linear time complexity, using local information and being parameter-free. For evaluating the proposed method, we conducted experiments on real-world networks. The results of comparing the proposed centrality measure with other measures in terms of epidemic models (SIR and SI), Kendall’s tau correlation coefficient and Rank-Frequency measures indicated that the proposed method outperforms the other compared centrality measures.