||Ranking influential spreaders is an ill-defined problem
Ranking influential spreaders is an ill-defined problem
Gu, Jain ,
Lee, Sungmin ,
Saramaki, Jari ,
HOLME, PETTERHolme, Petter
EPL : europhysics letters
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.