Ranking influential spreaders is an ill-defined problem

Research output: Contribution to journalArticle


Research units

  • Sungkyunkwan University
  • Tokyo Institute of Technology


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.


Original languageEnglish
Article number68002
Pages (from-to)1-5
Issue number6
Publication statusPublished - 1 Jun 2017
MoE publication typeA1 Journal article-refereed

ID: 15307298