Volume 118, Number 6, June 2017
|Number of page(s)||5|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||11 August 2017|
Ranking influential spreaders is an ill-defined problem
1 Department of Energy Science, Sungkyunkwan University - 440-746 Suwon, Republic of Korea
2 Department of Computer Science, Aalto University - FI-00076 Aalto, Finland
3 Institute of Innovative Research, Tokyo Institute of Technology - Tokyo, Japan
Received: 12 July 2017
Accepted: 27 July 2017
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.
PACS: 89.75.-k – Complex systems / 05.40.-a – Fluctuation phenomena, random processes, noise, and Brownian motion / 89.75.Fb – Structures and organization in complex systems
© EPLA, 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.