Path diversity improves the identification of influential spreaders

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 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 be applied to very large systems.

6 pages, 6 figures

References in corpus (7)

• Leaders in Social Networks, the Delicious Case
• New Model of Internet Topology Using k-shell Decomposition
• Ranking spreaders by decomposing complex networks
• Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity
• A k-shell decomposition method for weighted networks
• Epidemic spreading on heterogeneous networks with identical infectivity
• Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach

Cited by in corpus (8)

• Epidemic processes in complex networks
• Identifying influential spreaders in complex networks based on gravity formula
• Searching for superspreaders of information in real-world social media
• Leveraging percolation theory to single out influential spreaders in networks
• Fast influencers in complex networks
• Top influencers can be identified universally by combining classical centralities
• Vulnerability of state-interdependent networks under malware spreading
• Predicting Item Popularity: Analysing Local Clustering Behaviour of Users