Journal Article Ranking influential spreaders is an ill-defined problem

Gu, Jain  ,  Lee, Sungmin  ,  Saramaki, Jari  ,  HOLME, PETTER  ,  Holme, Petter

Finding influential spreaders of information and disease in networks is an important theoretical problem, and one of considerable recent interest. It has been almost exclusively formulated as a node-ranking problem —methods for identifying influential spreaders output a ranking of the nodes. In this work, we show that such a greedy heuristic does not necessarily work: the set of most influential nodes depends on the number of nodes in the set. Therefore, the set of n most important nodes to vaccinate does not need to have any node in common with the set of n + 1 most important nodes. We propose a method for quantifying the extent and impact of this phenomenon. By this method, we show that it is a common phenomenon in both empirical and model networks.

Number of accesses :  

Other information