Iterative resource allocation for ranking spreaders in complex networks

¹ Research Center of Complex Systems Science, University of Shanghai for Science and Technology Shanghai 200093, PRC
² Department of Physics, University of Fribourg - Chemin du Musée 3, CH-1700 Fribourg, Switzerland
³ School of Systems Science, Beijing Normal University - Beijing 100875, PRC
⁴ Web Sciences Center, University of Electronic Science and Technology of China - Chengdu 611731, PRC

^(a) an.zeng@unifr.ch
^(b) liujg004@ustc.edu.cn

Received: 31 December 2013
Accepted: 29 April 2014

Abstract

Ranking the spreading influence of nodes in networks is a very important issue with wide applications in many different fields. Various topology-based centrality measures have been proposed to identify influential spreaders. However, the spreading influence of a node is usually not only determined by its own centrality but also largely influenced by the centrality of neighbors. To incorporate the centrality information of neighbors in ranking spreaders, we design an iterative resource allocation (IRA) process in which the resource of nodes distributes to their neighbors according to neighbors' centrality. After iterations, the resource amount on each node will be stable and the final resources of nodes are used to rank their spreading influence. The iterative process can be applied to many traditional centrality measures including degree, K-shell, closeness, and betweenness. The validation of our method is based on the susceptible-infected-recovered (SIR) spreading in four representative real datasets. The results show that the ranking accuracy of the traditional centrality measures is remarkably enhanced by IRA.