Ranking nodes in complex networks based on local structure and improving closeness centrality

摘要

In complex networks, the nodes with most spreading ability are called influential nodes. In many applications such as viral marketing, identification of most influential nodes and ranking them based on their spreading ability is of vital importance. Closeness centrality is one of the most commonly used methods to identify influential spreaders in social networks. However, this method is time-consuming for dynamic large-scale networks and has high computational complexity. In this paper, we propose a novel ranking algorithm which improves closeness centrality by taking advantage of local structure of nodes and aims to decrease the computational complexity. In our proposed method, at first, a community detection algorithm is applied to extract community structures of the network. Thereafter, after ignoring the relationship between communities, one best node as local critical node for each community is extracted according to any centrality measure. Then, with the consideration of interconnection links between communities, another best node as gateway node is found. Finally, the nodes are sorted and ranked based on computing the sum of the shortest path length of nodes to obtained critical nodes. Our method can detect the most spreader nodes with high diffusion ability and low time complexity, which make it appropriately applicable to large-scale networks. Experiments on synthetic and real-world connected networks under common diffusion models demonstrate the effectiveness of our proposed method in comparison with other methods. (C) 2018 Elsevier B.V. All rights reserved.