The modern world can be best described as interlinked networks, of individuals, computing devices and social networks; where information and opinions propagate through their edges in a probabilistic or deterministic manner via interactions between individual constituents. These interactions can take the form of political discussions between friends, gossiping about movies, or the transmission of computer viruses. Winners are those who maximise the impact of scarce resource such as political activists or advertisements, or by applying resource to the most influential available nodes at the right time. We developed an analytical framework, motivated by and based on statistical physics tools, for impact maximisation in probabilistic information propagation on networks; to better understand the optimisation process macroscopically, its limitations and potential, and devise computationally efficient methods to maximise impact (an objective function) in specific instances.
The research questions we have addressed relate to the manner in which one could maximise the impact of information propagation by providing inputs at the right time to the most effective nodes in the particular network examined, where the impact is observed at some later time. It is based on a statistical physics inspired analysis, Dynamical Message Passing that calculates the probability of propagation to a node at a given time, combined with a variational optimisation process. The work has successfully addressed the following questions: 1) Given a graph and a propagation/infection process, which nodes are best to infect to maximise the spreading? Given a limited budget, how many nodes one can infect within a given time? How long will it take one to infect all nodes? 2) Maximising the impact on a subset of particular nodes at given times, by accessing a limited number of given nodes. 3) Identify the most appropriate vaccination targets in order to isolate a spreading disease through containment and islanding of an epidemic. Numerical studies on benchmark problems show the efficacy of the method both for information propagation in time and vaccination.
A. Y. Lokhov and D. Saad, arXiv:1608.08278 (2016)