• PNAS Chemistry Ad
  • Science Sessions: The PNAS Podcast Program

Optimal deployment of resources for maximizing impact in spreading processes

  1. David Saadb
  1. aCenter for Nonlinear Studies and Theoretical Division T-4, Los Alamos National Laboratory, Los Alamos, NM 87545;
  2. bThe Nonlinearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom
  1. Edited by Giorgio Parisi, University of Rome, Rome, Italy, and approved July 24, 2017 (received for review September 1, 2016)

Significance

Spreading processes play an increasingly important role in marketing, opinion setting, and epidemic modeling. Most existing algorithms for optimal resource allocation in spreading processes are based on topological characteristics of the underlying network and aim to maximize impact at infinite time. Clearly, realistic and efficient real-time allocation policies should consider both network properties and details of the dynamics; additionally, control may be applied only to a restricted set of accessible nodes, and impact should be maximized in a limited time window. We introduce a probabilistic targeting framework that incorporates the dynamics and encompasses previously considered optimization formulations. It is based on a scalable dynamic message-passing approach that allows for the solution of large real-world network instances.

Abstract

The effective use of limited resources for controlling spreading processes on networks is of prime significance in diverse contexts, ranging from the identification of “influential spreaders” for maximizing information dissemination and targeted interventions in regulatory networks, to the development of mitigation policies for infectious diseases and financial contagion in economic systems. Solutions for these optimization tasks that are based purely on topological arguments are not fully satisfactory; in realistic settings, the problem is often characterized by heterogeneous interactions and requires interventions in a dynamic fashion over a finite time window via a restricted set of controllable nodes. The optimal distribution of available resources hence results from an interplay between network topology and spreading dynamics. We show how these problems can be addressed as particular instances of a universal analytical framework based on a scalable dynamic message-passing approach and demonstrate the efficacy of the method on a variety of real-world examples.

Footnotes

  • ?1To whom correspondence should be addressed. Email: lokhov{at}lanl.gov.

Online Impact

                                      1. 99132880 2018-01-23
                                      2. 802899879 2018-01-23
                                      3. 295573878 2018-01-23
                                      4. 352668877 2018-01-23
                                      5. 984633876 2018-01-23
                                      6. 545928875 2018-01-23
                                      7. 976569874 2018-01-23
                                      8. 871324873 2018-01-23
                                      9. 263462872 2018-01-23
                                      10. 577161871 2018-01-23
                                      11. 255603870 2018-01-23
                                      12. 117346869 2018-01-23
                                      13. 90982868 2018-01-23
                                      14. 663415867 2018-01-23
                                      15. 793874866 2018-01-23
                                      16. 843582865 2018-01-23
                                      17. 864971864 2018-01-22
                                      18. 258841863 2018-01-22
                                      19. 957295862 2018-01-22
                                      20. 553518861 2018-01-22