Eur. Phys. J. B (2016) 89: 253
https://doi.org/10.1140/epjb/e2016-70329-6

Regular Article

Optimal selection of nodes to propagate influence on networks

Center of Applied Statistics, School of Statistics, Renmin University of China, Zhong-Guan-Cun Street 59, Beijing 100872, P.R. China

^a e-mail: sunyifan1984@163.com

Received: 24 May 2016
Received in final form: 29 August 2016
Published online: 21 November 2016

Abstract

How to optimize the spreading process on networks has been a hot issue in complex networks, marketing, epidemiology, finance, etc. In this paper, we investigate a problem of optimizing locally the spreading: identifying a fixed number of nodes as seeds which would maximize the propagation of influence to their direct neighbors. All the nodes except the selected seeds are assumed not to spread their influence to their neighbors. This problem can be mapped onto a spin glass model with a fixed magnetization. We provide a message-passing algorithm based on replica symmetrical mean-field theory in statistical physics, which can find the nearly optimal set of seeds. Extensive numerical results on computer-generated random networks and real-world networks demonstrate that this algorithm has a better performance than several other optimization algorithms.