Path diversity improves the identification of influential spreaders

¹ Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China - Xiyuan Avenue 2006, Chengdu 611731, PRC
² Department of Physics, University of Fribourg - Chemin du Musée 3, CH-1700 Fribourg, Switzerland

^(a) an.zeng@unifr.ch

Received: 31 May 2013
Accepted: 17 December 2013

Abstract

Identifying influential spreaders in complex networks is a crucial problem which relates to wide applications. Many methods based on the global information such as K-shell and PageRank have been applied to rank spreaders. However, most of the related previous works overwhelmingly focus on the number of paths for propagation, while whether the paths are diverse enough is usually overlooked. Generally, the spreading ability of a node might not be strong if its propagation depends on one or two paths while the other paths are dead ends. In this letter, we introduced the concept of path diversity and find that it can largely improve the ranking accuracy. We further propose a local method combining the information of path number and path diversity to identify influential nodes in complex networks. This method is shown to outperform many well-known methods in both undirected and directed networks. Moreover, the efficiency of our method makes it possible to apply it to very large systems.